РАЗНОРОДНЫЙ БЛОЧНЫЙ АЛГОРИТМ ПОИСКА КРАТЧАЙШИХ ПУТЕЙ МЕЖДУ ВСЕМИ ПАРАМИ ВЕРШИН ГРАФА

Рассматривается проблема поиска кратчайших путей между всеми парами вершин взвешенного ориентированного графа. Известны алгоритмы Дейкстры и Флойда-Уоршелла, однородные блочные и параллельные алгоритмы и другие алгоритмы решения этой проблемы. Предлагается новый разнородный блочный алгоритм, рассматривающий различные типы блоков и учитывающий разделяемую иерархическую организации памяти и многоядерность процессоров при вычислении блока каждого типа. На теоретическом и экспериментальном уровнях проводится сравнение предлагаемых разнородных алгоритмов вычисления блоков с общепринятым однородным универсальным алгоритмом пересчета блока. Основной акцент делается на использовании вариантов неоднородности, взаимодействия блоков во время вычислений и вариаций в размере блока, размере матрицы блоков и общего количества блоков с целью выявления возможности сокращения объема вычислений, производимых при расчете блока, сокращения активности работы с кэш памятью процессора и выявления влияния времени расчета каждого типа блока на общее время выполнения разнородного блочного алгоритма. Предложен рекуррентный ресинхронизированный алгоритм расчета диагонального блока (D0), улучшающий использование кэш памяти процессора и сокращающий количество итераций и размер данных, необходимых для расчёта диагонального блока до 3 раз, что дает ускорение в расчете диагонального блока до 60%. Для более эффективной работы с кэш памятью предложены варианты перестановки основных циклов k-i-j алгоритмов расчета блоков креста (C1, C2) и обновляемых блоков (U3), использование которых в комбинации с алгоритмом расчета диагонального блока сокращает общее время работы разнородного блочного алгоритма на 13% в среднем по сравнению с однородным блочным алгоритмом.

1. Floyd, R. W. Algorithm 97: Shortest path / R. W. Floyd // Communications of the ACM, 1962, 5(6), p. 345.

2. Hofner, P. Dijkstra, Floyd and Warshall Meet Kleene/ P. Hofner and B. Moller // Formal Aspect of Computing, Vol.24, No.4, 2012, № 2, pp. 459–476.

3. Venkataraman, G. A Blocked All-Pairs Shortest Paths Algorithm / G. Venkataraman, S. Sahni, S. Mukhopadhyaya // Journal of Experimental Algorithmics (JEA), Vol 8, 2003, pp. 857–874

4. Park, J. S. Optimizing graph algorithms for improved cache performance / J. S. Park, M. Penner, and V. K. Prasanna // IEEE Trans. on Parallel and Distributed Systems, 2004, 15(9), pp. 769–782.

5. Albalawi, E. Task Level Parallelization of All Pair Shortest Path Algorithm in OpenMP 3.0 / E. Albalawi, P. Thulasiraman, R. Thulasiram // 2ndInternational Conference on Advances in Computer Science and Engineering (CSE 2013), 2013, Los Angeles, CA, July 1–2, 2013, pp. 109–112.

6. Tang, P. Rapid Development of Parallel Blocked All-Pairs Shortest Paths Code for Multi-Core Computers / P. Tang // IEEE SOUTHEASTCON 2014, pp. 1–7.

7. Solomonik, E. Minimizing Communication in All Pairs Shortest Paths / E. Solomonik, A. Buluc, and J. Demmel // IEEE 27th International Symposium on Parallel & Distributed Processing, 2013, pp. 548–559.

8. Singh, A. Performance Analysis of Floyd Warshall Algorithm vs Rectangular Algorithm / A. Singh, P. K. Mishra // International Journal of Computer Applications, Vol.107, No.16, 2014, pp. 23–27.

9. Madduri, K. An Experimental Study of a Parallel Shortest Path Algorithm for Solving Large-Scale Graph Instances / K Madduri,. D. Bader, J. W. Berry, J. R. Crobak // Proceedings of the Ninth Workshop on Algorithm Engineering and Experiments (ALENEX), 2007, pp. 23–35.

10. Prihozhy, A. Synthesis and Optimization of Pipelines for HW Implementations of Dataflow Programs / A. Prihozhy, E. Bezati, H. Rahman, M. Mattavelli // IEEE Trans. on CAD of Integrated Circuits and Systems, Vol. 34, No. 10, 2015, pp. 1613–1626.