Ортогональная рекурсивная бисекция в часовне (алгоритм Барнса-Хата)

Question

Я реализую распределенную версию симуляции тела Барнса-Хата в часовне. Я уже реализовал последовательную и разделяемую версии памяти, которые доступны на моем GitHub.

Я следую алгоритму, изложенному здесь (глава 7):

1. Выполните ортогональную рекурсивную бисекцию и распределите тела так, чтобы каждый процесс выполнялся одинаково
2. Построить локально существенное дерево на каждом процессе
3. Вычислить силы и выдвинуть тела

У меня есть довольно хорошая идея о том, как реализовать алгоритм в C/MPI, используя MPI_Allreduce для деления пополам и простой передачи сообщений для связи между процессами (для передачи тела). А также MPI_Comm_split это очень удобная функция, которая позволяет мне разделять процессы на каждом этапе ORB.

У меня возникли проблемы с выполнением ORB с использованием параллельных / распределенных конструкций, которые предоставляет Chapel. Мне нужен какой-то способ суммирования (сокращения) работы между процессами (локали в часовне), разделения процессов на группы и межпроцессного взаимодействия для передачи тел.

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

Answer 1

После множества тупиков и сбоев мне удалось реализовать алгоритм в Chapel. Его можно найти здесь: https://github.com/novoselrok/parallel-algorithms/tree/75312981c4514b964d5efc59a45e5eb1b8bc41a6/nbody-bh/dm-chapel

Я не смог использовать большую часть модного параллельного оборудования, которое предоставляет Часовня. Я полагался только на блочные распределенные массивы с sync элементы. Я также воспроизвел модель SPMD.

В main.chpl Я настроил все необходимые массивы, которые будут использоваться для передачи данных. Каждый массив имеет соответствующий sync массив используется для синхронизации. Затем каждый работник начинается со своей доли тел и ранее упомянутых массивов. Worker.chpl содержит основную часть алгоритма

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

var localeSpace = {0..#numLocales};
var localeDomain = localeSpace dmapped Block(boundingBox=localeSpace);

var arr: [localeDomain] SomeType;
var arr$: [localeDomain] sync int; // stores the ranks of inteded receivers
var rank = here.id;

for i in 0..#numLocales-1 {
    var intendedReceiver = (rank + i + 1) % numLocales;
    var partner = ((rank - (i + 1)) + numLocales) % numLocales;

    // Wait until the previous value is read
    if (arr$[rank].isFull) {
        arr$[rank];
    }

    // Store my value
    arr[rank] = valueIWantToSend;
    arr$[rank] = intendedReceiver;

    // Am I the intended receiver?
    while (arr$[partner].readFF() != rank) {}

    // Read partner value
    var partnerValue = arr[partner];

    // Do something with partner value

    arr$[partner]; // empty

    // Reset write, which blocks until arr$[rank] is empty
    arr$[rank] = -1;
}

Это довольно сложный способ реализации каналов FIFO (см. Julia RemoteChannel, где я получил вдохновение для этого "шаблона"). Обзор:

• Сначала каждая локаль вычисляет своего предполагаемого получателя и своего партнера (откуда локаль будет читать значение)

• Локаль проверяет, было ли прочитано предыдущее значение

• Locales хранит новое значение и "блокирует" значение, устанавливая arr$[rank] с предполагаемым приемником

• Локаль ждет, пока его партнер установит значение и установит соответствующий предполагаемый получатель

• Когда локаль является предполагаемым получателем, она считывает значение партнера и выполняет с ним некоторые операции.

• Затем локаль очищает / разблокирует значение, читая arr$[partner]

• Наконец он сбрасывает его arr$[rank] написав -1, Таким образом, мы также гарантируем, что значение, установленное локалью, было прочитано предполагаемым получателем

Я понимаю, что это может быть слишком сложным решением этой проблемы. Вероятно, существует лучший алгоритм, который бы соответствовал глобальному представлению Chapels о параллельных вычислениях. Алгоритм, который я реализовал, подходит для модели вычислений SPMD.

При этом, я думаю, что Часовня все еще делает хорошую работу с точки зрения производительности. Вот показатели производительности по сравнению с Юлией и C/MPI. По мере роста числа процессов производительность значительно возрастает. У меня не было возможности запустить тест на кластере с>4 узлами, но я думаю, что Chapel получит респектабельные тесты.