Рассмотрим одномерный цикл, в котором производится вычисление массива A_new по массиву A_old, где N — размер массивов, f — некоторая функция без побочных эффектов, определение которой для данного рассмотрения несущественно:
for (n = 0; n < N; n++) {
A_new[n] = f(A_old[n]);
}
Существует несколько способов распараллелить данный цикл:- неявный;
- изменение границ пробегания индекса цикла;
- преобразование массивов.
Отметим, что проблема выбора способа для описания доступа к элементам массива выходит за рамки данного обсуждения и будет рассмотрена в отдельной главе.
Рассмотрим каждый способ распараллеливания отдельно.
Неявный способДанный способ используется в системах параллельного программирования OpenMP и DVM. Он позволяет пользователю практически без изменения исходной программы получить параллельную версию программы. Например, для OpenMP параллельная версия цикла будет записана следующим образом:
#pragma omp parallel for
for (n = 0; n < N; n++) {
A_new[n] = f(A_old[n]);
}
OpenMP — система параллельного программирования на общей памяти. В ней все исполняемые потоки имеют одинаковый доступ ко всем данным, размещенным в общей памяти. Поэтому не нужно заботиться о распределении данных, а достаточно лишь разделить работу (т.е. интервалы пробегания индекса цикла) примерно поровну между потоками, что делается системой автоматически.
Система DVM предназначена для параллельного программирования на распределенной памяти. В ней тоже используются псевдокомментарии, но их будет больше: они связаны с заданием распределения массивов по узлам вычислительной системы, распределением работы между узлами, с заданием необходимых перемещений данных между узлами.
Описанный (неявный) способ распараллеливания циклов является наиболее удобным для программиста. В тоже время он является наиболее трудно реализуемым на системе с распределенной памятью (в том числе и для гибридной системы) — желательно полностью автоматизировать и распределение, и перемещение данных между узлами (а также внутри узла между памятью центрального процессора и внутренней памятью ускорителей вычислений), что не всегда возможно. Приходится предоставлять программисту необходимые «рычаги управления» распределением и перемещением данных. При малой функциональности таких рычагов далеко не всякая задача может быть эффективно решена на данном инструменте. А при большой функциональности система становится достаточно близка к универсальной библиотеке MPI, и тогда возникает вопрос о целесообразности использования такой системы, в то время как вместо нее можно применить саму библиотеку MPI, которая широко распространена и активно используется. Отсюда можно сделать вывод о целесообразности применения проблемно-ориентированных систем, которые дают возможность эффективно и продуктивно решать некоторый ограниченный класс задач, не претендуя на универсальность.
Изменение области пробегания индекса циклаДанный способ используется в системах, где есть понятие распределенный массив (распределенный по узлам вычислительной системы), в таких как Global Arrays, UPC и RefNUMA.
В таких системах массивы A_old и A_new будут распределены по узлам вычислительной системы, и каждому вычислительному узлу будет принадлежать только часть массивов. Поэтому каждый узел должен обрабатывать лишь свою часть массива:
for (n = MY_START; n < MY_STOP; n++) {
A_new[n] = f(A_old[n]);
}
Где MY_START и MY_STOP — некоторые макро-определения, которые задают границы части массива, принадлежащей данному узлу. Конкретные определения этих макро-определений различны для разных систем программирования и в рамках данного рассмотрения неважны.
Снова отметим, что способ адресации элементов массива также не является существенным для данного рассмотрения. Для простоты изложения будем считать, что обычные обращения к массиву A_new[n] работают как для своей части массива (для данного узла), так и для чужой.
Описанный способ удобен тем, что (в общем случае) необходимо изменить только параметры цикла, а внутреннюю часть цикла и остальной код можно оставить без изменения. Данный код будет работоспособен. Отметим, что для повышения эффективности программы, возможно, потребуется модификация остального кода. Плюсом является то обстоятельство, что такого рода модификацию можно проводить инкрементно, имея в каждый момент времени корректно, пусть недостаточно эффективно, работающую программу.
Данный способ, однако, неприменим для современных графических ускорителей вычислений, не обладающих виртуальной памятью, поэтому затруднительно создать без значительных накладных расходов массив, распределенный между ускорителями.
Преобразование массивовДанный способ часто используется при разработке параллельной программы с использованием параллельных библиотек программирования MPI, SHMEM и других.
Здесь смысл массивов A_old и A_new и их размера N немного другой, чем в исходной программе. В начале работы — при инициализации параллельных процессов — переменные, представляющие эти массивы, будут переопределены. В результате основной цикл останется без изменения:
for (n = 0; n < N; n++) {
A_new[n] = f(A_old[n]);
}
Массивы A_old и A_new в конкретном процессе содержат те элементы исходных массивов из последовательной программы, которые являются своими для данного процесса. И N — размер этих массивов.
Данный способ сложнее чем предыдущие — в нем программист должен изменить последовательную программу на этапе инициализации, чтобы массивы A_old и A_new инициализировались в каждом процессе по-своему.
В то же время большинство остального кода (как правило, наиболее сложного) останется без изменений. И для повышения эффективности можно использовать системы OpenMP или ускорители вычислений для каждого отдельного процесса, независимо от остальных.
Еще одно отличие данного подхода заключается в том, что он реализуется в библиотеках, а не отдельных системах программирования. Поэтому его легко сочетать с другими библиотеками — как последовательными, так и параллельными.
ЗаключениеВ настоящем проекте используется именно третий подход — преобразование массивов. Наиболее трудоемкая часть — корректная инициализация массивов в каждом процессе — в значительной степени автоматизирована в разрабатываемой библиотеке CENTAUR.
Отдельного обсуждения требует способ задания обращений к массивам. Он будет рассмотрен отдельно. |