Solving optimization problems using a hybrid systolic search on GPU plus CPU

Abstract

In recent years, graphics processing units (GPUs) have emerged as a powerful architecture for solving a broad spectrum of applications in very short periods of time. However, most existing GPU optimization approaches do not exploit the full power available in a CPU–GPU platform. They have a tendency to leave one of them partially unused (usually the CPU) and fail to establish an accurate exchange of information that could help solve the target problem efficiently. Thus, better performance is expected from devising a hybrid CPU–GPU parallel algorithm that combines the highly parallel stream processing power of GPUs with the higher power of multi-core architectures. We have developed a hybrid methodology to efficiently solve optimization problems. We use a hybrid CPU–GPU architecture, to benefit from running it, in parallel, on both the CPU and the GPU. Our experiments over a heterogeneous set of combinatorial optimization problems with increasing dimensionality show a time gain of up to 365 × in our proposal, while demonstrating high numerical accuracy. This work is intended to open up a new line of research that matches both architectures with new algorithms and cooperation techniques.