New blocked all-pairs shortest paths algorithms operating on blocks of unequal sizes
In real-world networks, many problems imply finding the All-Pairs Shortest Paths (APSP) and their distances in a graph. Solving the large-scale APSP problem on modern multi-processor (multi-core) systems is the key for various application domains. The computational cost of solving the problem is hig...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Belarusian National Technical University
2024-01-01
|
| Series: | Системный анализ и прикладная информатика |
| Subjects: | |
| Online Access: | https://sapi.bntu.by/jour/article/view/640 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832543670000156672 |
|---|---|
| author | A. A. Prihozhy O. N. Karasik |
| author_facet | A. A. Prihozhy O. N. Karasik |
| author_sort | A. A. Prihozhy |
| collection | DOAJ |
| description | In real-world networks, many problems imply finding the All-Pairs Shortest Paths (APSP) and their distances in a graph. Solving the large-scale APSP problem on modern multi-processor (multi-core) systems is the key for various application domains. The computational cost of solving the problem is high, therefore in many cases approximate solutions are considered as acceptable. The blocked APSP algorithms are a promising approach which can exploit many processors (cores) and their caches in parallel mode efficiently. At the same time, to our best knowledge, all blocked algorithms of the Floyd-Warshall family use blocks of equal sizes. This property limits application of the algorithms. In this paper we propose new blocked algorithms which divide the input graph into unequal subgraphs and divide the matrix of distances between pairs of vertices into blocks of unequal sizes. The algorithms describe the dense subgraphs by the adjacency matrix and describe sparse subgraphs and connections between them by the adjacency list. This approach allows the Floyd-Warshall family algorithms to be used together with Dijkstra family algorithms. It can be applied to large graphs decomposed into dense (clusters) and sparse subgraphs. A new heterogeneous algorithm can significantly reduce the computation time of blocks depending on the block type and size. The contribution of the paper is the development of a new family of blocked APSP algorithms which can handle blocks of unequal sizes, save and extend the advantages of the state-of-the-art algorithms operating on blocks of equal sizes. The proposed algorithms are implemented as single- and multiple-threaded parallel applications for multi-core systems. |
| format | Article |
| id | doaj-art-d3dc6af629a94126951317e0f5a6511a |
| institution | Kabale University |
| issn | 2309-4923 2414-0481 |
| language | English |
| publishDate | 2024-01-01 |
| publisher | Belarusian National Technical University |
| record_format | Article |
| series | Системный анализ и прикладная информатика |
| spelling | doaj-art-d3dc6af629a94126951317e0f5a6511a2025-02-03T11:37:40ZengBelarusian National Technical UniversityСистемный анализ и прикладная информатика2309-49232414-04812024-01-010441310.21122/2309-4923-2023-4-4-13471New blocked all-pairs shortest paths algorithms operating on blocks of unequal sizesA. A. Prihozhy0O. N. Karasik1Belarusian National Technical UniversityISsoft SolutionsIn real-world networks, many problems imply finding the All-Pairs Shortest Paths (APSP) and their distances in a graph. Solving the large-scale APSP problem on modern multi-processor (multi-core) systems is the key for various application domains. The computational cost of solving the problem is high, therefore in many cases approximate solutions are considered as acceptable. The blocked APSP algorithms are a promising approach which can exploit many processors (cores) and their caches in parallel mode efficiently. At the same time, to our best knowledge, all blocked algorithms of the Floyd-Warshall family use blocks of equal sizes. This property limits application of the algorithms. In this paper we propose new blocked algorithms which divide the input graph into unequal subgraphs and divide the matrix of distances between pairs of vertices into blocks of unequal sizes. The algorithms describe the dense subgraphs by the adjacency matrix and describe sparse subgraphs and connections between them by the adjacency list. This approach allows the Floyd-Warshall family algorithms to be used together with Dijkstra family algorithms. It can be applied to large graphs decomposed into dense (clusters) and sparse subgraphs. A new heterogeneous algorithm can significantly reduce the computation time of blocks depending on the block type and size. The contribution of the paper is the development of a new family of blocked APSP algorithms which can handle blocks of unequal sizes, save and extend the advantages of the state-of-the-art algorithms operating on blocks of equal sizes. The proposed algorithms are implemented as single- and multiple-threaded parallel applications for multi-core systems.https://sapi.bntu.by/jour/article/view/640apsp problemblocked algorithmunequal sizes of blocksheterogeneous algorithmmulti-core processormulti-threaded implementation |
| spellingShingle | A. A. Prihozhy O. N. Karasik New blocked all-pairs shortest paths algorithms operating on blocks of unequal sizes Системный анализ и прикладная информатика apsp problem blocked algorithm unequal sizes of blocks heterogeneous algorithm multi-core processor multi-threaded implementation |
| title | New blocked all-pairs shortest paths algorithms operating on blocks of unequal sizes |
| title_full | New blocked all-pairs shortest paths algorithms operating on blocks of unequal sizes |
| title_fullStr | New blocked all-pairs shortest paths algorithms operating on blocks of unequal sizes |
| title_full_unstemmed | New blocked all-pairs shortest paths algorithms operating on blocks of unequal sizes |
| title_short | New blocked all-pairs shortest paths algorithms operating on blocks of unequal sizes |
| title_sort | new blocked all pairs shortest paths algorithms operating on blocks of unequal sizes |
| topic | apsp problem blocked algorithm unequal sizes of blocks heterogeneous algorithm multi-core processor multi-threaded implementation |
| url | https://sapi.bntu.by/jour/article/view/640 |
| work_keys_str_mv | AT aaprihozhy newblockedallpairsshortestpathsalgorithmsoperatingonblocksofunequalsizes AT onkarasik newblockedallpairsshortestpathsalgorithmsoperatingonblocksofunequalsizes |