Основные тенденции параллельного программирования.
Написал Michael-Jon Ainsley Hore, перевод: TuxRИсточник: http://www.opennet.ru/base/dev/mpi_intro.txt.html
Кем бы вы ни были - учёным, художником, музыкантом или кинорежиссёром - вы можете получить преимущества в скорости и стоимости сегодняшних высокопроизводительных кластеров Beowulf.
Когда в начале 90-х во время работы в НАСА Дональд Беккер представил идею кластера Beowulf, он навсегда изменил облик высокопроизводительных вычислений. Институты вместо того, чтобы вкладывать милионы долларов в последние модели суперкомпьютеров, сейчас могут потратить сотни тысяч и получить такую же производительность. Фактически, быстрый просмотр списка самых быстрых суперкомпьютеров в мире проекта TOP500 показывает, насколько большие перспективы открывают кластеры. Появление вычислительного кластера Beowulf, созданного из распространенных компонентов, на котором работала Linux, повлекло за собой неожиданный эффект - это захватило воображение компьютерщиков по всему миру, что не могли не заметить те, кто часто посещает новостной сайт Slashdot.
К сожалению, многие люди полагают, что кластеры Beowulf не применимы для выполнения их повседневных задач. Это лишь отчасти правда. Лично я не купил бы версию Quake 4, которая работала бы на кластерах Beowulf! С другой стороны, компании, такие как Pixar, используют эти компьютерные системы для рендеринга их последних фильмов. Также ученые во всем мире используют их в эту минуту, чтобы делать всё что угодно - от моделирования ядерной реакции до расшифровки человеческого генома. Хорошая новость в том, что высокопроизводительные вычисления не ограничиваются только академическими институтами и Голливудскими студиями.
Перед тем, как вы сделаете вашу программу параллельной, вам следует убедиться, что это действительно необходимо. Параллельные программы обычно пишутся, потому что данные, которые они обрабатывают слишком велики для обычных ПК или выполнение процессов (составляющих) приложение требуют большого количества времени. Стоит ли увеличение скорости выполнения программы на одну секунду работы по распараллеливанию вашего кода и управлению кластером Beowulf? Во многих случаях нет. Однако, как будет показано далее в этой статье, в некоторых ситуациях распараллеливание вашего кода может быть сделано с минимальными затратами и значительным выигрышем в производительности.
Вы можете применять одни и те же методы для обработки множества изображений, обработки аудио или любых других задач, которые легко разбиваются на части. Чтобы привести пример, как это делается для любой задачи, над которой вы работаете, я рассмотрю применение графического фильтра к весьма большому изображению нашего друга Тукса.
Типичная установка.
Первое, что нам потребуется - набор идентичных компьютеров с Linux, соединенных между собой высокоскоростной ethernet сетью. Гигабитный Ethernet будет наилучшим выбором. Скорость сетевого соединения - один из факторов, который может привести к том, что быстрый кластер будет работать очень медленно. Нам также будет нужна некоторая разделяемая файловая система и кластерное ПО/библиотеки. Большинство кластеров использует NFS, чтобы разделять жесткий диск, однако существуют более экзотические ФС, такие как IBM General Parallel File System (GPFS). Для кластерного ПО также есть несколько возможных вариантов. В настоящее время стандартом является Интерфейс Передачи Сообщений MPI (Message Passing Interface), но Параллельная Виртуальная Машина PVM (Parallel Virtual Mashine) тоже должна хорошо работать. Mosix и OpenMosix мы подробнее рассмотрим позже, но они используются преимущественно для программ, которые не были специально написаны для работы на кластерах; они работают, распределяя потоки в многопоточных программах на разные узлы. В этой статье предполагается, что у вас установлен MPI, однако процесс распараллеливания алгоритма для PVM точно такой же. Если вы еще не устанавливали MPI, Стен Бланк и Роман Заритский написали хорошую статью по установке MPI-кластера. Вы можете найти ее на веб-сайте Linux Journail (см. раздел "On-Line Ресурсы")
Инициализация программы
В начале каждой MPI программы есть несколько вызовов функций, которые инициализируют процесс коммуникации между компьютерами и вычисляют, какой "rank" какому узлу соответствует. Параметр узла "rank" - это номер, который однозначно идентифицирует его среди других компьютеров; он может принимать значения от 0 до "общий размер кластера-1". Узел 0 обычно называется главным узлом (master node) и он управляет процессом. Перед завершением программы вам необходимо сделать один дополнительный вызов для окончания процесса перед выходом. Вот, как это делается:
#include <mpi.h>
#include <stdlib.h>
int main (void) {
int myRank, clusterSize;
int imgHeight, lowerBoundY, upperBoundY,
boxSize;
// Инициализация MPI
MPI_Init((void *) 0, (void *) 0);
// Получаем номер текущего узла.
MPI_Comm_rank(MPI_COMM_WORLD, &myRank);
// Получаем общее количество узлов.
MPI_Comm_size(MPI_COMM_WORLD, &clusterSize);
// boxSize - величина изображения, которую будет обрабатывать
// каждый узел
boxSize = imgHeight / clusterSize;
// lowerBoundY - где каждый узел начинает обработку.
lowerBoundY = myRank*boxSize;
// upperBoundY - где каждый узел завершает обработку.
upperBoundY = lowerBoundY + boxSize;
// Здесь идет тело программы
// Очистка и выход:
MPI_Finalize(MPI_COMM_WORLD);
return 0;
}
Этот код работает независимо на каждой машине которая является частью
процесса, поэтому значения lowerBoundY и upperBoundY будут различными
для каждого узла. Это будет использовано в следующем разделе.Разбиение изображения
Применение к изображению фильтра может занять минуты или даже часы, в зависимости от комплексности фильтра, размера изображения и скорости компьютера. Чтобы решить эти проблемы, нам нужно распределить малые части изображения на разные компьютеры. Если у нас есть один большой файл изображения, мы можем сделать это на C/C++, как показано:
FILE *imageFile = fopen("image_in.ppm", "rb");
// Проверка, что файл существует.
if (imageFile != NULL) {
// Чтение заголовка.
fread(imageHeader, sizeof(char),
HEADER_LENGTH, imageFile);
// fseek устанавливает нас на точку изображения,
// которую будет обрабатывать данный узел.
fseek(imageFile, lowerBoundY*WIDTH*3, SEEK_SET);
// Here is where we read in the colors:
// i - текущая строка в изображении.
// j - текущий столбец.
// k - это цвет, 0 для красного, 1 для синего,
// и 2 для зелёного.
for (i=0; i<boxSize+1; i++) {
for (j=0; j<WIDTH; j++) {
for(k=0; k<3; k++) {
fread(&byte, 1, 1, imageFile);
pixelIndex = i*WIDTH+j+k;
origImage[pixelIndex] = byte;
}
}
}
}
fclose(imageFile);
Применение фильтра
Теперь, когда каждый из наших узлов хранит часть изображения для обработки, нам нужно применить фильтр. Команда Документирования GIMP выполнила большую работу по описанию, как это сделать, используя матрицу свёртки (convolution matrix) в документации GIMP. Множество эффектов изображения, как резкость, размытие, Гауссово размытие, определение контуров и усиление контуров - имеют уникальные матрицы, что производит желаемый эффект. Матрица свёртки работает, просматривая каждый пиксель изображения и изменяя его значение на основе значений соседних пикселей. В этой статье мы рассмотрим матрицу определения контуров.
Когда мы применяем фильтр к изображению, мы умножаем каждый пиксель на -4 и прибавляем значения пикселей, расположенных выше, ниже, слева и справа от данного. Это даст новое значение пикселя. Так как на углах матрицы только нули, мы можем упростить нашу программу и получить лучшую производительность, исключив эти вычисления. Ниже показано, как это делается на практике.
for (i=0; i<boxSize; i++) {
for (j=0; j<WIDTH; j++) {
if (i>0 && i<(HEIGHT-1) && j>0 && j<(WIDTH-1)){
// Сейчас мы применим матрицу фильтра
// сначала к текущему пикселю.
pixelIndex = i*WIDTH + j;
r = origImage[pixelIndex];
g = origImage[pixelIndex+1];
b = origImage[pixelIndex+2];
filter_r = -4*r;
filter_g = -4*g;
filter_b = -4*b;
// Затем к соседнему слева.
pixelIndex = i*WIDTH + j - 1;
r = origImage[pixelIndex];
g = origImage[pixelIndex+1];
b = origImage[pixelIndex+2];
filter_r += 1*r;
filter_g += 1*g;
filter_b += 1*b;
// Теперь к соседнему справа.
pixelIndex = i*WIDTH + j + 1;
r = origImage[pixelIndex];
g = origImage[pixelIndex+1];
b = origImage[pixelIndex+2];
filter_r += 1*r;
filter_g += 1*g;
filter_b += 1*b;
// Выше.
pixelIndex = (i-1)*WIDTH + j;
r = origImage[pixelIndex];
g = origImage[pixelIndex+1];
b = origImage[pixelIndex+2];
filter_r += 1*r;
filter_g += 1*g;
filter_b += 1*b;
// Ниже.
pixelIndex = (i+1)*WIDTH + j;
r = origImage[pixelIndex];
g = origImage[pixelIndex+1];
b = origImage[pixelIndex+2];
filter_r += 1*r;
filter_g += 1*g;
filter_b += 1*b;
}
// Запишем новое значение пикселя.
pixelIndex = i*WIDTH + j;
filterImage[pixelIndex] = filter_r;
filterImage[pixelIndex+1] = filter_g;
filterImage[pixelIndex+2] = filter_b;
}
}
Мы можем имитировать подпрограмму readImage() , чтобы написать функцию
writeImage() для записи изображения на диск по частям.Компиляция и выполнение вашей программы
Оба популярных дистрибутива MPI - LAM и MPICH - содержат скрипт-обёртку, чтобы позволить пользователям просто компилировать их программы с требуемыми библиотеками MPI. Эти скрипты позволяют вам задавать параметры для GCC, как вы обычно делаете:
mpicc: для программ на C
mpi++: для программ на C++ programs
mpif77: для программ на FORTRAN 77
Используйте mpirun, чтобы запустить скомпилированную программу.
Например, я скомпилировал свой код командой mpicc -O3 -o parallel
parallel.c , а затем запустил его командой mpirun n0 ./parallel.
Параметр n0 означает, что программа работает только на узле 0. Для её
выполнения на дополнительных узлах вы можете задать диапазон n0-7 (для
восьми процессоров) или использовать mpirun C для того, чтобы
программа выполнялась на всех доступных узлах.Оптимизация выполнения
Таким образом, с помощью всего нескольких простых вызовов MPI мы очень просто получили параллельный алгоритм фильтра изображений, но получилили мы выигрыш в производительности? Есть несколько способов, чтобы оптимизировать выполнение. Первое - во времени выполнения программы, а второе - во времени, насколько много работы мы можем сделать). Например, на одиночном компьютере, изображение 16,000 x 16,000 пикселей может потребовать массив из 768,000,000 элементов! Это слишком много для многих компьютеров - GCC жаловался мне, что массив слишком велик! Разбивая изображение, как мы сделали ранее, мы можем уменьшить требования к памяти для нашего приложения.
Я тестировал приведённый код на кластере Beowulf из 16 узлов с системой Fedora Core 1. Каждый узел имел 1.0 Гб ОЗУ, 3.06 ГГц процессор Pentium 4 и был соединён с другими узлами посредством Gigabit Ethernet. Узлы также имели общую сетевую файловую систему NFS.
Приведу несколько значений производительности нашей программы обработки изображений. Одной машине 3.06 ГГц требуется около 50 секунд для чтения, обработки и записи изображения 6,400 x 6,400 на диск, а 16 узлов, работающих одновременно выполняют ту же задачу примерно за 10 секунд. Даже изображение 16,000 x 16,000 пикселей, 16 узлов, работающих вместе, могут обработать быстрее, чем одна машина при обработке изображения в 6.25 раз меньше.
Основные сферы применения
В этой статье проиллюстрирован только один возможный путь, чтобы получить преимущества высокой производительности кластеров Beowulf, но та же концепция используется практически во всех параллельных программах. Обычно каждый узел считывает часть данных, выполняет некоторые операции над ними, и все узлы пересылают данные назад к главному узлу или записывают их на диск. Здесь приведены четыре примера областей, в которые, как я предполагаю, являются первыми кандидатами для распараллеливания:
Фильтры изображений: выше мы увидели, как параллельные вычисления могут чрезвычайно ускорить обработку изображений, а также дать пользователям возможность работать с очень большими изображениями. Набор плагинов для приложений, таких как The GIMP, которые могут получить преимущества кластеризации, могут быть очень полезны.
Обработка аудио: применение эффектов к аудиофайлам также занимает много времени. Открытые проекты - такие, как Audacity также ожидают разработки параллельных плагинов.
Операции с базами данных: задачи, требующие обработки большого количества записей потенциально могут получить выигрыш от параллельной обработки, если каждый узел построит запрос, который вернёт только часть нужного набора. Затем каждый узел обрабатывает данные, как обычно.
Системная безопасность: системные администраторы могут видеть насколько безопасными являются пароли их пользователей. Попытайтесь расшифровать /etc/shadow методом брутфорса, используя Beowulf, увеличив диапазон проверки на нескольких машинах. Это сэкономит ваше время и даст вам уверенность (хочется верить), что система в безопасности.
Заключительные замечания
Я надеюсь, что эта статья показала, что параллельное программирование может быть полезным для всех. Я перечислил несколько примеров, являющихся, как мне кажется, хорошими областями для применения этой концепции. Но, я уверен, есть много других областей.
Есть несколько ключевых моментов, чтобы удостовериться, что вы полностью параллелизовали любую задачу, над которой работаете. Во первых - это свести сетевые коммуникации между компьютерами к минимуму. Пересылка данных между узлами, как правило, отнимает много времени, по сравнению с тем, что происходит на одном узле. В вышеприведённом примере не было коммуникации между узлами. Однако многие задачи нуждаются в этом. Во вторых, если вы считываете данные с диска, считываете ровно столько, сколько требуется каждому узлу. Это поможет вам сохранять минимальные требования к памяти. В заключение, будьте внимательны, когда выполняете задачи, которые требуют, чтобы все узлы были синхронизированы, т.к. процесс не будет синхронизирован по-умолчанию. Некоторые машины будут работать немного быстрее, чем остальные. В конце я привел несколько необходимых функций MPI, которые вы можете использовать, включая ту, которая поможет вам синхронизировать узлы.
Я предполагаю, что в будущем компьютерные кластеры будут иметь еще более важную роль в нашей повседневной жизни. Я надеюсь, что эта статья убедила вас, что совсем просто разрабатывать приложения для таких машин, и что выигрыш в производительности, который они демонстрируют вполне достаточен для их использования в различных задачах. Я также хочу поблагодарить доктора Мохамеда Лараджи с факультета Физики Мемфисского Университета за то, что он дал мне разрешение запускать эти приложения на кластерах Beowulf его группы.
Несколько необходимых и полезных подпрограмм MPI
Существует более, чем 200 подпрограмм, которые входят в MPI, и все они полезны для различных целей. Их так много, потому что MPI работает на разнообразных системах. Здесь приведены некоторые функции, которые наиболее полезны для алгоритмов сортировки, продемонстрированных в этой статье:
MPI_Init((void*) 0, (void*) 0) - инициализирует MPI.
MPI_Comm_size(MPI_COMM_WORLD, &clstSize) - возвращает размер кластера в clstSize (integer).
MPI_Comm_rank(MPI_COMM_WORLD, &myRank) - возвращает номер (rank) узла в myRank (integer).
MPI_Barrier(MPI_COMM_WORLD) - делает паузу, пока все узлы в кластере не достигнут данной точки в коде.
MPI_Wtime() - возвращает время, прошедшее с момента некоторого неопределенного события в прошлом. Используется в процедурах подсчета времени и в других процессах.
MPI_Finalize(MPI_COMM_WORLD) - останавливает все процессы MPI. Вызывайте её перед завершением вашей программы.