GraphMapReduce: основанная на модели программирования MapReduce структура для вычислений на графах

__Описание структуры каталогов:*

Компиляция и запуск

1. Компиляция gmr:

   • make clean && make

2. Запуск gmr

   • Одиночный запуск:

     • Команда: ./startgmr.sh [algorithm] [partition] [graphfile]
     • Поддерживаемые алгоритмы: pagerank, sssp, trianglecount
     • Примеры запуска:
       • ./startgmr.sh
       • ./startgmr.sh pagerank
       • ./startgmr.sh sssp random
       • ./startgmr.sh sssp metis 4elt
       • ./startgmr.sh pagerank metis small
     • Или прямой запуск mpirun:
       • mpirun -np 3 gmr pagerank;
       • mpirun -np 3 sssp random;
       • mpirun -np 3 trianglecount metis 4elt.

   • Запуск на кластере:

     • Команда: ./startgmr.sh cluster hosts [algorithm] [partition] [graphfile]
     • Поддерживаемые алгоритмы: pagerank, sssp, trianglecount
     • Примеры запуска:
       • ./startgmr.sh cluster hosts
       • ./startgmr.sh cluster hosts pagerank
       • ./startgmr.sh cluster hosts sssp random
       • ./startgmr.sh cluster hosts sssp metis 4elt
       • ./startgrm.sh cluster hosts pagerank metis small
     • Или прямой запуск mpirun:
       • mpirun -machinefile hosts -np 10 gmr;
       • mpirun -machinefile hosts -np 10 gmr pagerank random;
       • mpirun -machinefile hosts -np 10 gmr pagerank trianglecount metis 4elt

• Примечание:
  • Если используется метод metis для разделения графа, необходимо предварительно использовать инструмент metis для разделения файла графа. Инструмент metis находится в каталоге pathtogmr/include/metis/. Компиляция может потребоваться в зависимости от платформы.
  • Для использования метода случайного разделения графа файл графа должен содержать записи вида from_vid to_vid в каждой строке.

3. (Необязательно) Разделение графа

   • В настоящее время доступны два метода разделения графа:

     • Случайное разделение: каждый процесс MPI последовательно считывает вершины графа в соответствии с номером процесса. Разделение происходит при запуске скрипта запуска startgmr.sh.
     • Метод Metis: для сохранения связей между вершинами графа, этот метод не только уменьшает объём передачи между процессами MPI, но и сохраняет локальность генерации пар ключ-значение вершин графа, что снижает нагрузку на операции Map, Reduce и Sort. GMR также предоставляет инструмент Metis для разделения графов (требуется перекомпиляция кода Metis и последующее выполнение команды "gpmetis graphfilename partsnumber"). Также можно использовать готовые примеры графов из каталога graph/.

   • На данный момент инструмент разделения использует библиотеку Metis. Исходный код и документация находятся в include/metis/, а компиляцию можно выполнить, следуя инструкциям в include/metis/README.md.

Основа структуры

• MPI: обмен данными между вычислительными процессами осуществляется через MPI.
• Модель программирования MapReduce.
• Разделение графа:
  • Обычный формат файла графа: from_vid to_vid. При использовании этого формата необходимо выбрать метод разделения "random" при запуске программы. Каждый процесс будет параллельно и равномерно считывать соответствующую часть файла. Этот метод может привести к значительному увеличению объёма обмена информацией во время итерационного процесса вычислений.
  • Формат подграфа, созданного с помощью Metis:
    • Чтобы распределить различные части исходного графа по разным вычислительным узлам для параллельных вычислений, исходный граф необходимо разделить на несколько подграфов. Для этого используется открытый исходный код Parmetis (Parmetis). Parmetis основан на MPI и предназначен для крупномасштабного разделения графов. Для удобства и соответствия нашим алгоритмам мы переписали вывод Parmetis. Формат каждого узла вывода следующий:

Для тестирования предоставляются три различных размера графов: small, 4elt и mdual, с количеством вершин от нескольких десятков до нескольких сотен тысяч.

Процесс итерационных вычислений

