Строится ассоциативный параллельный алгоритм для динамической обработки дерева кратчайших путей после добавления новой дуги к ориентированному взвешенному графу. Кратко описывается STAR-машина, которая моделирует работу ассоциативных (контекстно-адресуемых) параллельных систем с простейшими процессорными элементами и вертикальной обработкой информации. Описывается используемая структура данных и её свойства. Ассоциативный параллельный алгоритм представляется в виде процедуры InsertArcSPT, корректность которой доказывается. Показано, что на STAR-машине эта процедура выполняется за время O(hk), где h - число битов, которое требуется для кодирования длины максимального кратчайшего пути; к - число вершин, для которых вычисляются новые кратчайшие пути после добавления новой дуги к исходному графу. Приводятся результаты тестирования реализации алгоритма на графическом ускорителе.
Скачать электронную версию публикации
Загружен, раз: 104
- Title Ассоциативный параллельный алгоритм для динамической обработки дерева кратчайших путей после добавления новой дуги
- Headline Ассоциативный параллельный алгоритм для динамической обработки дерева кратчайших путей после добавления новой дуги
- Publesher
Tomsk State University - Issue Прикладная дискретная математика 46
- Date:
- DOI 10.17223/20710410/46/5
Ключевые слова
ориентированный взвешенный граф, матрица смежности, инкрементальный алгоритм, аффектная вершина, вертикальная обработка данных, ассоциативный параллельный процессор, oriented weighted graph, adjacency matrix, incremental algorithm, affected vertex, vertical data processing, associative paral lel processorАвторы
Ссылки
Fet Y. I. Vertical processing systems: a survey // IEEE Micro. 1995. V. 15. Iss. 1. P. 65-75
Potter J. L. Associative Computing: a Programming Paradigm for Massively Parallel Computers. Boston: Perseus Publishing, 1991. 304 p
Nepomniaschaya A. Sh. Language STAR for associative and parallel computation with vertical data processing // Parallel Computing Technologies. Singapore: World Scientific, 1991. P. 258-265
Nepomniaschaya A. Sh. Basic associative parallel algorithms for vertical processing systems // Bulletin of the Novosibirsk Computing Center. 2009. Ser. Comp. Sci. No. 9. P. 63-77
Foster C. C. Content Addressable Parallel Processors. N.Y.: John Wiley & Sons, 1976. 233 p. 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. S. Solution of path problems using associative parallel processors // Proc. ICPADS'97. Seoul: IEEE Computer Society Press,1997. P. 610-617
Непомнящая А. Ш. Сравнение алгоритмов Прима - Дейкстры и Краскала с помощью ассоциативного параллельного процессора // Кибернетика и системный анализ. 2000. №2. С. 19-27
Непомнящая А. Ш. Ассоциативная версия алгоритма Рамалингама для динамической обработки подграфа кратчайших путей после добавления к графу новой дуги // Кибернетика и системный анализ. 2012. № 3. C. 45-57
Nepomniaschaya A. S. Efficient parallel implementation of the Ramalingam decremental algorithm for updating the shortest paths subgraph // Computing and Informatics. 2013. V. 32. P. 331-354
Nepomniaschaya A. S. Associative version of the Ramalingam decremental algorithm for the dynamic all-pairs shortest-path problem // Bulletin of the Novosibirsk Computing Center. 2016. Ser. Comp. Sci. No. 39. P. 37-50
Nepomniaschaya A. S. Associative version of the Ramalingam incremental algorithm for the dynamic all-pairs shortest-path problem // Bulletin of the Novosibirsk Computing Center. 2016. Ser. Comp. Sci. No. 40. P. 75-86
Непомнящая А. Ш. Ассоциативный параллельный алгоритм для динамической обработки дерева кратчайших путей // Моделирование и анализ информационных систем. 2013. Т. 20. № 2. C. 5-22
Mirenkov N. N. The Siberian approach for an open-system high-performance computing architecture // Computing and Control Engineering J. 1992. V. 3. No. 3. P. 137-142
Непомнящая А. Ш., Владыко М. А. Сравнение моделей ассоциативного вычисления // Программирование. 1997. № 6. С. 41-50
Снытникова Т. В., Непомнящая А. Ш. Решение задач на графах с помощью STAR-машины, реализуемой на графических ускорителях // Прикладная дискретная математика. 2016. № 3(33). C. 98-115
Snytnikova T. V. and Snytnikov A. V. Implementation of the STAR-machine on GPU // Bulletin of the Novosibirsk Computing Center. 2016. Ser. Comp. Sci. No. 39. P. 51-60
Снытникова Т. В. Реализация модели ассоциативных вычислений на GPU: библиотека базовых процедур языка STAR // Вычислительные методы и программирование. Новые вычислительные технологии. 2018. №19(1). C. 85-95
http://www.dislab.Org/GraphHPC-2018/contest/GraphHPC-1.0.tgz - GraphHPC-1.0. 2018
Ассоциативный параллельный алгоритм для динамической обработки дерева кратчайших путей после добавления новой дуги | Прикладная дискретная математика. 2019. № 46. DOI: 10.17223/20710410/46/5
Скачать полнотекстовую версию
Загружен, раз: 434