Теория и практика параллельных вычислений

         

Сравнение алгоритмов разбиения графов


Рассмотренные алгоритмы разбиения графов различаются точностью получаемых решений, временем выполнения и возможностями для распараллеливания (под точностью понимается величина близости получаемых при помощи алгоритмов решений к оптимальным вариантам разбиения графов). Выбор наиболее подходящего алгоритма в каждом конкретном случае является достаточно сложной и неочевидной задачей. Проведению такого выбора может содействовать сведенная воедино в табл. 10.5 (см. [[67]]) общая характеристика ряда алгоритмов разделения графов, рассмотренных в данном разделе. Дополнительная информация по проблеме оптимального разбиения графов может быть получена, например, в [[67]].

Таблица 10.5. Сравнительная таблица некоторых алгоритмов разделения графов

АлгоритмыНеобходимость координатной информацииТочностьВремя выполненияВозможности для распараллеливания
Покоординатное разбиениеДа• • •
Рекурсивный инерционный метод деления пополамДа• •• • •
Деление с учетом связностиНет• •• •• •
Алгоритм Кернигана - Лина1 итерацияНет• •• •
10 итерацийНет• • •• • •• •
50 итерацийНет• • • •• • • •• • • •

Столбец "Необходимость координатной информации" отмечает использование алгоритмом координатной информации об элементах сети или вершинах графа.

Столбец "Точность" дает качественную характеристику величины приближения получаемых алгоритмом решений к оптимальным вариантам разбиения графов. Каждый дополнительный закрашенный кружок определяет примерно 10%-процентное улучшение точности приближения.

Столбец "Время выполнения" показывает относительное время, затрачиваемое различными алгоритмами разбиения. Каждый дополнительный закрашенный кружок соответствует увеличению времени разбиения примерно в 10 раз.

Столбец "Возможности для распараллеливания" характеризует свойства алгоритмов для параллельного выполнения. Алгоритм Кернигана – Лина при выполнении только одной итерации почти не поддается распараллеливанию. Этот же алгоритм при большем количестве итераций, а также метод деления с учетом связности могут быть распараллелены со средней эффективностью. Алгоритм покоординатного разбиения и рекурсивный инерционный метод деления пополам обладают высокими показателями для распараллеливания.



Содержание раздела