GPU is the mainstream co-processor computers of heterogeneous architecture. Parallel graph algorithms are fundamental for many data-driven applications to be solved on heterogeneous clusters. SSSP (Single Source Shortest Path) algorithm is one of the most important one. We proposed a graph representation structure with unified vertex's degree. This method ensures the data block size consistency. And then, the transferring in memory on this representation makes the data reading in cohesion for CUDA thread blocks. Thirdly, vertex renumbering optimizes the locality of graph vertices to make the relaxing operation more efficient. With data of New York road, we implemented SSSP algorithms of delta-stepping on Nvida Tesla K20x GPU device. The experimental results show that the best unified-degree is approximate to the mode of vertex-degree of the graph. For example of the New York road map, all degrees were unified into 4-degree that results to the biggest speed-up of SSSP algorithm.
展开▼
机译：GPU是异构架构的主流协处理器计算机。并行图算法对于要在异构集群上解决的许多数据驱动应用程序至关重要。 SSSP（单源最短路径）算法是最重要的算法之一。我们提出了具有统一顶点度的图表示结构。此方法可确保数据块大小的一致性。然后，此表示形式在内存中的传输使数据以内聚的方式读取CUDA线程块。第三，顶点重编号可优化图顶点的局部性，从而使松弛操作更有效。利用纽约路的数据，我们在Nvida Tesla K20x GPU设备上实现了增量步进的SSSP算法。实验结果表明，最佳统一度近似于图的顶点度模式。以纽约路线图为例，将所有度数统一为4度数，从而最大程度地提高了SSSP算法的速度。
展开▼
