Scientific Library of Tomsk State University

   E-catalog        

Image from Google Jackets
Normal view MARC view

Ассоциативный параллельный алгоритм для динамической обработки дерева кратчайших путей после добавления новой дуги А. Ш. Непомнящая, Т. В. Снытникова

By: Непомнящая, Анна ШмилевнаContributor(s): Снытникова, Татьяна ВалентиновнаMaterial type: ArticleArticleOther title: Associative parallel algorithm for dynamic update of shortest paths tree after inserting an ARC [Parallel title]Subject(s): матрица смежности | аффектная вершина | вертикальная обработка данных | ориентированные взвешенные графы | инкрементальные алгоритмы | ассоциативные параллельные процессорыGenre/Form: статьи в журналах Online resources: Click here to access online In: Прикладная дискретная математика № 46. С. 58-71Abstract: Строится ассоциативный параллельный алгоритм для динамической обработки дерева кратчайших путей после добавления новой дуги к ориентированному взвешенному графу. Кратко описывается STAR-машина, которая моделирует работу ассоциативных (контекстно-адресуемых) параллельных систем с простейшими процессорными элементами и вертикальной обработкой информации. Описывается используемая структура данных и её свойства. Ассоциативный параллельный алгоритм представляется в виде процедуры InsertArcSPT, корректность которой доказывается. Показано, что на STAR-машине эта процедура выполняется за время O(hk), где h - число битов, которое требуется для кодирования длины максимального кратчайшего пути; к - число вершин, для которых вычисляются новые кратчайшие пути после добавления новой дуги к исходному графу. Приводятся результаты тестирования реализации алгоритма на графическом ускорителе.
Tags from this library: No tags from this library for this title. Log in to add tags.
No physical items for this record

Библиогр.: 19 назв.

Строится ассоциативный параллельный алгоритм для динамической обработки дерева кратчайших путей после добавления новой дуги к ориентированному взвешенному графу. Кратко описывается STAR-машина, которая моделирует работу ассоциативных (контекстно-адресуемых) параллельных систем с простейшими процессорными элементами и вертикальной обработкой информации. Описывается используемая структура данных и её свойства. Ассоциативный параллельный алгоритм представляется в виде процедуры InsertArcSPT, корректность которой доказывается. Показано, что на STAR-машине эта процедура выполняется за время O(hk), где h - число битов, которое требуется для кодирования длины максимального кратчайшего пути; к - число вершин, для которых вычисляются новые кратчайшие пути после добавления новой дуги к исходному графу. Приводятся результаты тестирования реализации алгоритма на графическом ускорителе.

There are no comments on this title.

to post a comment.