Потоковый блочно-параллельный алгоритм поиска кратчайших путей на графе
Репозиторий БНТУ
Информация об архиве | Просмотр оригиналаПоле | Значение | |
Заглавие |
Потоковый блочно-параллельный алгоритм поиска кратчайших путей на графе
Threaded block-parallel algorithm for finding the shortest paths on graph |
|
Автор |
Карасик, О. Н.
Прихожий, А. А. |
|
Тематика |
Графы
Алгоритмы |
|
Описание |
Рассмотрена задача поиска кратчайших путей на взвешенных графах. Проанализированы варианты постановки задачи, известные алгоритмы решения, области практического применения и существующие проблемы, в частности проблема масштабируемости. Исследован класс блочно-параллельных алгоритмов, их достоинства и недостатки. Предложен быстрый потоковый блочно-параллельный алгоритм, ориентированный на графы большого размера и отличающийся изменением порядка вычислений блоков, сокращением критического пути, уменьшением времени работы на многоядерной системе, сокращением обменов данными между локальными кэш ядер и между уровнями памяти.
|
|
Дата |
2019-03-05T12:59:08Z
2019-03-05T12:59:08Z 2018 |
|
Тип |
Статья (Article)
|
|
Идентификатор |
Карасик, О. Н. Потоковый блочно-параллельный алгоритм поиска кратчайших путей на графе = Threaded block-parallel algorithm for finding the shortest paths on graph / О. Н. Карасик, А. А. Прихожий // Доклады БГУИР. – 2018. – № 2. – С. 77-84.
http://rep.bntu.by/handle/data/50343 |
|
Язык |
ru
|
|
Охват |
Минск
|
|
Издатель |
Белорусский государственный университет информатики и радиоэлектроники
|
|