Створення і дослідження паралельних схем алгоритму Джонсона в технології GPGPU

Створення і дослідження паралельних схем алгоритму Джонсона в технології GPGPU

Запропоновано застосування алгоритму Джонсона для знаходження найкоротших шляхів між усіма парами вершин зваженого орієнтованого графа. Виконано його формалізацію у термінах модифікованих систем алгоритмічних алгебр Глушкова. Обґрунтовано доцільність використання технології GPGPU для пришвидшення ро...

Ausführliche Beschreibung

Gespeichert in:
Bibliographische Detailangaben
Veröffentlicht in:Проблеми програмування
Datum:2016
Hauptverfasser: Погорілий, С.Д., Слинько, М.С.
Format: Artikel
Sprache:Ukrainian
Veröffentlicht: Інститут програмних систем НАН України 2016
Schlagworte:
Паралельне програмування. Розподілені системи і мережі
Online Zugang:https://nasplib.isofts.kiev.ua/handle/123456789/126395
Tags: Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:Створення і дослідження паралельних схем алгоритму Джонсона в технології GPGPU / С.Д. Погорілий, М.С. Слинько // Проблеми програмування. — 2016. — № 2-3. — С. 105-112. — Бібліогр.: 10 назв. — укр.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id nasplib_isofts_kiev_ua-123456789-126395
record_format dspace
spelling Погорілий, С.Д.
Слинько, М.С.
2017-11-23T13:02:10Z
2017-11-23T13:02:10Z
2016
Створення і дослідження паралельних схем алгоритму Джонсона в технології GPGPU / С.Д. Погорілий, М.С. Слинько // Проблеми програмування. — 2016. — № 2-3. — С. 105-112. — Бібліогр.: 10 назв. — укр.
1727-4907
https://nasplib.isofts.kiev.ua/handle/123456789/126395
004.3
Запропоновано застосування алгоритму Джонсона для знаходження найкоротших шляхів між усіма парами вершин зваженого орієнтованого графа. Виконано його формалізацію у термінах модифікованих систем алгоритмічних алгебр Глушкова. Обґрунтовано доцільність використання технології 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.
uk
Інститут програмних систем НАН України
Проблеми програмування
Паралельне програмування. Розподілені системи і мережі
Створення і дослідження паралельних схем алгоритму Джонсона в технології GPGPU
Создание и исследование параллельных схем алгоритма Джонсона в технологии GPGPU
Research and development of Johnson's algorithm parallel schemes in GPGPU technology
Article
published earlier
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
title Створення і дослідження паралельних схем алгоритму Джонсона в технології GPGPU
spellingShingle Створення і дослідження паралельних схем алгоритму Джонсона в технології GPGPU
Погорілий, С.Д.
Слинько, М.С.
Паралельне програмування. Розподілені системи і мережі
title_short Створення і дослідження паралельних схем алгоритму Джонсона в технології GPGPU
title_full Створення і дослідження паралельних схем алгоритму Джонсона в технології GPGPU
title_fullStr Створення і дослідження паралельних схем алгоритму Джонсона в технології GPGPU
title_full_unstemmed Створення і дослідження паралельних схем алгоритму Джонсона в технології GPGPU
title_sort створення і дослідження паралельних схем алгоритму джонсона в технології gpgpu
author Погорілий, С.Д.
Слинько, М.С.
author_facet Погорілий, С.Д.
Слинько, М.С.
topic Паралельне програмування. Розподілені системи і мережі
topic_facet Паралельне програмування. Розподілені системи і мережі
publishDate 2016
language Ukrainian
container_title Проблеми програмування
publisher Інститут програмних систем НАН України
format Article
title_alt Создание и исследование параллельных схем алгоритма Джонсона в технологии GPGPU
Research and development of Johnson's algorithm parallel schemes in GPGPU technology
description Запропоновано застосування алгоритму Джонсона для знаходження найкоротших шляхів між усіма парами вершин зваженого орієнтованого графа. Виконано його формалізацію у термінах модифікованих систем алгоритмічних алгебр Глушкова. Обґрунтовано доцільність використання технології 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.
issn 1727-4907
url https://nasplib.isofts.kiev.ua/handle/123456789/126395
citation_txt Створення і дослідження паралельних схем алгоритму Джонсона в технології GPGPU / С.Д. Погорілий, М.С. Слинько // Проблеми програмування. — 2016. — № 2-3. — С. 105-112. — Бібліогр.: 10 назв. — укр.
work_keys_str_mv AT pogoríliisd stvorennâídoslídžennâparalelʹnihshemalgoritmudžonsonavtehnologíígpgpu
AT slinʹkoms stvorennâídoslídžennâparalelʹnihshemalgoritmudžonsonavtehnologíígpgpu
AT pogoríliisd sozdanieiissledovanieparallelʹnyhshemalgoritmadžonsonavtehnologiigpgpu
AT slinʹkoms sozdanieiissledovanieparallelʹnyhshemalgoritmadžonsonavtehnologiigpgpu
AT pogoríliisd researchanddevelopmentofjohnsonsalgorithmparallelschemesingpgputechnology
AT slinʹkoms researchanddevelopmentofjohnsonsalgorithmparallelschemesingpgputechnology
first_indexed 2025-12-07T17:56:04Z
last_indexed 2025-12-07T17:56:04Z
_version_ 1850873127318323200

Ähnliche Einträge