A parallel Dijkstra algorithm based on multi-granularity communication

被引：0

作者：

Sun, Wenbin ^{[1
]}

Tan, Zhenglong ^{[1
]}

Wang, Jiang ^{[1
]}

Zhao, Shuaiyang ^{[1
]}

机构：

[1] School of Geoscience and Surveying Engineering, China University of Mining and Technology(Beijing), Beijing,100083, China

来源：

Zhongguo Kuangye Daxue Xuebao/Journal of China University of Mining and Technology | 2014年 / 43卷 / 05期

关键词：

Bi-directional search - Communication method - Communication time - Dijkstra algorithms - MPI communications - Network segmentation - Parallelization algorithms - Shortest path algorithms;

D O I：

暂无

中图分类号：

学科分类号：

摘要：

Parallelizing serial algorithm is one of effective methods to improve shortest path algorithm efficiency. A new parallel method based on the idea of bidirectional search and overlapping network segmentation is approached in this paper. In order to reduce communication time of shortest path algorithm, a multi-granularity communication method among different processes is described. The experiment is done by using of American road network data provided by DIMAS. The result indicates: overlapping network segmentation method is an effective selection for shortest path algorithm; improving communication multi-granularity size reduces communication time of different processes in parallelization algorithm; MPI communication time by transferring 50 network nodes each time is one-tenth of that by transferring 1 network node.

引用

页码：938 / 943

共 50 条

[21] Track planning model of USV based on multi-granularity pattern ant colony algorithm
Ma, Liang
Liu, Ting Yin
Shen, Zhan Sheng
2023 35TH CHINESE CONTROL AND DECISION CONFERENCE, CCDC, 2023, : 3119 - 3122
[22] Multi-granularity Fatigue in Recommendation
Xie, Ruobing
Ling, Cheng
Zhang, Shaoliang
Xia, Feng
Lin, Leyu
PROCEEDINGS OF THE 31ST ACM INTERNATIONAL CONFERENCE ON INFORMATION AND KNOWLEDGE MANAGEMENT, CIKM 2022, 2022, : 4595 - 4599
[23] MGPA: a multi-granularity space preallocation algorithm for object-based storage devices
He, Shuibing
Yang, Yuanhua
Xu, Xianbin
Xu, Xiaohua
INTERNATIONAL JOURNAL OF EMBEDDED SYSTEMS, 2016, 8 (2-3) : 237 - 248
[24] A multi-granularity ensemble algorithm for medical image classification based on broad learning system
Li, Keyuan
Zhang, Qinghua
Xie, Qin
Huang, Shuaishuai
JOURNAL OF INTELLIGENT & FUZZY SYSTEMS, 2024, 46 (03) : 5853 - 5867
[25] Multi-granularity Attribute Reduction
Liang, Shaochen
Liu, Keyu
Chen, Xiangjian
Wang, Pingxin
Yang, Xibei
ROUGH SETS, IJCRS 2018, 2018, 11103 : 61 - 72
[26] Multi-granularity for knowledge distillation
Shao, Baitan
Chen, Ying
IMAGE AND VISION COMPUTING, 2021, 115 (115)
[27] Multi-granularity resource Reservations
Saewong, S
Rajkumar, R
RTSS 2005: 26th IEEE International Real-Time Systems Symposium, Proceedings, 2005, : 143 - 153
[28] Multi-Granularity Representations of Dialog
Mehri, Shikib
Eskenazi, Maxine
2019 CONFERENCE ON EMPIRICAL METHODS IN NATURAL LANGUAGE PROCESSING AND THE 9TH INTERNATIONAL JOINT CONFERENCE ON NATURAL LANGUAGE PROCESSING (EMNLP-IJCNLP 2019): PROCEEDINGS OF THE CONFERENCE, 2019, : 1752 - 1761
[29] Irregular object simplify method based on multi-granularity
Liao, Xiaoping
Xiao, Haihua
Ma, Junyan
PROCEEDINGS OF THE 3RD INTERNATIONAL CONFERENCE ON MECHATRONICS AND INDUSTRIAL INFORMATICS, 2015, 31 : 535 - 541
[30] Information mining based on Multi-Granularity News Fusion
Yu, Wei
Tang, Xiaoyue
Gan, Lin
Li, Shijun
Zhang, Yunlu
Wang, Jun
ADVANCES IN APPLIED SCIENCES AND MANUFACTURING, PTS 1 AND 2, 2014, 850-851 : 592 - +

← 1 2 3 4 5 →