Отчёт по использованию Intel® MTL

Создать новую статью

30.06.2011 12:00


Цель: реализовать параллельный поиск клик с использованием существующего алгоритма Брона-Кербоша.

Алгоритм Брона-Кербоша


Был использован алгоритм Брона-Кербоша описанный в Combinatorial Algorithms: Theory and Practice.
Реализация этого алгоритма на языке программирования Erlang доступна тут.
Из анализа алгоритма следует, что на первом шаге алгоритма исследуется множество несвязных вершин графа,
которое порождает множество деревьев решений используемых в методе ветвей и границ.

Идея распараллеливания алгоритма заключается в том, чтобы параллельно обрабатывать несколько деревьев решений.
Исходный текст доступен тут.

Исследованные производительности

Производительность исследовалась на конфигурации: Linux, 4 процессора Intel(R) Xeon(R) CPU X7560 @ 2.27GHz, суммарное количество нитей 64.
Были сгенерированы три случайных графа, со следующими характеристиками:
№
Обозначение
Число вершин
Число ребер
Число найденных клик
1
500.20
500
24950
100 936
2
1000.10
1000
49950
98 842
3
1500.15
1500
168637
1 462 910

Графики времени выполнения


Время выполнения от числа потоков

Общее время выполнения


График увеличение производительности
Увеличение производительности



























Благодарность


Выражаю огромную благодарность за предоставленную возможность использования многоядерного сервера Intel MTL в создание выпускной квалификационной работе бакалавра.