Решение задач на графах с помощью STAR-машины, реализуемой на графических ускорителях

Снытникова, Татьяна Валентиновна; Непомнящая, Анна Шмилевна

Для решения многих задач на графах построены эффективные алгоритмы на ассоциативных параллельных процессорах. Но на данный момент нет широко используемых ассоциативных архитектур. Однако с развитием графических ускорителей появилась возможность реализовывать ассоциативные параллельные модели без существенной потери эффективности вычислений, что позволяет применять ассоциативные алгоритмы на практике. Представляется реализация абстрактной модели ассоциативной параллельной обработки данных (STAR-маши-на) на графических ускорителях с помощью технологии CUDA. Измеряется производительность реализации и показывается её эффективность для решения задач на графах на примере алгоритма Уоршалла нахождения транзитивного замыкания ориентированного графа. На графе с 5000 вершин последовательный алгоритм Уоршалла выполнялся за 884,622 с, ассоциативная параллельная версия — за 64,454с (ускорение в 13 раз), а ассоциативная параллельная версия, адаптированная под GPU, — за 0,372с (ускорение в 2 378 раз).

Решение задач на графах с помощью STAR-машины, реализуемой на графических ускорителях

Связанные документы (рекомендация CORE)

Новости проекта

Новости

Партнеры

Индексация