Архивы: по дате | по разделам | по авторам

Параллельный стиль

Архив

автор : Константин Михайленко 11.02.2002

Все суперкомпьютеры - товар штучный. А значит, при всех своих преимуществах "монолитный суперкомпьютер" имеет существенный недостаток: увеличение знаменателя в соотношении цена/производительность вызывает непропорционально большой рост числителя.

Все суперкомпьютеры - товар штучный. А значит, при всех своих преимуществах «монолитный суперкомпьютер» ¹ имеет существенный недостаток: увеличение знаменателя в соотношении цена/производительность вызывает непропорционально большой рост числителя.

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

POSIX-threads. POSIX ² - интерфейс для организации так называемых нитей (Pthreads). Поддерживается практически всеми Unix-системами, но не подходит для практического параллельного программирования. Реализуется на слишком низком уровне, изначально не разрабатывался для проведения параллельных вычислений и неудобен для вызова посредством Fortran-программ. Упоминание Fortran здесь не случайно. Этот язык программирования остается основным и самым удобным для написания эффективных вычислительных приложений.
OpenMP - стандарт библиотек для написания приложений, работающих на общем поле памяти (SMP, NUMA). Предусматривает реализацию распараллеливания путем использования POSIX-threads. В отличие от последнего, у OpenMP есть интерфейс как к С-, так и к Fortran-программам. Существуют открытые реализации стандарта, например OdinMP.
PVM и MPI - открытые пакеты библиотек и программ, реализующие модель передачи сообщений. Исторически сложилось так, что стандарт MPI получил более широкое распространение, и существует масса коммерческих и открытых продуктов на его основе. Из самых известных стоит упомянуть два свободно распространяемых пакета: MPICH, разработанный в Argonne National Laboratory - самый популярный в России, и LAM, созданный в Ohio Supercomputer Center и в настоящее время поддерживаемый Laboratory for Scientific Computing of the University of Notre Dame. Пакет MPICH хорошо работает на множестве различных платформ и поддерживает кластеры на базе SMP-узлов. LAM хорошо показывает себя при использовании на гетерогенных UNIX-кластерах.

Вычислительный кластер

Под термином «кластер» обычно понимается массив из отдельных машин (рабочих станций или ПК), соединенных каналом связи, предназначенный для работы параллельных приложений по модели передачи сообщений. Фактически кластер представляет собой дешевую реализацию массивно-параллельного компьютера.

Кластеры можно классифицировать как по типам узлов ³, так и по видам используемых коммуникаций.

По типам узлов кластеры можно разделить на гомогенные (в которых машины одинаковы по мощности и используемой ОС) и гетерогенные (в котором машины разные - или по производительности, или по софту). В гетерогенных кластерах (таковые обычно возникают при желании по максимуму использовать имеющийся под рукой «зоопарк» компьютеров или когда часть узлов заодно используются как рабочие станции и загружены локальными задачами) возникает дополнительная проблема балансировки загрузки узлов.

Для построения вычислительных кластеров используют самое разное сетевое оборудование - начиная с Fast Ethernet и заканчивая специализированными средствами коммуникации (см. табл. 1). Все они обычно характеризуются двумя параметрами:

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

Латентность. Это среднее время между вызовом функции передачи данных и самой передачей. Оно идет на адресацию информации, срабатывание промежуточных сетевых устройств (коммутаторов) и прочие накладные расходы.

Фактически два этих параметра не только характеризуют кластер, но и ограничивают класс задач, которые могут эффективно решаться на нем. Так, если задача требует частой передачи данных, кластер, использующий сетевое оборудование с большой латентностью (например Gigabit Ethernet), будет большую часть времени тратить даже не на передачу данных между процессами, а на установление связи, узлы же будут простаивать (недогрузка узлов кластера), и мы не получим значительного увеличения производительности.

