Donetsk National Technical University
Please use this identifier to cite or link to this item:
https://ea.donntu.edu.ua/jspui/handle/123456789/24264| Title: | Формування та дослідження паралельних схем алгоритму Йена |
| Other Titles: | FORMALIZATION OF PARALLEL SCHEMES OFYEN’S ALGORITHM ФОРМИРОВАНИЕ И ИССЛЕДОВАНИЕ ПАРАЛЛЕЛЬНЫХ СХЕМ АЛГОРИТМА ЙЕНА |
| Authors: | Погорілий, С.Д. Комісарук, С.О. POGORILY, S.D. KOMISARUK, S.O. ПОГОРЕЛЫЙ, С.Д. КОМИССАРУК, С.О. |
| Keywords: | маршрутизация алгоритм Йена граф матрица смежности k кратчайших путей система алгоритмических алгебр САА-М схема распараллеливание, поток синхронизация контрольная точка асинхронная дизъюнкция OpenMP-технология routing Yen`s algorithm graph adjacency matrix the k shortest path systems of algorithmic algebras SAA-M scheme paralleling thread synchronization checkpoint asynchronous disjunctions OpenMP technology маршрутизація матриця суміжності k найкоротших шляхів система алгоритмічних алгебр розпаралелювання потік синхронізація контрольна точка асинхронна диз’юнкція OpenMP-технологія |
| Issue Date: | 2012 |
| Publisher: | Донецкий национальний технический университет |
| Citation: | Наукові праці Донецького національного технічного університету, серія «Інформатика, кібернетика та обчислювальна техніка»,вып. 15 (203), Донецк, ДонНТУ, 2012 |
| Abstract: | Виконано формалізацію алгоритму Йена пошуку k найкоротших шляхів у зваженому неорієнтованому графі з використанням математичного апарату модифікованих систем алгоритмічних алгебр В.М. Глушкова. Запропоновано концепцію розпаралелювання алгоритму для архітектур зі спільною пам’яттю, що ґрунтується на мінімізації витрат на паралельну обробку та синхронізацію даних. Проведено трансформацію схеми алгоритму та одержано паралельну схему. Виконано експериментальне порівняння швидкодії послідовної та паралельної схем з використанням кластерних обчислень. |
| Description: | Formalization of Yen’s algorithm for the k shortest path find in weighted undirected graph using mathematical means of V. M. Glushkov modified system of algorithmic algebras is performed. Conceptions of paralleling algorithm for architectures with shared memory, which are based on minimization of loss on parallel data proceeding and synchronization are proposed. Transformation scheme of the algorithm is performed, parallel scheme are obtained. Experimental searching performance gain for parallel and consecutive schemes was carried out by using cluster computation. |
| URI: | http://ea.donntu.edu.ua/handle/123456789/24264 |
| Appears in Collections: | Випуск 15(203) |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.