Формування та дослідження паралельних схем алгоритму Йена
Електронний архів E-archive DonNTU – (Electronic archive Donetsk National Technical University)
Переглянути архів Інформація| Поле | Співвідношення | |
| Title |
Формування та дослідження паралельних схем алгоритму Йена
FORMALIZATION OF PARALLEL SCHEMES OFYEN’S ALGORITHM ФОРМИРОВАНИЕ И ИССЛЕДОВАНИЕ ПАРАЛЛЕЛЬНЫХ СХЕМ АЛГОРИТМА ЙЕНА |
|
| Creator |
Погорілий, С.Д.
Комісарук, С.О. POGORILY, S.D. KOMISARUK, S.O. ПОГОРЕЛЫЙ, С.Д. КОМИССАРУК, С.О. |
|
| Subject |
маршрутизация
алгоритм Йена граф матрица смежности 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-технологія |
|
| 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. Виконано формалізацію алгоритму Йена пошуку k найкоротших шляхів у зваженому неорієнтованому графі з використанням математичного апарату модифікованих систем алгоритмічних алгебр В.М. Глушкова. Запропоновано концепцію розпаралелювання алгоритму для архітектур зі спільною пам’яттю, що ґрунтується на мінімізації витрат на паралельну обробку та синхронізацію даних. Проведено трансформацію схеми алгоритму та одержано паралельну схему. Виконано експериментальне порівняння швидкодії послідовної та паралельної схем з використанням кластерних обчислень. |
|
| Date |
2013-12-10T08:04:58Z
2013-12-10T08:04:58Z 2012 |
|
| Type |
Article
|
|
| Identifier |
Наукові праці Донецького національного технічного університету, серія «Інформатика, кібернетика та обчислювальна техніка»,вып. 15 (203), Донецк, ДонНТУ, 2012
УДК 004.4 http://ea.donntu.edu.ua/handle/123456789/24264 |
|
| Publisher |
Донецкий национальний технический университет
|
|