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

doi:10.17223/20710410/33/9

Эндаумент фонд ТГУ!
Впиши своё имя в историю университета
- Сделать пожертвование -

Add to "Quick Collection"

Description	Size	Format
Решение задач на графах с помощью STAR-машины, реализуемой на графических ускорителях	1 MB	Adobe Acrobat PDF	Read	Download
DOI Доступ к ресурсу на сайте издателя			10.17223/20710410/33/9

Title: Решение задач на графах с помощью STAR-машины, реализуемой на графических ускорителях
Title: Solution of graph problems by means of the STAR-machine being implemented on GPUS
Creator: Снытникова, Татьяна Валентиновна
|
Непомнящая, Анна Шмилевна
Date: 2016
DOI: 10.17223/20710410/33/9
Description: Для решения многих задач на графах построены эффективные алгоритмы на ассоциативных параллельных процессорах. Но на данный момент нет широко используемых ассоциативных архитектур. Однако с развитием графических ускорителей появилась возможность реализовывать ассоциативные параллельные модели без существенной потери эффективности вычислений, что позволяет применять ассоциативные алгоритмы на практике. Представляется реализация абстрактной модели ассоциативной параллельной обработки данных (STAR-маши-на) на графических ускорителях с помощью технологии CUDA. Измеряется производительность реализации и показывается её эффективность для решения задач на графах на примере алгоритма Уоршалла нахождения транзитивного замыкания ориентированного графа. На графе с 5000 вершин последовательный алгоритм Уоршалла выполнялся за 884,622 с, ассоциативная параллельная версия — за 64,454с (ускорение в 13 раз), а ассоциативная параллельная версия, адаптированная под GPU, — за 0,372с (ускорение в 2 378 раз).

Relationships: Show Relationship Browser for this Object
collection(s): Журналы ТГУ
Identifier: смотреть в электронном каталоге НБ ТГУ
Type: статьи в журналах
Source: Прикладная дискретная математика. 2016. № 3. С. 98-115
Language: rus

Created: 09-11-2016

780 Visitors

646 Hits

138 Downloads

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