III Международная студенческая научная конференция Студенческий научный форум - 2011

Введение

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

Два последних варианта требует изменения алгоритма программы - его распараллеливания на несколько потоков, каждый из которых может выполняться на любой машине. Долгое время программисты писали свои реализации взаимодействия потоков приложения, пока в 1994 году не появился стандарт, получивший название Message-Passing Interface. Он создавался коллективно (http://www.mpi-forum.org/), в результате получился гибкий и удобный инструмент. MPI особенно удобен тем, что он и мал, и велик. Всего в стандарте описано 125 функций, но минимальный набор составляют всего шесть, остальные нужны для эффективности или удобства. Существует несколько версий стандарта MPI.

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

Мы будем рассматривать установку и работу  реализации MPICH (MPI CHameleon), написанную для Windows авторами стандарта. Использованная нами версия MPICH разработана в соответствии со стандартом MPI 1.2. Сразу скажем, что поддержка 9x/ME минимальна: возможен запуск только нескольких потоков на одном компьютере, поэтому лучше выполнять установку на NT/2k/XP.

Установка MPICH

Для установки нам потребуется дистрибутив MPICH, который можно скачать по этой ссылке: ftp://ftp.mcs.anl.gov/pub/mpi/nt/mpich.nt.1.2.5.zip

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

После завершения установки MPICH на всех компьютерах временную папку можно удалить.

Настройка MPICH

Для того чтобы программа, написанная с использованием MPICH, могла выполняться на нескольких компьютерах, нужно чтобы на них существовал пользователь с одинаковым именем и паролем. Для удобства рекомендуется создать для этих целей отдельного пользователя. В Windows XP это можно сделать с помощью команды вида net user <;username> <;password> /add.

Для настройки MPI на главном компьютере нужно войти в меню «Пуск»-> «Программы»-> «MPICH»-> «mpd» и запустить Configuration tool. Слева при помощи кнопки Add добавляем в список те компьютеры, на которые была установлена MPICH. Также можно нажать Select и просканировать компьютеры на наличие установленного mpd или проверить его доступность.

Затем нужно поставить галочку возле Show configuration (справа вверху) и по очереди нажать на имена компьютеров в списке. Справа под именем компьютера должно появиться ´mpich 1.2.5 May 1 2003´. Если там написано что-то включающее слово error, значит, отсутствует связь со службой mpd на удаленном компьютере. Скорее всего, проблема в файрволе, и нужно произвести его настройку.

Далее в середине окна нужно выбрать настройки - необходимый минимум включает только галочку возле hosts. Для отладки бывает удобно использовать Job Host - средство, позволяющее следить за запущенными задачами и завершать их. Для его использования нужно поставить галочку около use job host, рядом нажать yes и указать имя хоста, Job Host которого нужно использовать. После завершения настроек нужно нажать Apply и OK.

Следует помнить, что MPICH позволяет распределить потоки по компьютерам в сети, на которых она  установлена, но распределение потоков по ядрам (для многоядерных процессоров) производится операционной системой.

Подключение MPICH к Delphi

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

Можно скачать такой модуль для FreePascal (http://freepascal.ru/download/zips/mpi.zip) и внести в него небольшие изменения (исправить ошибки, выдаваемые компилятором Delphi при попытке создать приложение, использующее данный модуль) или воспользоваться уже адаптированным нами для Delphi модулем, который прилагается к данному описанию.

Модуль нужно добавлять в проект стандартными средствами Delphi. Следует убедиться, что во всех модулях программы, в которых используется MPI, имеется строка вида USES MPI.

Основные функции MPI

Основные функции MPI, с помощью которых можно организовать параллельное вычисление

 

1	MPI_Init	подключение к MPI
2	MPI_Finalize	завершение работы с MPI
3	MPI_Comm_size	определение размера области взаимодействия
4	MPI_Comm_rank	определение номера процесса
5	MPI_Send	стандартная блокирующая передача
6	MPI_Recv	блокирующий прием

 

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

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

Каждый поток в MPI имеет собственный номер, называемый рангом потока. Это число используется в большинстве функций передачи сообщений. Для получения своего ранга процесс может использовать функцию MPI_Comm_rank с двумя параметрами. Первый - коммуникатор, которому принадлежит данный процесс. В терминологии MPI коммуникатором называется группа потоков. Все потоки по умолчанию принадлежат коммуникатору MPI_COMM_WORLD, и нумерация идет с нуля. Программист может создавать собственные коммуникаторы и вводить в них собственную нумерацию. Второй параметр MPI_Comm_rank - это переменная, в которую будет записан ранг процесса. Для получения общего количества процессов в коммуникаторе используется функция MPI_Comm_size с такими же параметрами.

Скелет программы MPI

Для удобства и упрощения работы, мы предлагаем использовать стандартный скелет программы MPI. В нем предполагается, что ветвь 0 главная, а остальные управляются ею. Однако можно сделать и совсем по-другому, предоставляется полная свобода. Главное - не запутаться во множестве ветвей. Вот текст этого скелета:

 

var argv:PPchar;

argc, rank, size:longint;

begin
// не передаем параметры
argv:=nil;
argc:=0;
MPI_Init(argc,argv);
MPI_Comm_rank(MPI_COMM_WORLD, rank);
MPI_Comm_size(MPI_COMM_WORLD, size);
if rank=0 then begin
// главная ветвь
end else begin
// остальные ветви
end;
MPI_Finalize();
end.

Функции обмена данными в MPI

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

Для начала рассмотрим две самые простые функции MPI_Send и MPI_Recv, выполняющие передачу по модели «один-одному» с автоматическим выбором типа блокировки. Так зачем нужны остальные, если, к примеру, схему передачи «один-всем» можно реализовать циклическим вызовом MPI_Send? Да, можно, но этот путь неэффективен: такие коллективные функции в MPI передают данные, используя реальную архитектуру кластера, то есть используют широковещательные адреса, разделяемую память и т.д.

Перечислим параметры MPI_Send по порядку: адрес буфера, в котором хранятся данные для передачи; количество данных (не размер буфера!); тип данных; ранг получателя сообщения; идентификатор сообщения; коммуникатор. Идентификатор сообщения назначается программистом и служит для удобства, так как получающий поток может фильтровать сообщения по этому полю. Тип данных нужен для их корректного преобразования, так как теоретически MPI может связывать потоки на разных платформах, имеющих разные внутренние представления данных. По этой же причине все функции приема и передачи оперируют не количеством передаваемых байт, а количеством ячеек нужного типа. MPI_Recv имеет еще один параметр, имеющий тип MPI_Status - структура, в которую помещаются свойства полученного сообщения. Кроме того, параметры «Идентификатор сообщения» и «Ранг потока» могут иметь значения MPI_ANY_TAG и MPI_ANY_SOURCE соответственно. Как нетрудно догадаться, в этих случаях функция получает пакет с любым идентификатором и от любого потока. Рекомендуется делать именно так, а потом фильтровать сообщения по параметру статуса, если, конечно, не требуется четкий порядок получения сообщений.

До этого момента речь шла только о передаче сообщений, содержащих лишь один тип. А как передать разнотипную структуру? Если все используемые компьютеры имеют одинаковую архитектуру, то можно писать что-то наподобие MPI_Send(&buf, sizeof(s), MPI_BYTE, ...). Если архитектуры компьютеров различаются, то предварительно данные должны быть упакованы - вместе с самими данными в буфер записывается информация об их типе. Это делается функцией MPI_Pack:

• MPI_Pack(add_data_p, add_count, add_type, buf_p, buf_size, buf_pos_p, comm);
• add_data_p - указатель на данные, которые нужно упаковать.
• add_count - количество ячеек памяти.
• add_type - MPI-тип этих ячеек.
• buf_p - указатель на буфер, куда упаковываются данные.
• buf_size - размер буфера.
• buf_pos_p - переменная текущей позиции в buf. Не забудьте предварительно записать туда 0! После выполнения функции значение изменяется.

• comm - коммуникатор.

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

На принимающей стороне последовательность действий такая: «подсмотреть» размер пакета, подсчитать размер буфера для распаковки, выделить память и распаковать туда пакет. Первое выполняет функция MPI_Probe. Параметры - ранг отправителя, идентификатор сообщения, коммуникатор и переменная типа MPI_Status, в которую будут записаны параметры сообщения. Стандарт MPI гарантирует, что вызов MPI_Recv, следующий за MPI_Probe и имеющий те же значения ранга, идентификатора и коммуникатора, получит именно то сообщение, параметры которого были «подсмотрены» первой функцией.

Размер буфера можно подсчитать функцией MPI_Get_count - ее параметры: переменная типа MPI_Status, которую мы использовали при вызове MPI_Probe, тип данных (в этом случае MPI_BYTE) и переменная, в которую будет записан необходимый размер буфера. Распаковка вызывается функцией MPI_Unpack, которой передаются те же параметры, что и MPI_Pack, только в другом порядке.

Коллективный обмен данными затрагивает не два процесса, а все процессы внутри коммуникатора.

Простейшими (и наиболее часто используемыми) разновидностями такого вида взаимодействия процессов являются рассылка MPI_Bcast и коллективный сбор данных MPI_Reduce.

 

function MPI_Bcast( buff : pointer;

                                   count : longint;

                                   datatype : MPI_Datatype;

                                    root : longint;

                                   comm : MPI_Comm) : longint; 

buf	- адрес первого элемента буфера передачи
count	- максимальное количество принимаемых элементов в буфере
datatype	- MPI-тип этих элементов
root	- ранг источника рассылки
comm	- коммуникатор

 

Функция MPI_Bcast реализует "широковещательную передачу". Один процесс (главный или root процесс) рассылает всем (и себе, в том числе) сообщение длины count, а остальные получают это сообщение.

 

function MPI_Reduce( buf : pointer;

                                   result : pointer;

                                   count : longint;

                                   datatype : MPI_Datatype;

                                   operation : MPI_Op;

                                   root : longint;

                                   comm : MPI_Comm) : longint;

 

buf	- адрес первого элемента буфера передачи
count	- количество элементов в буфере передачи
datatype	- MPI-тип этих элементов
operation	- операция приведения
root	- ранг главного процесса
comm	- коммуникатор

 

Функция MPI_Reduce выполняет операцию приведения над массивом данных buf, полученным от всех процессов, и пересылает результат в result одному процессу (ранг которого определен параметром root).

Как и функция MPI_Bcast, эта функция должна вызываться всеми процессами в заданном коммуникаторе, и аргументы count, datatype и operation должны совпадать.

Имеется 12 предопределенных операций приведения

MPI_MAX	максимальное значение
MPI_MIN	минимальное значение
MPI_SUM	суммарное значение
MPI_PROD	значение произведения всех элементов
MPI_LAND	логическое "и"
MPI_BAND	побитовое "и"
MPI_LOR	логическое "или"
MPI_BOR	побитовое "или"
MPI_LXOR	логическое исключающее "или"
MPI_BXOR	побитовое исключающее "или"
MPI_MAXLOC	индекс максимального элемента
MPI_MINLOC	индекс минимального элемента

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

Дополнительные функции MPI

В некоторых случаях может потребоваться узнать имя компьютера, на котором выполняется конкретный процесс. Для этой цели используется функция MPI_Get_Processor_Name с двумя параметрами. При успешном вызове этой функции переменная proc_name содержит строку с именем компьютера, а name_len - длину этой строки.

MPI_Barrier (в качестве параметра передается коммуникатор). Функция останавливает выполнение всех потоков в этом коммуникаторе до тех пор, пока ВСЕ они не подойдут к барьеру. Очень удобно для синхронизации работы потоков.

MPI_Abort используется для прекращения выполнения всех потоков в коммуникаторе. Параметры - коммуникатор и код ошибки.

MPI_Wtime.  function MPI_Wtime : double;

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

Типы данных в MPI и их соответствие типам Delphi

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

MPI_CHAR	shortint	1
MPI_SHORT	smallint	2
MPI_INT	longint	4
MPI_LONG	longint	4
MPI_UNSIGNED_CHAR	byte	1
MPI_UNSIGNED_SHORT	word	2
MPI_UNSIGNED	longword	4
MPI_UNSIGNED_LONG	longword	4
MPI_FLOAT	single	4
MPI_DOUBLE	double	8
MPI_LONG_DOUBLE	double	8
MPI_BYTE	untyped data	1
MPI_PACKED	составной тип	-

 

MPI-тип MPI_PACKED используется при передаче данных производных типов (сконструированных из базовых типов).

Запуск программ, использующих MPI

После того, как будет выполнена компиляция программы, должен появиться  исполняемый файл (*.exe). Запуск этого файла НЕ ЯВЛЯЕТСЯ запуском MPI программы.

Запуск MPI-программы осуществляется с помощью загрузчика приложения mpirun. Формат вызова таков:

>mpirun [ключи mpirun] программа [ключи программы]

Вот некоторые из опций команды mpirun:

-np x

запуск x процессов. Значение x может не совпадать с числом компьютеров в кластере (например, при использовании компьютера с многоядерным процессором) . В этом случае на некоторых машинах запустится несколько процессов. То, как они будут распределены, mpirun решит сам (зависит от установок, сделанных программой MPIConfig.exe)

-localonly x

-np x -localonly

запуск x процессов только на локальной машине

-machinefile filename

использовать файл с именами машин

-hosts n host1 host2 ... hostn

-hosts n host1 m1 host2 m2 ... hostn mn

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

-map drive: \hostshare

использовать временный диск

-dir drive:myworkingdirectory

запускать процессы в указанной директории

-env "var1=val1|var2=val2|var3=val3..."

присвоить значения переменным окружения

-logon

запросить имя пользователя и пароль

-pwdfile filename

использовать указанный файл для считывания имени пользователя и пароля. Первая строка в файле должна содержать имя пользователя, а вторая - его пароль)

-nocolor

подавить вывод от процессов различным цветом

-priority class[:level]

установить класс приоритета процессов и, опционально, уровень приоритета. class = 0,1,2,3,4 = idle, below, normal, above, high level = 0,1,2,3,4,5 = idle, lowest, below, normal, above, highest

по умолчанию используется -priority 1:3, то есть очень низкий приоритет.

Для организации параллельного вычисления на нескольких компьютерах следует:

 1. На каждом компьютере, входящем в кластер, должен существовать пользователь с одним и тем же именем и паролем, с ограниченными привилегиями.

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

3. Сохранить имя этого пользователя и его  пароль в системном реестре Windows в зашифрованном виде. Для этого предназначена программа MPIRegister.exe.

Опции таковы:

mpiregister

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

mpiregister -remove

Удаляет данные о пользователе и пароле.

mpiregister -validate

Проверяет правильность сохраненных данных.

Запускать mpiregister следует только на главном компьютере. Загрузчик приложения mpirun без опции -pwdfile будет запрашивать данные, сохраненные программой mpiregister. Если таковых не обнаружит, то запросит имя пользователя и пароль сам.

Примеры программ, использующих MPI

В папке ‘Primer1´ находится программа, выводящая номера процессов и компьютеров, на которых они запущены. Данная программа работает с любым возможным количеством процессов, если оно находится в рамках допустимого для MPI.

В папке ‘Primer2´ находится программа, демонстрирующая обмен данными между двумя процессами. Она написана с использованием всего 2ух процессов, и при ее запуске с большим количеством процессов задействованы будут только два из них, остальные процессы будут простаивать.

В папке ‘Primer3´ находится пример, идущий в комплекте с дистрибутивом MPICH, переписанный для Delphi.

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

В папке ‘Primer5´ находится программа, использующая параллельные вычисления для поиска минимального значения элемента в одномерном массиве. Программа может использовать любое возможное количество процессов, если оно находится в рамках допустимого для MPI.

В папке ‘Primer6´ находится программа, использующая параллельные вычисления для умножения двух квадратных матриц. Программа может выполняться при количестве процессов больше либо равным 2.

Задания для самостоятельной работы

Написать программу, реализующую:

• § сортировку двухмерного массива по строкам по возрастанию значений элементов.
• сортировку двухмерного массива по строкам по убыванию значений элементов.
• сортировку двухмерного массива по столбцам по убыванию значений элементов.
• сортировку двухмерного массива по столбцам по возрастанию значений элементов.
• поиск максимального значения элемента в массиве.
• поиск среднего значения элементов в массиве.

Список использованной литературы

1. Статья Распределенные вычисления на FreePascal под Windows, Илья Аввакумов
2.  http://www.citforum.ru/programming/delphi/freepascal/
3. С. Немнюгин, О. Стесик. Параллельное программирование для многопроцессорных вычислительных систем. "БХВ-Петербург" СПб, 2002.
4. В.Д. Корнеев. Параллельное программирование в MPI. "Институт компьютерных исследований" М, Ижевск, 2003.
5. Спецвыпуск журнала Хакер #065:
6. http://www.xakep.ru/magazine/xs/065/070/1.asp

Код для цитирования: Скопировать