ord_adj

group homepage English version

Проект ord_adj реализует алгоритм разбиения графа, который не только гарантирует связность полученных подобластей, но и позволяет обеспечить выполнение дополнительных ограничений. Таких как, например, гарантия неразрезания связей вершин графа, валентность которых превышает некоторый порог. Такие условия могут играть очень важную роль при построении параллельных алгоритмов в задачах добычи нефти и газа, где произвольные разрезы поперек скважин могут резко понизить эффективность параллельного кода. Сходные проблемы с выделенными структурами, которые нельзя разрезать, возникают во многих других предметных областях.

ord_rest

Пример простого автоматического разрезания области. Предложенный алгоритм очень быстрый и простой. По скорости работы он заметно обгоняет ParMetis практически на всех тестовых задачах. Однако качество разбиения у алгоритма ord_adj, как правильно, несколько хуже, чем у ParMetis. Опции выполнения ограничений при разбиении в текущей версии ParMetis отсутствует.

vka

Сравнение с пакетом ParMetis на «audikw_1»

Приведем данные, позволяющие сравнить производительность разработанной реализации алгоритма разбиения графов с известным пакетом ParMETIS. Заметим, что результаты по быстродействию, приведенные в последней работе, соответствуют параллельной реализации на суперкомпьютере BlueGene [8] с числом параллельных процессов до 1024, тогда как измерение времени для представленная в настоящем отчете программа ORD14ADJ производилось для одного вычислительного ядра настольного ПК (процессор AMD 2.2 GHz, память 2 Gbytes). Для тестирования была использована структура разреженности симметричной матрицы «audikw_1», входящей в коллекцию разреженных матриц университета Флориды [9]. Соответствующий неориентированный граф имеет n=943695 узлов и 38354076 дуг, причем число дуг, связанных с узлом, находится в пределах от 21 до 345. Число пробных разбиений в ORD14ADJ берется равным NIT=1.

Таблица 1. Сравнение результатов ORD14ADJ и ParMETIS на структуре «audikw_1»

Число блоков NBL=p	Метод разбиения	EdgeCut	Балансировка	Время счета
16	ParMETIS ORD14ADJ	1357326 2370564	0.960 0.893	10.4 0.58
32	ParMETIS ORD14ADJ	2027681 3404502	0.950 0.933	10.9 0.64
64	ParMETIS ORD14ADJ	2965230 4503672	0.950 0.940	3.13 0.68
128	ParMETIS ORD14ADJ	4162268 5960709	0.950 0.929	3.38 0.76
256	ParMETIS ORD14ADJ	5710116 7712100	0.950 0.888	1.40 0.92
512	ParMETIS ORD14ADJ	7524868 9746582	0.950 0.889	1.57 1.21
1024	ParMETIS ORD14ADJ	9745613 12207705	0.960 0.867	1.15 1.78
2048	ParMETIS ORD14ADJ	12534227 14959654	0.930 0.839	2.36 2.88

Из результатов видно, что даже для такой достаточно сложной задачи предлагаемый метод, реализованный программой ORD14ADJ, сопоставим по скорости счета и качеству разбиения с параллельной версией программы ParMETIS, являющейся современным стандартом в рассматриваемой области. При этом ORD14ADJ всегда обеспечивает связность получаемых подграфов, отвечающих блокам, в то время как известно, что ParMETIS не дает такой гарантии. Более того, достаточно длительный и разнообразный опыт использования пакетов МЕТIS и ParMETIS свидетельствует о ненадежности их работы при использовании на графах большого размера (уже начиная с нескольких миллионов узлов).