Заседание семинара "Моделирование систем информатики" 24.05.2016 в 15-00. "Реализация алгоритма Уоршалла на графическом ускорителе", Снытникова Татьяна

Cеминар ИВМиМГ СО РАН: 
Моделирование систем информатики
Дата / Время проведения: 
Tuesday, 24 May, 2016 - 08:00
Место проведения: 
1-233
Докладчик
Ф.И.О. докладчика: 
Снытникова Татьяна
Название доклада: 
Реализация алгоритма Уоршалла на графическом ускорителе
Аннотация доклада: 

За основу параллельной версии алгоритма Уоршалла на GPU взят ассоциативный параллельный алгоритм Уоршалла (Star-алгоритм). Приводятся Star-алгоритм Уоршалла (с обходом матрицы смежности по строкам) и его модификация (с обходом по столбцам). Показывается адаптация модифицированного Star-алгоримта к архитектуре GPU.

         Производится сравнение времени работы представленных алгоритмов с временем работы других реализаций алгоритма Уоршалла на графических ускорителях. На графе с 5000 вершин относительно последовательного алгоритма Уоршалла получено ускорение в 13 раз для модифицированного