Отображение графовых задач на архитектуру графических ускорителей — теория и практика
Автор
А.С. Колганов
Аннотация
В последнее время все большую роль играют графические ускорители (GPU) в не графических вычислениях. Потребность их использования обусловлена их относительно высокой производительностью и более низкой стоимостью. Как известно, на GPU хорошо решаются задачи на структурных сетках, где параллелизм так или иначе легко выделяется. Но есть задачи, которые требуют больших мощностей и используют неструктурные сетки. Примерами таких задач является: Single Shortest Source Path problem (SSSP) – задача поиска кратчайших путей от заданной вершины до всех остальных во взвешенном графе, MST (minimum spanning tree) — поиск минимального остовного леса в графе, BFS (breadth first search) — поиск в ширину в графе, Community detection — обнаружение тесно связанных сообществ в графе и другие. Данные задачи очень часто используются в различных областях исследований: распознавание различных объектов, компьютерное зрение, анализ и построение сетей (например, телефонных, электрических, компьютерных, дорожных и т.д.), химия и биология и во многих других областях.
Ключевые слова
GPU, параллельная обработка графов.
Язык
Русский