high performance computing on graphics processing units: hgpu.org

Many graph algorithms have given solution to the problem of finding shortest paths between nodes in a graph. These problems are considered among the fundamental combinatorial optimization problems. They have many applications, such as car/robot navigation systems, traffic simulations, tramp steamer problem, courier-scheduling optimization, Internet route planners, web searching, or exploiting arbitrage opportunities in currency exchange, among others. During the last decades, the interest of the scientific community in these problems has significantly increased not only due to this wide-applicability, but also thanks to the currently popular and efficient parallel computing. Additionally, the advent of new parallel programming models together with modern powerful hardware accelerators, such as the Graphics Processing Units or the many-core XeonPhis boards, may highly improve the performance of previous parallel algorithms, and also has open the possibility to study new and more efficient parallel approaches to exploit these specific architectures. Furthermore, the emerging of heterogeneous parallel computing combining these powerful hardware accelerators with the classical and increasingly powerful CPUs, provides a perfect environment to face the most costly shortest-path problems in the context of High Performance Computing (HPC). However, the programming of hardware accelerators, the optimization of their running times, and also, the coordination of these devices with other computational units of different nature, are still very complex tasks for non-expert programmers. One important indicator of the added complexity found in these environments is the lack of studies to guide the programmer into the correct use of proper values for GPU runtime configuration parameters. Regarding the coordination of different computational devices, there are also few models or frameworks that simplifies the programming when different parallel computing layers are used, to combine the use of many-cores and classical CPU cores present in a shared-memory system, or even from different systems. This Ph.D. thesis addresses both mentioned problems, the algorithmic GPU programming and the heterogeneous parallel coordination in the context of: Developing new GPU-based approaches to the shortest path problem; the study of the tuning of the GPU configuration parameters; and also, designing solutions where both sequential and parallel algorithms are deployed concurrently in heterogeneous environments.