Track: Optimization

Abstract

With its multicore technology designed for intensive computation, graphics processing units (GPUs) have advanced tremendously in recent years. The GPU is a multicore coprocessor with dozens or even hundreds of cores designed for intensive computations, unlike a central processing unit (CPU), which has a limited number of cores available. However, CPUs have large caches for accommodating large amounts of data, whereas GPUs have smaller caches but use a massive amount of threads. In order to achieve the best performance from both CPU and GPU, GPU-CPU heterogeneous computing architectures have emerged, resulting in a paradigm shift in parallel computing. Data parallelism, also known as SIMD (single instruction, multiple data), is realized through this paradigm, which allows multiple threads to execute the same task simultaneously on different subsets of the same data. When data parallelism is used to program, it is particularly relevant when there is a lot of data to process, as is often the case in scientific computing. Due to their inherent nature as intensive computing, data parallelism is ideally suited for meta-heuristics. As part of this research, data parallelism is introduced to meta-heuristics, as well as a particular optimization technique called "tiling" in parallel computing. "Tiling" refers to grouping threads into tiles to share access to programmable caches on GPUs in order to improve computation speed, particularly for programs that use the same data repeatedly. We introduce the "tiling" technique to ant colony optimization, a meta-heuristic for solving quadratic assignment problem (QAP). A heterogeneous computing architecture is expected to provide benefits in speed, quality, and efficiency over a CPU alone.