Самая быстрая и энергоэффективная реализация алгоритма поиска в ширину на одноузловых различных параллельных архитектурах согласно рейтингу Graph500
Автор: Колганов Александр Сергеевич
Рубрика: Вычислительная математика
Статья в выпуске: 2 т.7, 2018 года.
Бесплатный доступ
Поиск в ширину является одним из основных алгоритмов обхода графа и базовым для многих алгоритмов анализа графов более высокого уровня. Поиск в ширину на графах является задачей с нерегулярным доступом к памяти и с нерегулярной зависимостью по данным, что сильно усложняет его распараллеливание на все существующие архитектуры. В статье будет рассмотрена реализация алгоритма поиска в ширину (основного теста рейтинга Graph500) для обработки больших графов на различных архитектурах: Intel х86, IBM Power8+, Intel KNL и NVidia GPU. Будет рассмотрены алгоритмы реализации поиска в ширину, такие как top-down обход, bottom-up обход и гибридный обход, содержащий в себе как top-down, так и bottom-up обходы. Будут описаны особенности реализации алгоритма на общей памяти, а также преобразования графа: локальная сортировка вершин графа, глобальная сортировка вершин графа, перенумерация всех вершин графа, сжатое представление вершин графа. Данные преобразования и гибридный алгоритм обхода позволяют достичь рекордных показателей производительности и энергоэффективности на данном алгоритме среди всех одноузловых систем рейтинга Graph500 и GreenGraph500.
Параллельная обработка графов
Короткий адрес: https://sciup.org/147160643
IDR: 147160643 | УДК: 004.021 | DOI: 10.14529/cmse180201
The fastest and energy-efficient breadth-first search algorithm on a single node with various parallel architectures according to Graph500
The breadth-first search algorithm is one of the basic algorithms for graph traversing and is used in many other algorithms of high-level graph analysis. BFS is characterized with intensive irregular memory accesses and a random data dependency, which greatly complicates its parallelization to all existing architectures. The paper considers the implementation of the BFS algorithm (the core benchmark of the Graph500 rating) for processing large graphs on different architectures: Intel x86, IBM Power8+, Intel KNL and NVidia GPU. Algorithms for implementing breadth-first search will be considered, such as top-down traverse, bottom-up traverse, and a hybrid traverse that includes both top-down and bottom-up traverses. The features of the algorithm implementation on shared memory will be shown, as well as graph transformations (local sorting of graph vertices, global sorting of graph vertices, renumbering of all graph vertexes, compressed representation of graph vertices), which allow achieving the best performance and energy-efficiency in this algorithm among all single-node systems of Graph500 and GreenGraph500 ratings.
Список литературы Самая быстрая и энергоэффективная реализация алгоритма поиска в ширину на одноузловых различных параллельных архитектурах согласно рейтингу Graph500
- Cherkassky B.V., Goldberg A.V., Radzik T. Shortest Paths Algorithms: Theory and Experimental Evaluation//Math. Program. 1996. Vol. 73. P. 129-174 DOI: 10.1007/BF02592101
- Moore E.F. The Shortest Path through a Maze//Proceedings of the International Symposium on the Theory of Switching (2-5 April 1957). Harvard University Press, 1959. P. 285-292.
- Chazelle B.A. Minimum Spanning Tree Algorithm with Inverse-ackermann Type Complexity//Journal of the ACM. 2000. Vol. 47, No. 6. P. 1028-1047 DOI: 10.1145/355541.355562
- Колганов А.С. Параллельная реализация алгоритма поиска минимальных остовных деревьев с использованием центрального и графического процессоров//Вестник Южно-Уральского государственного университета. Серия: Вычислительная математика и информатика. 2016. Т. 5, № 3. С. 5-19 DOI: 10.14529/cmse160301
- Рейтинг Graph500. URL: http://graph500.org/(дата обращения 01.12.2017)
- Рейтинг GreenGraph500. URL: http://green.graph500.org/(дата обращения 01.12.2017)
- Cormen T., Leiserson, C., Rivest R. Introduction to Algorithms. MIT Press, Cambridge. 1990.
- Edmonds J., Karp R.M. Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems//Journal of the ACM. 1972. Vol. 19, No. 2. P. 248-264 DOI: 10.1007/3-540-36478-1_4
- Brandes U. A Faster Algorithm for Betweenness Centrality//J. Math. Sociol. 2001. Vol. 25, No. 2. P. 163-177 DOI: 10.1080/0022250X.2001.9990249
- Frasca M., Madduri K., Raghavan P. NUMA-Aware Graph Mining Techniques for Performance and Energy Efficiency//Proc. ACM/IEEE Int. Conf. High Performance Computing, Networking, Storage and Analysis (Salt Lake City, Utah, USA, November 10-16, 2012). P. 1-11 DOI: 110.1109/SC.2012.81
- Girvan M., Newman M.E. Community Structure in Social and Biological Networks//Proc. Natl. Acad. Sci. (USA, June 11, 2002). Vol. 99, No. 12. P. 7821-7826 DOI: 10.1073/pnas.122653799
- Dijkstra E.W. A Note on Two Problems in Connexion with Graphs//Numerische Mathematik. 1959. Vol. 1, No. 1. P. 269-271 DOI: 10.1007/BF01386390
- Рейтинг Top500. URL: https://www.top500.org/(дата обращения 01.12.2017)
- Bader D.A., Madduri K. Designing Multithreaded Algorithms for Breadth-first Search and St-connectivity on the Cray MTA-2. 2006. P. 523-530 DOI: 10.1109/ICPP.2006.34
- Korf R.E., Schultze P. Large-scale Parallel Breadth-first Search//AAAI. 2005. P. 1380-1385.
- Yoo A., Chow E., Henderson K., McLendon W., Hendrickson B., Catalyurek U. A Scalable Distributed Parallel Breadth-first Search Algorithm on BlueGene/L//Proceedings of the 2005 ACM/IEEE Conference on Supercomputing (Seattle, Washington, USA, November 12-18, 2005) DOI: 10.1109/SC.2005.4
- Zhang Y., Hansen E.A. Parallel Breadth-first Heuristic Search on a Shared-memory Architecture//AAAI Workshop on Heuristic Search, Memory-Based Heuristics and Their Applications. 2006.
- Yasui Y., Fujisawa K., Sato Y. Fast and Energy-efficient Breadth-First Search on a Single NUMA System//Lecture Notes in Computer Science. Vol. 8488. P. 365-381 DOI: 10.1007/978-3-319-07518-1_23
- Hiragushi T., Takahashi D. Efficient Hybrid Breadth-First Search on GPUs//Lecture Notes in Computer Science. Vol. 8286. P. 40-50 DOI: 10.1007/978-3-319-03889-6_5
- Merrill D., Garland M., Grimshaw A. Scalable GPU Graph Traversal//Proceedings of the 17th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (New Orleans, Louisiana, USA, February 25-29, 2012). P. 117-128 DOI: 10.1145/2370036.2145832
- Chakrabarti D., Zhan Y., Faloutsos C. R-MAT: A Recursive Model for Graph Mining//Proceedings of the 2004 SIAM International Conference on Data Mining (Florida, USA, April 22-24, 2004). P. 442-446 DOI: 10.1137/1.9781611972740.43
- Pissanetzky S. Sparse Matrix Technology. Academic Press. 1984.
- Динамический параллелизм в CUDA. URL: https://devblogs.nvidia.com/parallelforall/cuda-dynamic-parallelism-api-principles/(дата обращения 01.12.2017)
- Спецификация процессора Intel Xeon Phi 7250. URL: https://ark.intel.com/ru/products/94035/Intel-Xeon-Phi-Processor-7250-16GB-1_40-GHz-68-core (дата обращения 01.12.2017)
- Спецификация процессора Intel Xeon E5 2699 v3. URL: https://ark.intel. com/ru/products/81061/Intel-Xeon-Processor-E5-2699-v3-45M-Cache-2_30-GHz (дата обращения 01.12.2017)
- Спецификация процессоров IBM Power8 и NVidia Tesla P100. URL: https://www-03. ibm.com/systems/ru/power/hardware/s822lc-hpc/(дата обращения 01.12.2017)
- Технология NVLink. URL: http://www.nvidia.com/object/nvlink.html (дата обращения 01.12.2017)
