计算机科学
計算機科學
계산궤과학
COMPUTER SCIENCE
2012年
3期
299-303
,共5页
邢星星%赵国兴%骆祖莹%方浩
邢星星%趙國興%駱祖瑩%方浩
형성성%조국흥%락조형%방호
全源最短路径%GPU%棋盘划分%Floyd算法
全源最短路徑%GPU%棋盤劃分%Floyd算法
전원최단로경%GPU%기반화분%Floyd산법
针对有向图中每对顶点之间的最短路径问题,基于CPU集群并行算法,根据GPU并行计算加速机制,提出了基于棋盘划分方式的GPU并行算法,以增加算法的并行性与数据的局部性.当有向图规模超过GPU显存限制时,进一步提出了异步并行处理的GPU最短路径算法.实验结果表明,与CPU上单核算法相比,本算法具有如下加速效果:(1)对于节点数少于10000的小规模有向图,可以实现约155倍的加速；(2)对于节点数超过10000的大规模有向图,可实现约25倍的加速.
針對有嚮圖中每對頂點之間的最短路徑問題,基于CPU集群併行算法,根據GPU併行計算加速機製,提齣瞭基于棋盤劃分方式的GPU併行算法,以增加算法的併行性與數據的跼部性.噹有嚮圖規模超過GPU顯存限製時,進一步提齣瞭異步併行處理的GPU最短路徑算法.實驗結果錶明,與CPU上單覈算法相比,本算法具有如下加速效果:(1)對于節點數少于10000的小規模有嚮圖,可以實現約155倍的加速；(2)對于節點數超過10000的大規模有嚮圖,可實現約25倍的加速.
침대유향도중매대정점지간적최단로경문제,기우CPU집군병행산법,근거GPU병행계산가속궤제,제출료기우기반화분방식적GPU병행산법,이증가산법적병행성여수거적국부성.당유향도규모초과GPU현존한제시,진일보제출료이보병행처리적GPU최단로경산법.실험결과표명,여CPU상단핵산법상비,본산법구유여하가속효과:(1)대우절점수소우10000적소규모유향도,가이실현약155배적가속；(2)대우절점수초과10000적대규모유향도,가실현약25배적가속.
