QQ客服 官方微博 反馈留言

	UniDegree: A GPU-based graph representation for SSSP
	Zhang, Changyou ; Wang, Feng ; Huang, Kun ; Liu, Zhiyou ; Chen, Yifeng
	2015
英文摘要	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. ? Springer International Publishing Switzerland 2015.; EI; 704-715; 9529
语种	英语
出处	15th International Conference on Algorithms and Architectures for Parallel Processing, ICA3PP 2015
DOI标识	10.1007/978-3-319-27122-4_49
内容类型	其他
源URL	[http://ir.pku.edu.cn/handle/20.500.11897/436936]
专题	信息科学技术学院
推荐引用方式 GB/T 7714	Zhang, Changyou,Wang, Feng,Huang, Kun,et al. UniDegree: A GPU-based graph representation for SSSP. 2015-01-01.

个性服务

查看访问统计

相关权益政策

暂无数据

收藏/分享

除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。