Самая быстрая и энергоэффективная реализация алгоритма поиска в ширину на одноузловых различных параллельных архитектурах согласно рейтингу Graph500

Самая быстрая и энергоэффективная реализация алгоритма поиска в ширину на одноузловых различных параллельных архитектурах согласно рейтингу Graph500

Автор: Колганов Александр Сергеевич

Журнал: Вестник Южно-Уральского государственного университета. Серия: Вычислительная математика и информатика @vestnik-susu-cmi

Рубрика: Вычислительная математика

Статья в выпуске: 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   |   DOI: 10.14529/cmse180201

Список литературы Самая быстрая и энергоэффективная реализация алгоритма поиска в ширину на одноузловых различных параллельных архитектурах согласно рейтингу 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)
Еще
Статья научная
QR-код для установки приложения SciUp Наведите камеру и скачайте бесплатное приложение SciUp