Теория и практика параллельных вычислений
Сравнение алгоритмов разбиения графов
Рассмотренные алгоритмы разбиения графов различаются точностью получаемых решений, временем выполнения и возможностями для распараллеливания (под точностью понимается величина близости получаемых при помощи алгоритмов решений к оптимальным вариантам разбиения графов). Выбор наиболее подходящего алгоритма в каждом конкретном случае является достаточно сложной и неочевидной задачей. Проведению такого выбора может содействовать сведенная воедино в табл. 10.5 (см. [[67]]) общая характеристика ряда алгоритмов разделения графов, рассмотренных в данном разделе. Дополнительная информация по проблеме оптимального разбиения графов может быть получена, например, в [[67]].
| Покоординатное разбиение | Да | • | • | • • • | |
| Рекурсивный инерционный метод деления пополам | Да | • • | • | • • • | |
| Деление с учетом связности | Нет | • • | • • | • • | |
| Алгоритм Кернигана - Лина | 1 итерация | Нет | • • | • • | • |
| 10 итераций | Нет | • • • | • • • | • • | |
| 50 итераций | Нет | • • • • | • • • • | • • • • | |
Столбец "Необходимость координатной информации" отмечает использование алгоритмом координатной информации об элементах сети или вершинах графа.
Столбец "Точность" дает качественную характеристику величины приближения получаемых алгоритмом решений к оптимальным вариантам разбиения графов. Каждый дополнительный закрашенный кружок определяет примерно 10%-процентное улучшение точности приближения.
Столбец "Время выполнения" показывает относительное время, затрачиваемое различными алгоритмами разбиения. Каждый дополнительный закрашенный кружок соответствует увеличению времени разбиения примерно в 10 раз.
Столбец "Возможности для распараллеливания" характеризует свойства алгоритмов для параллельного выполнения. Алгоритм Кернигана – Лина при выполнении только одной итерации почти не поддается распараллеливанию. Этот же алгоритм при большем количестве итераций, а также метод деления с учетом связности могут быть распараллелены со средней эффективностью. Алгоритм покоординатного разбиения и рекурсивный инерционный метод деления пополам обладают высокими показателями для распараллеливания.