Сетевое оборудование	Пиковая пропускная способность, Мбайт/с	Латентность, мс
Fast Ethernet	12,5	150
Gigabit Ethernet	125	150
Myrinet	160	5
SCI	400 (реально ~100)	2,3
cLAN	150	30

MPI - душа кластера

Давайте обсудим, что нам предлагает стандарт MPI (Message Passing Interface - взаимодействие через передачу сообщений). Как уже говорилось, этот стандарт оказался наиболее распространенным при написании вычислительных и иных параллельных приложений для массивно-параллельных суперкомпьютеров и кластеров. Кроме упоминавшихся свободных пакетов MPICH и LAM существуют и другие реализации. Коммерческие чаще всего делаются для Windows NT, а реализации от производителей (Hewlett-Packard, Sun, Cray, Silicon Graphics,) ориентированы на приложения для своих MPI-суперкомпьютеров. Все эти пакеты содержат одинаковый базовый набор MPI-функций, поэтому приложение, отлаженное с использованием одного из них, должно компилироваться с применением других ⁴.

К достоинствам пакета MPICH можно отнести почти абсолютную кросс-платформность. Так, в руководстве по установке перечисляется двенадцать различных программно-аппаратных платформ и вдвое больше вариантов, на которых может быть установлен MPICH. Кроме того, MPICH распространяется в исходных кодах и собирается на месте, с учетом особенностей конкретной платформы и среды коммуникации. После установки пакет работает со своими библиотеками, вызывая имеющиеся в системе компиляторы C/C++ и Fortran 77/90.

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

Думаем параллельно

Чтобы написать корректное и эффективное параллельное приложение, нужно выполнить следующие условия:

Алгоритм должен быть разбит на относительно независимые, требующие примерно одинакового времени выполнения блоки - они будут реализованы как отдельные процессы.
Параллельно работающие части алгоритма должны составлять бо’льшую по времени выполнения часть программы. При уменьшении параллельной части приложения резко снижается его эффективность.
Количество и объем передаваемых сообщений должны быть минимизированы; кроме того, допустимая частота сообщений может ограничиваться используемыми коммуникациями.

Этим условиям идеально соответствует алгоритм суммирования какого-либо ряда - практически полностью отсутствует последовательная часть приложения, то есть параллелизм приближается к 100%. Число сообщений равно удвоенному числу процессов: вначале каждому процессу рассылается информация о длине суммируемого им участка, и в конце от каждого процесса передается результат, а полученные значения складываются.

Подобный алгоритм можно использовать для написания параллельной программы нахождения определенного интеграла методом трапеций:

Распараллелить это вычисление проще простого:

то есть интеграл заменяется суммой интегралов по меньшим непересекающимся областям. Таким образом, можно сформулировать алгоритм:

Определение подынтегральной функции f(x).
Запуск параллельного приложения, определение числа процессов и их номеров.
Определение пределов интегрирования a_i, a_i+1 и частоты разбиения отрезка для каждого процесса.
Интегрирование каждым процессом функции по своему отрезку.
Пересылка каждым процессом полученного результата нулевому процессу.
Суммирование нулевым процессом полученных значений и печать результата.
Завершение параллельной части приложения и всей программы.

В листинге приводится программа на C, реализующая этот алгоритм. (Желающие могут посмотреть листинг аналогичной программы на Fortran77 на нашем сайте.)

В настоящее время идет активное кластеростроительство по всему миру, в том числе и в России. Однако кластер - не панацея. Как и любой другой суперкомпьютер, это не просто «очень быстрый ПК», а самостоятельная машина с архитектурой, значительно, а иногда радикально отличающейся от архитектуры рабочих станций и ПК, что приводит к особенностям написания эффективных приложений. Иначе говоря, переход на суперкомпьютер обычно сопровождается значительной переработкой имеющихся кодов, а многие задачи требуют полной замены используемого алгоритма, то есть фактически написания новой программы.

