The All-Pair Shortest-Path Problem in Shared-Memory Heterogeneous Systems

Abstract

This chapter faces the All-Pair Shortest-Path problem for sparse graphs combining parallel algorithms and parallel-productivity methods in heterogeneous systems. As this problem can be divided into independent Single-Source ShortestPath subproblems, we distribute this computation space into different processing units, CPUs and graphical processing units (GPUs), that are usually present in modern shared-memory systems. Although the powerful GPUs are significantly faster than the CPUs, its combined use leads to better execution times. Furthermore, two different policies have been used for the scheduling issue, an equitable scheduling, where the workspace is equitably divided between all computational units independently of its nature, and a work-stealing scheduling, where a computational unit steals a new task when it has finished its previous work.