HETEROGENIOUS BLOCKED ALL-PAIRS SHORTEST PATHS ALGORITHM
The problem of finding the shortest paths between all pairs of vertices in a weighted directed graph is considered. The algorithms of Dijkstra and Floyd-Warshall, homogeneous block and parallel algorithms and other algorithms of solving this problem are known. A new heterogeneous block algorithm is...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Belarusian National Technical University
2017-11-01
|
| Series: | Sistemnyj Analiz i Prikladnaâ Informatika |
| Subjects: | |
| Online Access: | https://sapi.bntu.by/jour/article/view/178 |
| _version_ | 1797873794718629888 |
|---|---|
| author | A. A. Prihozhy O. N. Karasik |
| author_facet | A. A. Prihozhy O. N. Karasik |
| author_sort | A. A. Prihozhy |
| collection | DOAJ |
| description | The problem of finding the shortest paths between all pairs of vertices in a weighted directed graph is considered. The algorithms of Dijkstra and Floyd-Warshall, homogeneous block and parallel algorithms and other algorithms of solving this problem are known. A new heterogeneous block algorithm is proposed which considers various types of blocks and takes into account the shared hierarchical memory organization and multi-core processors for calculating each type of block. The proposed heterogeneous block computing algorithms are compared with the generally accepted homogeneous universal block calculation algorithm at theoretical and experimental levels. The main emphasis is on using the nature of the heterogeneity, the interaction of blocks during computation and the variation in block size, the size of the block matrix and the total number of blocks in order to identify the possibility of reducing the amount of computation performed during the calculation of the block, reducing the activity of the processor’s cache memory and determining the influence of the calculation time of each block type on the total execution time of the heterogeneous block algorithm. A recurrent resynchronized algorithm for calculating the diagonal block (D0) is proposed, which improves the use of the processor’s cache and reduces the number of iterations up to 3 times that are necessary to calculate the diagonal block, which implies the acceleration in calculating the diagonal block up to 60%. For more efficient work with the cache memory, variants of permutation of the basic loops k-i-j in the algorithms of calculating the blocks of the cross (C1 and C2) and the updated blocks (U3) are proposed. These permutations in combination with the proposed algorithm for calculating the diagonal block reduce the total runtime of the heterogeneous block algorithm to 13% on average against the homogeneous block algorithm. |
| first_indexed | 2024-04-10T01:20:41Z |
| format | Article |
| id | doaj.art-7674cc861f23409f94de50a89e514606 |
| institution | Directory Open Access Journal |
| issn | 2309-4923 2414-0481 |
| language | English |
| last_indexed | 2024-04-10T01:20:41Z |
| publishDate | 2017-11-01 |
| publisher | Belarusian National Technical University |
| record_format | Article |
| series | Sistemnyj Analiz i Prikladnaâ Informatika |
| spelling | doaj.art-7674cc861f23409f94de50a89e5146062023-03-13T09:47:40ZengBelarusian National Technical UniversitySistemnyj Analiz i Prikladnaâ Informatika2309-49232414-04812017-11-0103687510.21122/2309-4923-2017-3-68-75138HETEROGENIOUS BLOCKED ALL-PAIRS SHORTEST PATHS ALGORITHMA. A. Prihozhy0O. N. Karasik1Белорусский национальный технический университетБелорусский национальный технический университетThe problem of finding the shortest paths between all pairs of vertices in a weighted directed graph is considered. The algorithms of Dijkstra and Floyd-Warshall, homogeneous block and parallel algorithms and other algorithms of solving this problem are known. A new heterogeneous block algorithm is proposed which considers various types of blocks and takes into account the shared hierarchical memory organization and multi-core processors for calculating each type of block. The proposed heterogeneous block computing algorithms are compared with the generally accepted homogeneous universal block calculation algorithm at theoretical and experimental levels. The main emphasis is on using the nature of the heterogeneity, the interaction of blocks during computation and the variation in block size, the size of the block matrix and the total number of blocks in order to identify the possibility of reducing the amount of computation performed during the calculation of the block, reducing the activity of the processor’s cache memory and determining the influence of the calculation time of each block type on the total execution time of the heterogeneous block algorithm. A recurrent resynchronized algorithm for calculating the diagonal block (D0) is proposed, which improves the use of the processor’s cache and reduces the number of iterations up to 3 times that are necessary to calculate the diagonal block, which implies the acceleration in calculating the diagonal block up to 60%. For more efficient work with the cache memory, variants of permutation of the basic loops k-i-j in the algorithms of calculating the blocks of the cross (C1 and C2) and the updated blocks (U3) are proposed. These permutations in combination with the proposed algorithm for calculating the diagonal block reduce the total runtime of the heterogeneous block algorithm to 13% on average against the homogeneous block algorithm.https://sapi.bntu.by/jour/article/view/178алгоритм флойда-уоршеллакратчайший путьразнородный блочный алгоритммногоядерная системаразделяемая кэш память |
| spellingShingle | A. A. Prihozhy O. N. Karasik HETEROGENIOUS BLOCKED ALL-PAIRS SHORTEST PATHS ALGORITHM Sistemnyj Analiz i Prikladnaâ Informatika алгоритм флойда-уоршелла кратчайший путь разнородный блочный алгоритм многоядерная система разделяемая кэш память |
| title | HETEROGENIOUS BLOCKED ALL-PAIRS SHORTEST PATHS ALGORITHM |
| title_full | HETEROGENIOUS BLOCKED ALL-PAIRS SHORTEST PATHS ALGORITHM |
| title_fullStr | HETEROGENIOUS BLOCKED ALL-PAIRS SHORTEST PATHS ALGORITHM |
| title_full_unstemmed | HETEROGENIOUS BLOCKED ALL-PAIRS SHORTEST PATHS ALGORITHM |
| title_short | HETEROGENIOUS BLOCKED ALL-PAIRS SHORTEST PATHS ALGORITHM |
| title_sort | heterogenious blocked all pairs shortest paths algorithm |
| topic | алгоритм флойда-уоршелла кратчайший путь разнородный блочный алгоритм многоядерная система разделяемая кэш память |
| url | https://sapi.bntu.by/jour/article/view/178 |
| work_keys_str_mv | AT aaprihozhy heterogeniousblockedallpairsshortestpathsalgorithm AT onkarasik heterogeniousblockedallpairsshortestpathsalgorithm |