Детальная информация

Название: Разработка параллельного приближенного алгоритма поиска дерева Штейнера на GPU: выпускная квалификационная работа магистра: направление 01.04.02 «Прикладная математика и информатика» ; образовательная программа 01.04.02_02 «Математические методы анализа и визуализации данных»
Авторы: Чернова Вероника Сергеевна
Научный руководитель: Пастор Алексей Владимирович
Другие авторы: Арефьева Людмила Анатольевна; Чуканов Вячеслав Сергеевич
Организация: Санкт-Петербургский политехнический университет Петра Великого. Институт прикладной математики и механики
Выходные сведения: Санкт-Петербург, 2021
Коллекция: Выпускные квалификационные работы; Общая коллекция
Тематика: Алгоритмы; Маршрутизаторы; дерево Штейнера; Steiner tree
УДК: 004.421; 510.5; 004.715
Тип документа: Выпускная квалификационная работа магистра
Тип файла: PDF
Язык: Русский
Код специальности ФГОС: 01.04.02
Группа специальностей ФГОС: 010000 - Математика и механика
Ссылки: Отзыв руководителя; Рецензия; Отчет о проверке на объем и корректность внешних заимствований
DOI: 10.18720/SPBPU/3/2021/vr/vr21-3865
Права доступа: Доступ по паролю из сети Интернет (чтение, печать, копирование)
Дополнительно: Новинка

Разрешенные действия:

Действие 'Прочитать' будет доступно, если вы выполните вход в систему или будете работать с сайтом на компьютере в другой сети Действие 'Загрузить' будет доступно, если вы выполните вход в систему или будете работать с сайтом на компьютере в другой сети

Группа: Анонимные пользователи

Сеть: Интернет

Аннотация

Данная работа посвящена реализации на GPU и оптимизации одного из алгоритмов поиска дерева Штейнера, а именно алгоритма KMB. Алгоритм KMB существует в двух вариантах, первый (оригинальный) предназначен для работы на неориентированных графах, а второй - на ориентированных. Неориентированный KMB имеет вычислительную сложность O(|V|^2+|E|) с учетом существующей оптимизации, а ориентированный - O(|T||V|^2). В данной работе неориентированный KMB был эффективно распараллелен и реализован на GPU, а для его ориентированного варианта была разработана оптимизация, снижающая его вычислительную сложность до O(|V|^2+|E|). В данной работе представлена оценка производительности трех реализованных программ: неориентированного KMB, ориентированного KMB и неориентированного KMB на GPU. Результаты показали, что программа на GPU начинает выигрывать в производительности на графах с 60 000 ребрами и более. Также, было произведено сравнение практических точностей неориентированного и ориентированного алгоритмов KMB. При сравнении на графах от 50 до 2500 вершин оказалось, что в среднем их точности примерно равны. Среднее отличие приближенного дерева Штейнера от оптимального решения для неориентированного KMB составило 10,2%, а для ориентированного KMB – 10,1%.

This work dedicated to the development of GPU-based KMB algorithm that finds an approximate Steiner tree on undirected graphs. Moreover, this work proposes an optimization for directed version of KMB algorithm. Undirected KMB have time complexity of O(|V|^2+|E|) with optimization, while directed KMB have time complexity of O(|T||V|^2). The optimization that is proposed in this work make time complexity for directed KMB of O(|V|^2+|E|). This paper presents an assessment of the performance of three implemented programs: undirected KMB, directed KMB and undirected GPU-based KMB. Experiments have shown that GPU-based KMB have better performance than other two programs on graphs with 60 000 edges and more. Moreover, in this work was produced a comparison of accuracy for directed and undirected KMB by experiments. Experiments was conducted on graphs with number of vertices from 50 to 2500. It shown that accuracy of directed and undirected KMB approximately equal. Average difference of given solution from optimal solution for undirected KMB is 10,2%, and for directed KMB is 10,1%.

Права на использование объекта хранения

Место доступа Группа пользователей Действие
Локальная сеть ИБК СПбПУ Все Прочитать Печать Загрузить
Интернет Авторизованные пользователи СПбПУ Прочитать Печать Загрузить
Интернет Авторизованные пользователи (не СПбПУ)
-> Интернет Анонимные пользователи

Статистика использования

stat Количество обращений: 3
За последние 30 дней: 0
Подробная статистика