1. Обмен данными:
   • Первый шаг — обход собственного подграфа graph и соседних подграфов, сбор информации о количестве байтов, которые необходимо отправить другим узлам, и запрос на выделение памяти для отправки.
   • Второй шаг — обмен информацией о количестве байтов, необходимых для приёма, с другими узлами через MPI_Alltoall(). После получения информации каждый узел вычисляет и запрашивает необходимое пространство для приёма данных.
   • Третий шаг — повторный обход собственного подграфа graph, копирование уверенности в вершинах, которые нужно отправить другим узлам, в буфер отправки char *sb.
   • Четвёртый шаг — вызов MPI_Alltoallv() для отправки данных из буфера отправки на другие узлы. 2. Вычисление 1th/2: map

Создать вершины Vertex на основе данных в буфере обмена и экземпляра графа graph, а затем применить бизнес-логику функции map для генерации списка ключей и значений (key/value list) из вершин Vertex.

3. Сортировка сгенерированного списка key/value: sort

4. Вычисление 2th/2: reduce

Применить бизнес-логику функции reduce к отсортированному списку ключей и значений для его сокращения.

5. Обновление результата вычисления reduce в графе graph

6. (Необязательно) Для совместимости с неструктурными данными MapReduce

В дополнение к локальной сортировке между Map и Reduce, фреймворк также реализует глобальную сортировку. Это позволяет поддерживать вычисления MapReduce для неструктурных данных.

Графические и неграфические вычисления MapReduce отличаются в процессе вычислений. Фреймворк поддерживает оба типа вычислений, реализуя глобальную сортировку между Map и Reduce.

Рисунок: Сравнение графических и неграфических вычислений MapReduce

Пример: PageRank

4.1.1 Простой граф с 10 вершинами разделён на три подграфа subgraphs[3]:

Рисунок: Простой граф с 10 вершинами

4.1.2 Итерационный процесс

• Каждая подгруппа отправляет свои граничные вершины своим соседям, используя MPI_Alltoall().

• Внутри каждого вычислительного узла каждая вершина <id, loc, [neighbors]> применяет функцию map, создавая несколько пар ключ-значение: {key, value1}, где key находится среди соседей, а value1 равно значению, делённому на количество соседей.

void map(Vertex &v, std::list<KV> &kvs){
    int neighbor_count = 0;
    while(v.neighbors[neighbor_count] != 0)neighbor_count++;

    float value = v.value / neighbor_count;
    for (int i = 0; i < neighbor_count; i++)
        kvs.push_back({v.neighbors[i], value});
}

• В каждом узле пары ключ-значение, созданные функцией map, сортируются по ключу.

• Функция reduce применяется к группам пар ключ-значение с одинаковыми ключами.

KV reduce(std::list<KV> &kvs) {
   float sum = 0.0;
    for (auto kv : kvs) {
        sum += kv.value;
    }

    /*Pagerank=a*(p1+p2+…Pm)+(1-a)*1/n，其中m是指向网页j的网页j数，n所有网页数*/
    sum = 0.5 * sum + (1 - 0.5) / (sizeof(vs) / sizeof(Vertex) - 1); 
    return {kvs.front().key, sum};
}

Проблемы завершения и ловушки в PageRank

Поведение пользователя в сети является примером процесса Маркова. Для обеспечения сходимости необходимо выполнение условия: граф должен быть сильно связным, то есть должна существовать возможность перехода от любой страницы к любой другой странице.

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

Предположим, мы удалим связь между C и A в исходном графе, превратив C в тупик. Получим следующий граф:

Рисунок: Граф с тупиковой страницей C

Ещё одна проблема — это «ловушки», когда некоторые страницы имеют ссылки только на себя. Например:

Рисунок: Ловушка на странице C

Пользователь, попавший на страницу C, застревает в ней, и все вероятности распределяются на эту страницу. Это делает бессмысленным ранжирование остальных страниц.

Алгоритм кратчайшего пути с одним источником SSSP (алгоритм Дейкстры)

Задача подсчёта треугольников TriangleCount

Параллельный алгоритм поиска в ширину BFS с использованием MapReduce

Двудольный граф и алгоритм распространения меток Pregel

Таблица сравнения процессоров и платформ для различных алгоритмов: