Для своей задачи надо запустить на кластере: 2 версии Galois, для общей и распределённой памяти,свою реализацию из igraph, GAP, если там есть такая задача.
Эксперимент 1. Взять 5-6 "реальных" графов (Suite Sparse, SNAP или графы из папки matrices), запустить Galois для общей памяти, свою реализацию, GAP в 1, 2,4,8,16 потоков. Нарисовать графики времени работы, масштабируемости, эффективности масштабируемости.
Эксперимент 2. Взять синтетические графы одного типа, 4х разных размеров, 3 разных плотностей (например, 16,32,64). Запустить Galois для общей памяти, свою реализацию, GAP в 1, 2,4,8,16 потоков. Нарисовать графики времени работы, масштабируемости, эффективности масштабируемости.
Эксперимент 3. Взять 5-6 "реальных" графов (Suite Sparse, SNAP или графы из папки matrices), запустить Galois для распределенной памяти в 1, 2, 4, 8,16 процессов на 1, 2, 4 узлах. Для каждого числа процессов подобрать число узлов, на котором будет наименьшее время работы. Нарисовать график времени работы, масштабируемости, эффективности масштабируемости.
Эксперимент 4. Взять синтетические графы одного типа, 4х разных размеров, 3 разных плотностей (например, 16,32,64). Запустить Galois для распределенной памяти в 1 2, 4, 8, 16 процессов на 1, 2, 4 узлах. Для каждого числа процессов подобрать число узлов, на котором будет наименьшее время работы. Нарисовать графики времени работы, масштабируемости, эффективности масштабируемости.
Порядок графов: наибольший, на котором можете дождаться результатов расчетов. (Сделайте прикидочные эксперименты). В идеале - графы от 1 млн до нескольких млн вершин. Если для вашей задачи это долго ( например, betweenness centrality), то от 100 000 до 1 млн. Ориентируемся на время работы от 0,5 с до нескольких минут на запуск.
Замеры своей программыпровести на тех же графах, что и Galois. Если очень медленно работает, то взять меньшие размеры. Если возможно, сделать замеры по фазам работы алгоритма.
В отчет включить результаты всех экспериментов. Описать:
- мат постановку задачи + вставить картинку, нарисованную в igraph. Написать, какие алгоритмы использовались у вас и в стороннем софте.
- методику тестирования (характеристики графов, тестовая инфраструктура, что мерили)
- результаты экспериментов, 4 группы. Привести графики и таблицы, не забыть подписать оси
- к каждому виду экспериментов написать выводы
- общий вывод