Оптимизация генерации списка ребер графа в бенчмарке Graph 500 Калужин Александр, 320 гр

План Краткий обзор бенчмака Graph500 Постановка задачи Анализ предоставленного кода Предлагаемая модификация кода Реализация предложенной модификации Оценка эффективности Дальнейшая работа

Зачем еще один список? Top500, Green500 : HPL Linpack = Flop/s ориентирован Претензии к Top500: Отражает узкий класс задач Top500 стал очень важен/моден => отрасль кренит в одну сторону Другие бенчмарки: HPCC, NPB, …

Data Intensive Computing Определение – Время счета < Время доступа к данным Доступ к данным (Data Fetch) – Обращения к памяти (DRAM/Cache) – Коммуникации (интерконнект) – Доступ к дискам (СХД) – ограничены пропускной способностью и задержкой (низкая временная локальность) Графовые задачи – частный случай DataIntensive HPC

Graph500 v1.2 Benchmark 1 SEARCH 1. Генерируется случайный список ребер 2. Создается граф 3. Выполняется поиск вширь 4. Результаты поиска валидируются 5. Пункты 3 и 4 выполняются 64 раза 6. Выводятся результаты

Поиск вширь BFS

процедура BFS(Граф,источник): Создать пустую очередь Q положить источник в очередь Q отметить источник пока Q непуста: взять из очереди Q элемент и поместить в переменную v для каждого соседнего с v ребра e принадлежащего Граф пусть w другой конец ребра e если w не отмечено отметить w положить w в очередь Q

Список Graph500 #1

Постановка задачи Цель работы: при ограниченных объемах оперативной памяти достичь максимального размера генерируемого графа Задачи: Проанализировать бенчмарк graph500 Проанализировать имеющийся код Разработать модификации алгоритма Реализовать разработанные модификации Тестирование

Исходный код генератора Несколько версий (последовательный, OMP, MPI) Вершина – 64 бита. Ребро хранятся как пара вершин Алгоритм R-MAT: Алгоритм рекурсивно генерирует ребра Вход: подматрица смежности, количество ребер и инициаторы Выход: список ребер Разбивает на четыре подматрицы: Исключение – единичная подматрица или количество ребер не превосходит 1 M1 M3M4 M2

Логика генерации Инициализация псевдорандоного генератора Генерация ребер графа, R-MAT алгоритм Генерация псевдорандомной перестановки вершин Применение перестановки к списку ребер Перемешевание ребер

Предлагаемая модификация кода Перенос генерации перестановки вершин Разбить генерацию ребер на k итераций (k = 128) Инициализация псевдорандоного генератора Холостая генерация ребер графа, R-MAT алгоритм Генерация псевдорандомной перестановки вершин Инициализация псевдорандоного генератора Генерация ребер графа, R-MAT алгоритм Применение перестановки вершин к текущему списку ребер Запись текущего списка ребер на диск K раз

Реализация изменений CONST_NUMBER_OF_ITERATIONS FLAG_TO_USE_ITERATION_METHOD Полная модификация make_graph() Частичная модификация generate_kronecker() generate_kronecker_internal() Создание новых функций check_and_apply_iteration() create_filename_for_proccess() Удаление scramble_edges()

Пример кода static void check_and_apply_iteration( #ifdef GRAPHGEN_KEEP_MULTIPLICITIES generated_edge* local_edges #else int64_t* local_edges #endif) { int i; CNT_REMAIN_EDGES--; if (local_edges == NULL || USING_FEW_MEMORY || CNT_REMAIN_EDGES > 0) return; CNT_REMAIN_EDGES = CNT_EDGES_PER_ITERATION; CNT_PROCCESSED_EDGES += CNT_EDGES_PER_ITERATION; /* Copy the edge endpoints into the result array if necessary */ int64_t* result; #ifdef GRAPHGEN_KEEP_MULTIPLICITIES result = (int64_t*)xmalloc(2 * CNT_EDGES_PER_ITERATION * sizeof(int64_t)); for (i = 0; i < CNT_EDGES_PER_ITERATION; ++i) { if (local_edges[i].multiplicity != 0) { result[i * 2] = local_edges[i].src; result[i * 2 + 1] = local_edges[i].tgt ; } else { result[i * 2] = result[i * 2 + 1] = (int64_t)(-1); } #else result = local_edges; #endif /* Apply vertex permutation to part of graph.*/ apply_permutation_mpi(NULL, perm_local_size, local_vertex_perm, N, CNT_EDGES_PER_ITERATION, result); for (i = 0;i < CNT_EDGES_PER_ITERATION; ++i) fprintf(output_file, "%lld %lld\n", result[i * 2], result[i * 2 + 1]); #ifdef GRAPHGEN_KEEP_MULTIPLICITIES free(result); #endif }

Результаты Граф полностью совпадает с первоначальным Использование оперативной памяти уменьшено в 5 раза => scale увеличен на 2 Среднее время работы возросло в 1.4 раз

График зависимости времени выполнения генерации ребер max scale графа от количества узлов для модифицированного алгоритма

График зависимости времени выполнения генерации ребер max scale графа от количества узлов для исходного алгоритма

Дальнейшая работа Запуск на полной мощности Ломоносова Объединение результатов с остальными частями бенчмарка Дальнейшая оптимизация генерации списка ребер Оптимизация и совершенствование других частей бенчмарка

Спасибо за внимание, Вопросы?