| 多核平台并行单源最短路径算法 |
| |
| 引用本文： | 黄跃峰,钟耳顺.多核平台并行单源最短路径算法[J].计算机工程,2012,38(3):1-3. |
| |
| 作者姓名： | 黄跃峰 钟耳顺 |
| |
| 作者单位： | 1. 中国科学院地理科学与资源研究所资源与环境信息系统国家重点实验室,北京100101;中国科学院研究生院,北京100049
2. 中国科学院地理科学与资源研究所资源与环境信息系统国家重点实验室,北京,100101 |
| |
| 基金项目： | 国家“863”计划基金资助项目（2009AA12Z331） |
| |
| 摘 要： | 提出一种多核平台并行单源最短路径算法。采用与Δ-Stepping算法相似的并行策略，通过多个子线程对同一个桶中的弧段进行并行松弛，利用主线程控制串行搜索中桶的序列。实验结果表明，该算法求解全美单源最短路径的时间约为4 s，与使用相同代码实现的串行算法相比，加速比更高。
|
| 关 键 词： | 并行算法 最短路径 网络分析 多核平台 |
| 收稿时间： | 2011-07-06 |
Parallel Single-source Shortest Path Algorithm on Multi-core Platform |
| |
| HUANG Yue-feng
,
ZHONG Er-shun.Parallel Single-source Shortest Path Algorithm on Multi-core Platform[J].Computer Engineering,2012,38(3):1-3. |
| |
| Authors: | HUANG Yue-feng ZHONG Er-shun |
| |
| Affiliation: | 1. State Key Lab of Resources and Environmental Information System, Institute of Geographic Sciences and Natural Resources Research, Chinese Academy of Sciences, Beijing 100101, China; 2. Graduate University of Chinese Academy of Sciences, Beijing 100049, China) |
| |
| Abstract: | A multi-thread parallel Single-source Shortest Path（SSSP） algorithm is proposed in multi-cores platform. It employs buckets to sort and uses the similar parallel strategy of A-Stepping algorithm. It does edge relaxations of the same bucket in parallel by slave threads, and searches all buckets in sequence by master thread. Experimental results show that this algorithm performs 4 seconds in the USA road network, achieving a higher speedup compared with serial parallel algorithm using same code. |
| |
| Keywords: | parallel algorithm shorlest path network analysis multi-core platform |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《计算机工程》浏览原始摘要信息 |
|
点击此处可从《计算机工程》下载全文 |
