Threaded block-parallel algorithm for finding the shortest paths on graph
The problem of finding the shortest paths on weighted graphs is considered. The variants of statement of the problem, known algorithms for it solving, areas of practical application and existing challenges, in particular, the challenge of scalability, are analyzed. The class of block-parallel algori...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | Russian |
| Published: |
Educational institution «Belarusian State University of Informatics and Radioelectronics»
2019-06-01
|
| Series: | Doklady Belorusskogo gosudarstvennogo universiteta informatiki i radioèlektroniki |
| Subjects: | |
| Online Access: | https://doklady.bsuir.by/jour/article/view/969 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849243446187917312 |
|---|---|
| author | O. N. Karasik A. A. Prihozhy |
| author_facet | O. N. Karasik A. A. Prihozhy |
| author_sort | O. N. Karasik |
| collection | DOAJ |
| description | The problem of finding the shortest paths on weighted graphs is considered. The variants of statement of the problem, known algorithms for it solving, areas of practical application and existing challenges, in particular, the challenge of scalability, are analyzed. The class of block-parallel algorithms, their advantages and disadvantages is investigated. A fast block-parallel threaded algorithm oriented to large-sized graphs is proposed. It differs by changing the order of block calculations, reducing the critical path and operating time on a multi-core system, decreasing the data exchanges among local caches of cores and between neighbor levels of hierarchical memory. |
| format | Article |
| id | doaj-art-1cfaa21a5b0b4cd1b07ad9fef50f58bd |
| institution | Kabale University |
| issn | 1729-7648 |
| language | Russian |
| publishDate | 2019-06-01 |
| publisher | Educational institution «Belarusian State University of Informatics and Radioelectronics» |
| record_format | Article |
| series | Doklady Belorusskogo gosudarstvennogo universiteta informatiki i radioèlektroniki |
| spelling | doaj-art-1cfaa21a5b0b4cd1b07ad9fef50f58bd2025-08-20T03:59:27ZrusEducational institution «Belarusian State University of Informatics and Radioelectronics»Doklady Belorusskogo gosudarstvennogo universiteta informatiki i radioèlektroniki1729-76482019-06-01027784968Threaded block-parallel algorithm for finding the shortest paths on graphO. N. Karasik0A. A. Prihozhy1Белорусский национальный технический университетБелорусский национальный технический университетThe problem of finding the shortest paths on weighted graphs is considered. The variants of statement of the problem, known algorithms for it solving, areas of practical application and existing challenges, in particular, the challenge of scalability, are analyzed. The class of block-parallel algorithms, their advantages and disadvantages is investigated. A fast block-parallel threaded algorithm oriented to large-sized graphs is proposed. It differs by changing the order of block calculations, reducing the critical path and operating time on a multi-core system, decreasing the data exchanges among local caches of cores and between neighbor levels of hierarchical memory.https://doklady.bsuir.by/jour/article/view/969graphshortest pathblocked algorithmparallel computingmultithreading |
| spellingShingle | O. N. Karasik A. A. Prihozhy Threaded block-parallel algorithm for finding the shortest paths on graph Doklady Belorusskogo gosudarstvennogo universiteta informatiki i radioèlektroniki graph shortest path blocked algorithm parallel computing multithreading |
| title | Threaded block-parallel algorithm for finding the shortest paths on graph |
| title_full | Threaded block-parallel algorithm for finding the shortest paths on graph |
| title_fullStr | Threaded block-parallel algorithm for finding the shortest paths on graph |
| title_full_unstemmed | Threaded block-parallel algorithm for finding the shortest paths on graph |
| title_short | Threaded block-parallel algorithm for finding the shortest paths on graph |
| title_sort | threaded block parallel algorithm for finding the shortest paths on graph |
| topic | graph shortest path blocked algorithm parallel computing multithreading |
| url | https://doklady.bsuir.by/jour/article/view/969 |
| work_keys_str_mv | AT onkarasik threadedblockparallelalgorithmforfindingtheshortestpathsongraph AT aaprihozhy threadedblockparallelalgorithmforfindingtheshortestpathsongraph |