%0 Journal Article
%T GPU-based Algorithm of Shortest Path<br>基于GPU的全源最短路径算法
%A XING Xing-xing ZHAO Guo-xing LUO Zu-ying FANG Hao
%A <br>邢星星
%A 赵国兴
%A 骆祖莹
%A 方浩
%J 计算机科学
%D 2012
%I 
%X As for the all-pairs shortest path problem in the graph, based on parallel algorithm in the CPU cluster envi- ronment, depending on parallel speedup mechanism on the GPU, in order to increase the parallelism and locality, chess- board division method was chosen for task division in this parallel algorithm on the GPU. Because the graph scale is lar- ger than the display memory, the asynchronous parallel algorithm on the GPU was presented. hhe experimental data proves that the algorithm has accelerating effects below compared with CPU with single core: first, for the small graph whose vertexes arc less than 10000, it is about 155 times faster; second,for the large graph whose vertexes arc more than 10000,it is about 25 times faster.
%K Shortest path
%K GPU
%K Chessboard division
%K Floyd<br>全源最短路径
%K GPU
%K 棋盘划分
%K Floyd算法
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=64A12D73428C8B8DBFB978D04DFEB3C1&aid=D5B7C4A24E11D7BA17EE09595612460D&yid=99E9153A83D4CB11&vid=7C3A4C1EE6A45749&iid=38B194292C032A66&sid=BF112261B65CB9C9&eid=358F98408588E522&journal_id=1002-137X&journal_name=计算机科学&referenced_num=0&reference_num=0