ГлавнаяАрхивРешение задач на графах с помощью STAR-машины, реализуемой на графических ускорителях

Решение задач на графах с помощью STAR-машины, реализуемой на графических ускорителях | Прикладная дискретная математика. 2016. № 3(33). DOI: 10.17223/20710410/33/9

Для решения многих задач на графах построены эффективные алгоритмы на ассоциативных параллельных процессорах. Но на данный момент нет широко используемых ассоциативных архитектур. Однако с развитием графических ускорителей появилась возможность реализовывать ассоциативные параллельные модели без существенной потери эффективности вычислений, что позволяет применять ассоциативные алгоритмы на практике. Представляется реализация абстрактной модели ассоциативной параллельной обработки данных (STAR-маши-на) на графических ускорителях с помощью технологии CUDA. Измеряется производительность реализации и показывается её эффективность для решения задач на графах на примере алгоритма Уоршалла нахождения транзитивного замыкания ориентированного графа. На графе с 5000 вершин последовательный алгоритм Уоршалла выполнялся за 884,622 с, ассоциативная параллельная версия - за 64,454с (ускорение в 13 раз), а ассоциативная параллельная версия, адаптированная под GPU, - за 0,372с (ускорение в 2 378 раз).
  • Title Решение задач на графах с помощью STAR-машины, реализуемой на графических ускорителях
  • Headline Решение задач на графах с помощью STAR-машины, реализуемой на графических ускорителях
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 3(33)
  • Date:
  • DOI 10.17223/20710410/33/9
Ключевые слова
ассоциативный параллельный процессор, вертикальная обработка данных, SIMD, GPU, ориентированный граф, транзитивное замыкание, associative parallel processor, vertical data processing, SIMD, GPU, directed graph, adjacency matrix, transitive closure
Авторы
Ссылки
Potter J.L. Associative Computing: a Programming Paradigm for Massively Parallel Computers. Boston: Perseus Publishing, 1991. 304 p.
Rudolph J. A. A production implementation of an associative array processor - STARAN // AFIPS'72. N.Y.: ACM, 1972. P. 229-241.
Foster C. C. Content Addressable Parallel Processors. N. Y.: John Wiley & Sons, 1976. 233 p.
Higuchi T., Furuya T., Handa K., et al. IXM2: a parallel associative processor // ISCA'91. Proc. 18th Annual Intern. Symp. Computer Architecture. N. Y.: ACM, 1991. P. 22-31.
Непомнящая А. Ш., Владыко М. А. Сравнение моделей ассоциативного вычисления // Программирование. 1997. №6. С. 41-50.
Nepomniaschaya A. Sh. Language STAR for associative and parallel computation with vertical data processing // Parallel Computing Technologies. Singapore: World Scientific, 1991. P. 258-265.
Potter J., Baker J., Scott S., et al. ASC: An Associative-Computing Paradigm // Computer. 1994. No. 27(11). P. 19-25.
Nepomniaschaya A. Sh. Basic associative parallel algorithms for vertical processing systems // Bulletin of the Novosibirsk Computing Center. 2009. Ser. Comp. Science. No. 9. P. 63-77.
Nepomniaschaya A. Sh. Constructions used in associative parallel algorithms for undirected graphs. Part 1 // Bulletin of the Novosibirsk Computing Center. 2013. Ser. Comp. Science. No. 35. P. 69-83.
Nepomniaschaya A. Sh. Constructions used in associative parallel algorithms for directed graphs // LNCS. 2015. V.9251. P. 201-209.
Nepomniaschaya A. Sh. Solution of path problems using associative parallel processors // Intern. Conf. Parallel and Distributed Systems. Seoul: IEEE Computer Society Press, 1997. P. 610-617.
Nepomniaschaya A. Sh. and Dvoskina M. A. A simple implementation of Dijkstra's shortest path algorithm on associative parallel processors // Fundamenta Informaticae. IOS Press, 2000. V. 43. P. 227-243.
Nepomniaschaya A. Sh. An associative version of the Bellman - Ford algorithm for finding the shortest paths in directed graphs // LNCS. 2001. V.2127. P. 285-292.
Nepomniaschaya A. Sh. Efficient implementation of Edmonds' algorithm for finding optimum branchings on associative parallel processors // Proc. 8th Intern. Conf. Parallel and Distributed Systems (ICPADS'01). KyongJu City: IEEE Computer Society Press, 2001. P. 3-8.
Непомнящая А. Ш. Сравнение алгоритмов Прима - Дейкстры и Краскала с помощью ассоциативного параллельного процессора // Кибернетика и системный анализ. 2000. №2. С. 19-27.
Nepomniaschaya A. Sh. Representation of the Gabow algorithm for finding smallest spanning trees with a degree constraint on associative parallel processors // LNCS. 1996. V. 1123. P. 813-817.
Nepomniaschaya A. Sh. Associative parallel algorithms for dynamic edge update of minimum spanning trees // LNCS. 2003. V.2763. P. 141-150.
Nepomniaschaya A. Sh. Associative parallel algorithm for dynamic reconstructing a minimum spanning tree after deletion of a vertex // LNCS. 2005. V. 3606. P. 151-173.
Непомнящая А. Ш. Ассоциативный параллельный алгоритм для динамической обработки минимального каркаса после добавления к графу новой вершины // Кибернетика и системный анализ. 2006. №1. С. 19-31.
Nepomniaschaya A. Sh. Efficient implementation of the Italiano algorithms for updating the transitive closure on associative parallel processors // Fundamenta Informaticae. IOS Press, 2008. V. 89. No. 2-3. P. 313-329.
Nepomniaschaya A. Sh. Associative version of the Ramalingam decremental algorithm for dynamic updating the single-sink shortest paths subgraph // LNCS. 2009. V. 5698. P. 257-268.
Непомнящая А. Ш. Ассоциативная версия алгоритма Рамалингама для динамической обработки подграфа кратчайших путей после добавления к графу новой дуги // Кибернетика и системный анализ. 2012. №3. C. 45-57.
Mingxian J. Associative operations from MASC to GPU // PDPTA-15 - The 21st Intern. Conf. on Parallel and Distributed Processing Techniques and Applications. Las Vegas: CSREA Press, 2015. P. 388-393.
http://www.dis.uniroma1.it/challenge9/download.s - 9th DIMACS Implementation Challenge - Shortest Paths. 2010.
http://www.nvidia.ru/object/tesla-server-gpus-ru.html - Высокопроизводительные вычисления для серверов| Графические процессоры Tesla|NVIDIA. 2016.
Harish P. and Narayanan P. Accelerating large graph algorithms on the GPU using CUDA // LNCS. 2007. V. 4873. P. 197-208.
Katz G. J. and Kider Jr. T. All-pairs shortest-paths for large graphs on the GPU // Proc. 23rd ACM SIGGRAPH/EUROGRAPHICS Symp. Graphics Hardware. Sarajevo: Eurographics Association, 2008. P. 47-55.
Lund B. and Smith J. W. A Multi-Stage CUDA Kernel for Floyd - Warshall. arXiv preprint arXiv:1001.4108
Решение задач на графах с помощью STAR-машины, реализуемой на графических ускорителях | Прикладная дискретная математика. 2016. № 3(33). DOI: 10.17223/20710410/33/9
Решение задач на графах с помощью STAR-машины, реализуемой на графических ускорителях | Прикладная дискретная математика. 2016. № 3(33). DOI: 10.17223/20710410/33/9