|
eaDonNTU, Donetsk >
Научные труды ДонНТУ >
Серія: Інформатика, кібернетика та обчислювальна техніка >
Випуск 15(203) >
Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на этот ресурс:
http://ea.donntu.ru/handle/123456789/24264
|
| Название: | Формування та дослідження паралельних схем алгоритму Йена |
| Другие названия: | FORMALIZATION OF PARALLEL SCHEMES OFYEN’S ALGORITHM
ФОРМИРОВАНИЕ И ИССЛЕДОВАНИЕ ПАРАЛЛЕЛЬНЫХ СХЕМ АЛГОРИТМА ЙЕНА |
| Авторы: | Погорілий, С.Д.
Комісарук, С.О.
POGORILY, S.D.
KOMISARUK, S.O.
ПОГОРЕЛЫЙ, С.Д.
КОМИССАРУК, С.О. |
| Ключевые слова: | маршрутизация
алгоритм Йена
граф
матрица смежности
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-технологія |
| Дата публикации: | 2012 |
| Издатель: | Донецкий национальний технический университет |
| Библиографическое описание: | Наукові праці Донецького національного технічного університету, серія «Інформатика, кібернетика та обчислювальна техніка»,вып. 15 (203), Донецк, ДонНТУ, 2012 |
| Аннотация: | Виконано формалізацію алгоритму Йена пошуку k найкоротших шляхів у зваженому
неорієнтованому графі з використанням математичного апарату модифікованих систем
алгоритмічних алгебр В.М. Глушкова. Запропоновано концепцію розпаралелювання алгоритму для архітектур зі спільною пам’яттю, що ґрунтується на мінімізації витрат на паралельну обробку
та синхронізацію даних. Проведено трансформацію схеми алгоритму та одержано паралельну схему. Виконано експериментальне порівняння швидкодії послідовної та паралельної схем з використанням кластерних обчислень. |
| Описание: | 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 |
| Располагается в коллекциях: | Випуск 15(203)
|
Все ресурсы в архиве электронных ресурсов защищены авторским правом, все права сохранены.
|
