Статья

Название статьи ЭКСПЕРИМЕНТАЛЬНАЯ И ТЕОРЕТИЧЕСКАЯ ОЦЕНКИ ПАРАЛЛЕЛЬНЫХ АЛГОРИТМОВ НАХОЖДЕНИЯ МИНИМАЛЬНОГО ОСТОВНОГО ДЕРЕВА НА КЛАСТЕРНЫХ СИСТЕМАХ
Автор А.А. Аль-Хулайди, Ю.О. Чернышев
Рубрика РАЗДЕЛ II. АВТОМАТИЗАЦИЯ ПРОЕКТИРОВАНИЯ
Месяц, год 07, 2011
Индекс УДК 004.032.24
DOI
Аннотация Описывается параллельный алгоритм, разработанный для нахождения минимального отстовного дерева, на основе алгоритма Борувки и Оценки вычислительной сложности предложенного параллельного алгоритма . Были произведены вычислительные эксперименты для оценки эффективности параллельного алгоритма Прима и разработанного параллельного алгоритма на основе метода Борувки. Проведена сравнительная характеристика экспериментальных и теоретических оценок параллельных алгоритмов поиска минимального остовного дерева на кластерных системах и многопроцессорной среде. Предложенные параллельные алгоритмы позволяют достигать значительной величины ускорения, в том числе и при использовании нескольких тысяч процессоров. Сравнительная характеристика экспериментальных и теоретических оценок параллельных алгоритмов нахождения минимального остовного дерева, показала достаточную эффективность разработанного параллельного алгоритма на основе метода Борувки для нахождения минимального остовного дерева. Данный алгоритм может, использован для разработки параллельной программы для кластера локальной сети, либо многопроцессорной вычислительной системы.

Скачать в PDF

Ключевые слова Метод Борувки; параллельное программирование; остовного дерева.
Библиографический список 1. Интернет-ресурс http://www.winhpc.ru/?id=138(дата обращения 12.12.2010).
2. Интернет-ресурс http://rain.ifmo.ru/cat/view.php/theory/graph-spanning-trees/mst-2005(дата обращения 10.12.2010).
3. Аль-хулайди А.А. Разработка параллельного алгоритма для нахождения минимального остовного дерева // Шестнадцатая международная открытая научная конференция "Современные проблемы информатизации" издательство.– Воронеж: ВГТУ, 2011. – № 3. – С. 1-14.

Comments are closed.