Створення і дослідження паралельних схем алгоритму Джонсона в технології GPGPU
Запропоновано застосування алгоритму Джонсона для знаходження найкоротших шляхів між усіма парами вершин зваженого орієнтованого графа. Виконано його формалізацію у термінах модифікованих систем алгоритмічних алгебр Глушкова. Обґрунтовано доцільність використання технології GPGPU для пришвидшення ро...
Збережено в:
| Дата: | 2016 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | Ukrainian |
| Опубліковано: |
Інститут програмних систем НАН України
2016
|
| Назва видання: | Проблеми програмування |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/126395 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Створення і дослідження паралельних схем алгоритму Джонсона в технології GPGPU / С.Д. Погорілий, М.С. Слинько // Проблеми програмування. — 2016. — № 2-3. — С. 105-112. — Бібліогр.: 10 назв. — укр. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-126395 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1263952017-11-24T03:02:43Z Створення і дослідження паралельних схем алгоритму Джонсона в технології GPGPU Погорілий, С.Д. Слинько, М.С. Паралельне програмування. Розподілені системи і мережі Запропоновано застосування алгоритму Джонсона для знаходження найкоротших шляхів між усіма парами вершин зваженого орієнтованого графа. Виконано його формалізацію у термінах модифікованих систем алгоритмічних алгебр Глушкова. Обґрунтовано доцільність використання технології GPGPU для пришвидшення роботи алгоритму. Отримано низку схем паралельної версії алгоритму, оптимізовану для використання в технології GPGPU. Запропоновано підходи до реалізації отриманих схем з використанням архітектури обчислень NVIDIA CUDA. Виконано експериментальне дослідження підвищення продуктивності при проведенні обчислень на відеоадаптері. Предложено применение алгоритма Джонсона для нахождения кратчайших путей между всеми парами вершин взвешенного ориентированного графа. Выполнена его формализация в терминах модифицированных систем алгоритмических алгебр Глушкова. Обоснована целесообразность использования технологии GPGPU для ускорения работы алгоритма. Получен ряд схем параллельной версии алгоритма, оптимизированной под использование в технологии GPGPU. Предложено подходы к реализации полученных схем с использованием архитектуры вычислений NVIDIA CUDA. Выполнено экспериментальное исследование повышения производительности при проведении вычислений на видеоадаптере. Johnson’s all pairs shortest path algorithm application in an edge weighted, directed graph is considered. Its formalization in terms of Glushkov’s modified systems of algorithmic algebras was made. The expediency of using GPGPU technology to accelerate the algorithm is proved. A number of schemas of parallel algorithm optimized for using in GPGPU were obtained. Suggested approach to the implementation of the schemes obtained using computing architecture NVIDIA CUDA. An experimental study of improved performance by using GPU for computations was made. 2016 Article Створення і дослідження паралельних схем алгоритму Джонсона в технології GPGPU / С.Д. Погорілий, М.С. Слинько // Проблеми програмування. — 2016. — № 2-3. — С. 105-112. — Бібліогр.: 10 назв. — укр. 1727-4907 http://dspace.nbuv.gov.ua/handle/123456789/126395 004.3 uk Проблеми програмування Інститут програмних систем НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Ukrainian |
| topic |
Паралельне програмування. Розподілені системи і мережі Паралельне програмування. Розподілені системи і мережі |
| spellingShingle |
Паралельне програмування. Розподілені системи і мережі Паралельне програмування. Розподілені системи і мережі Погорілий, С.Д. Слинько, М.С. Створення і дослідження паралельних схем алгоритму Джонсона в технології GPGPU Проблеми програмування |
| description |
Запропоновано застосування алгоритму Джонсона для знаходження найкоротших шляхів між усіма парами вершин зваженого орієнтованого графа. Виконано його формалізацію у термінах модифікованих систем алгоритмічних алгебр Глушкова. Обґрунтовано доцільність використання технології GPGPU для пришвидшення роботи алгоритму. Отримано низку схем паралельної версії алгоритму, оптимізовану для використання в технології GPGPU. Запропоновано підходи до реалізації отриманих схем з використанням архітектури обчислень NVIDIA CUDA. Виконано експериментальне дослідження підвищення продуктивності при проведенні обчислень на відеоадаптері. |
| format |
Article |
| author |
Погорілий, С.Д. Слинько, М.С. |
| author_facet |
Погорілий, С.Д. Слинько, М.С. |
| author_sort |
Погорілий, С.Д. |
| title |
Створення і дослідження паралельних схем алгоритму Джонсона в технології GPGPU |
| title_short |
Створення і дослідження паралельних схем алгоритму Джонсона в технології GPGPU |
| title_full |
Створення і дослідження паралельних схем алгоритму Джонсона в технології GPGPU |
| title_fullStr |
Створення і дослідження паралельних схем алгоритму Джонсона в технології GPGPU |
| title_full_unstemmed |
Створення і дослідження паралельних схем алгоритму Джонсона в технології GPGPU |
| title_sort |
створення і дослідження паралельних схем алгоритму джонсона в технології gpgpu |
| publisher |
Інститут програмних систем НАН України |
| publishDate |
2016 |
| topic_facet |
Паралельне програмування. Розподілені системи і мережі |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/126395 |
| citation_txt |
Створення і дослідження паралельних схем алгоритму Джонсона в технології GPGPU / С.Д. Погорілий, М.С. Слинько // Проблеми програмування. — 2016. — № 2-3. — С. 105-112. — Бібліогр.: 10 назв. — укр. |
| series |
Проблеми програмування |
| work_keys_str_mv |
AT pogorílijsd stvorennâídoslídžennâparalelʹnihshemalgoritmudžonsonavtehnologíígpgpu AT slinʹkoms stvorennâídoslídžennâparalelʹnihshemalgoritmudžonsonavtehnologíígpgpu |
| first_indexed |
2023-10-18T20:50:43Z |
| last_indexed |
2023-10-18T20:50:43Z |
| _version_ |
1796151257182765056 |