Впрочем, использование кластеров представляется разумным лишь при выполнении одного условия: если есть специалисты, умеющие делать эффективные параллельные приложения и понимающие алгоритмы, которые требуют высокопроизводительных вычислений. Нужны специалисты, работающие на стыке наук: информатики с математикой, механикой, физикой, генетикой. Их очень мало, однако в некоторых вузах, в частности в УГАТУ (Уфимский государственный авиационный технический университет), создаются кафедры, занимающиеся подготовкой таких специалистов.

Может быть, кто-то из сумевших дочитать эту статью до конца станет одним из создателей параллельных приложений для науки и техники?

Автор благодарит Станислава Лукащука, доцента кафедры высокопроизводительных вычислительных технологий и систем УГАТУ, за активное обсуждение статьи и, главное, за предоставленный листинг программы.

1 (обратно к тексту) - Конечно, современные суперкомпьютеры можно объединить в несколько довольно аморфных классов: это и векторные машины, и многопроцессорные, и NUMA, и разнообразные смешения этих групп. Под «монолитным суперкомпьютером» я подразумеваю машину конкретного производителя, имеющую имя и поддерживаемую данным производителем. Этим она отличается от «кластерного суперкомпьютера», обычно собираемого «на коленке».
2 (обратно к тексту) - POSIX (The Portable Operating System Interface) - стандарт интерфейса С-функций, предназначенный для облегчения переноса программных продуктов между различными операционными системами.
3 (обратно к тексту) - Под узлом понимается отдельный компьютер, входящий в состав кластера. Узлы кластера могут быть одно- или двух-, реже - четырехпроцессорными.
4 (обратно к тексту) - Конечно, идеальной совместимости не бывает. Поэтому вполне возможно использование некоторых нестандартных функций - расширений стандарта, - снижающих переносимость. Кроме того, отлаженное для одной платформы приложение может быть неэффективным на другой.
5 (обратно к тексту) - В принципе, параллельные приложения можно даже выполнять на обычном персональном компьютере, но, конечно, выигрыша в производительности в этом случае мы не получим. Скорее наоборот: будет затрачено время на старт параллельного приложения (порождение процессов) и обмен сообщениями.
#include “mpi.h”

/* определение функции */

double F (double x)

{

double c = x*x*x;

return c;

}

int main (int argc, char **argv)

{

/* объявление рабочих переменных */

double sum, s, dx, a, b, x0, x1;

int i, n;

/* объявление переменных для MPI */

int ierror, myid, numproc;

MPI_Status status;

/* инициализация параллельной части приложения */

ierror = MPI_Init (&argc, &argv);

if (ierror != 0)

{

printf (“MPI initialization error: %d”, ierror);

return;

}

/* определение числа параллельных процессов в группе */

MPI_Comm_size (MPI_COMM_WORLD, &numproc);

/* определение идентификатора процесса */

MPI_Comm_rank (MPI_COMM_WORLD, &myid);

/* определение параметров интегрирования */

a = 0.0;

b = 1.0;

n = 20;

dx = (b - a)/n/numproc;

/* вычисление интеграла */

sum = 0.0;

x0 = a + dx*n*myid;

for (i = 0; i < n; i++)

{

x1 = x0 + dx;

sum += (F(x0) + F(x1))*dx/2.0;

x0 = x1;

}

/* отправка результата всеми процессами */

if (myid > 0)

{

MPI_Send(&sum, 1, MPI_DOUBLE, 0, 000+myid,

\MPI_COMM_WORLD);

}

/* получение результатов процессом 0 и суммирование */

if (myid == 0)

{

s = sum;

for (i = 0; i < numproc-1; i++)

{

MPI_Recv(&sum, 1, MPI_DOUBLE, MPI_ANY_SOURCE,

\MPI_ANY_TAG, MPI_COMM_WORLD, &status);

s += sum;

}

printf (“%g \n”, s);

}

MPI_Finalize();

}