Учебное пособие саранск издательство свмо 2013 2 удк 004. 42 Ббк з97 Авторский знак о753
 Скачать 6.58 Mb.
|
|
• status – структура с дополнительной информацией. Функция копирует данные из массива sendbuffer процесса с рангом src в буфер recvbuffer процесса с рангом dest. Другая полезная функция: int MPI_Sendrecv_replace (void* buffer, int count, MPI_Datatype datatype, int dest, int sendtag, int src, int recvtag MPI_Comm comm, MPI_Status* status). Использует только один буфер, также передавая данные с процесса src на процесс dest. 2.5 Коллективные взаимодействия процессов В операциях коллективного взаимодействия процессов участвуют все процессы коммуникатора. Соответствующая процедура должна быть вызвана каждым процессом, быть может, со своим набором параметров. Возврат из процедуры коллективного взаимодействия может произойти в тот момент, когда участие процесса в данной операции уже закончено. Как и для блокирующих процедур, возврат означает то, что разрешен свободный доступ к буферу приема или посылки. Асинхронных коллективных операций в MPI нет [5]. В коллективных операциях можно использовать те же коммуникаторы, что и были использованы для операций типа точка-точка. MPI гарантирует, что сообщения, вызванные коллективными операциями, никак не повлияют на выполнение других операций и не пересекутся с 21 сообщениями, появившимися в результате индивидуального взаимодействия процессов. Нельзя рассчитывать на синхронизацию процессов с помощью коллективных операций. Если какой-то процесс уже завершил свое участие в коллективной операции, то это не означает ни того, что данная операция завершена другими процессами коммуникатора, ни того, что она ими начата. В коллективных операциях не используются идентификаторы сообщений. 2.5.1 Барьерная синхронизация В ряде ситуаций независимо выполняемые в процессах вычисления необходимо синхронизировать. Так, например, для измерения времени начала работы параллельной программы необходимо, чтобы для всех процессов одновременно были завершены все подготовительные действия, перед окончанием работы программы все процессы должны завершить свои вычисления и т.п. Синхронизация процессов, т.е. одновременное достижение процессами тех или иных точек процесса вычислений, обеспечивается при помощи функции MPI: int MPI_Barrier(MPI_Comm comm), где • comm — коммуникатор, в рамках которого выполняется операция. Функция MPI_Barrier определяет коллективную операцию, и, тем самым, при использовании она должна вызываться всеми процессами используемого коммуникатора. При вызове функции MPI_Barrier выполнение процесса блокируется, продолжение вычислений процесса произойдет только после вызова функции MPI_Barrier всеми процессами коммуникатора [2]. 2.5.2 Передача данных от одного процесса всем. Широковещательная рассылка данных При программировании параллельных задач часто возникает необходимость разослать какую-то порцию данных всем процессам сразу. Очевидно, что для решения этой задачи можно воспользоваться рассмотренными ранее операциями двупроцессного обмена. MPI_Comm_size(MPI_COMM_WORLD, &ProcNum); for (int i = 1; i < ProcNum; i++) MPI_Send(&x, n, MPI_DOUBLE, i, 0, MPI_COMM_WORLD); 22 Однако, такое решение неэффективно вследствие значительных затрат на синхронизацию процессов. Поэтому в MPI появилась специальная операция - операция широковещательной рассылки [9] int MPI_Bcast(void *buf, int count, MPI_Datatype type, int root, MPI_Comm comm), где • buf, count, type — буфер памяти с отправляемым сообщением (для процесса с рангом 0) и для приема сообщений (для всех остальных процессов); • root — ранг процесса, выполняющего рассылку данных; • comm — коммуникатор, в рамках которого выполняется передача данных. Функция MPI_Bcast осуществляет рассылку данных из буфера buf, содержащего count элементов типа type, с процесса, имеющего номер root, всем процессам, входящим в коммуникатор comm. Следует отметить: • функция MPI_Bcast определяет коллективную операцию, и, тем самым, при выполнении необходимых рассылок данных вызов функции MPI_Bcast должен быть осуществлен всеми процессами указываемого коммуникатора; • указываемый в функции MPI_Bcast буфер памяти имеет различное назначение у разных процессов: для процесса с рангом root, которым осуществляется рассылка данных, в этом буфере должно находиться рассылаемое сообщение, а для всех остальных процессов указываемый буфер предназначен для приема передаваемых данных; • все коллективные операции "несовместимы" с парными операциями — так, например, принять широковещательное сообщение, отосланное с помощью MPI_Bcast, функцией MPI_Recv нельзя, для этого можно задействовать только MPI_Bcast. Рис. 2.1. Общая схема операции передачи данных от одного процесса всем процессам 23 2.5.3 Передача данных от всех процессов одному. Операции редукции MPI предоставляет обратную по отношению к широковещательной рассылке операцию - операцию сбора данных или редукцию. Операция редукции позволяет, собрав на одном из узлов данные, посланные остальными узлами, выполнить над ними какую-либо из групповых операций - типа сложения, поиска максимума, минимума, среднего значения и т.д. [10] int MPI_Reduce(void *sendbuf, void *recvbuf, int count, MPI_Datatype type, MPI_Op op, int root, MPI_Comm comm), где • sendbuf — буфер памяти с отправляемым сообщением; • recvbuf — буфер памяти для результирующего сообщения (только для процесса с рангом root); • count — количество элементов в сообщениях; • type — тип элементов сообщений; • op — операция, которая должна быть выполнена над данными; • root — ранг процесса, на котором должен быть получен результат; • comm — коммуникатор, в рамках которого выполняется операция. В качестве операций редукции данных могут быть использованы предопределенные в MPI операции (таблица 2.2). Таблица 2.2. Базовые (предопределенные) типы операций MPI для функций редукции данных Операции Описание MPI_MAX Определение максимального значения MPI_MIN Определение минимального значения MPI_SUM Определение суммы значений MPI_PROD Определение произведения значений Элементы получаемого сообщения на процессе root представляют собой результаты обработки соответствующих элементов передаваемых процессами сообщений, т.е.: где есть операция, задаваемая при вызове функции MPI_Reduce (для пояснения на рисунке 2.3 показан пример выполнения функции редукции данных). Следует отметить: 24 • функция MPI_Reduce определяет коллективную операцию, и, тем самым, вызов функции должен быть выполнен всеми процессами указываемого коммуникатора. При этом все вызовы функции должны содержать одинаковые значения параметров count, type, op, root, comm; • передача сообщений должна быть выполнена всеми процессами, результат операции будет получен только процессом с рангом root; • выполнение операции редукции осуществляется над отдельными элементами передаваемых сообщений. Так, например, если сообщения содержат по два элемента данных и выполняется операция суммирования MPI_SUM, то результат также будет состоять из двух значений, первое из которых будет содержать сумму первых элементов всех отправленных сообщений, а второе значение будет равно сумме вторых элементов сообщений соответственно. Рис. 2.2. Общая схема операции сбора и обработки на одном процессе данных от всех процессов 2.5.4 Функции распределения и сбора данных При программировании часто возникает задача распределения массива данных по процессам некоторыми регулярными "кусками". Например, распределение матрицы, нарезанной вертикальными лентами. Возникает и обратная задача – сбор на некотором выделенном процессе некоторого набора данных, распределенного по всем процессам [7]. 25 Рис. 2.3. Распределение данных Распределение и сбор данных осуществляется с помощью вызовов процедур MPI_Scatter и MPI_Gather. int MPI_Scatter(void* sendbuf, int sentcount, MPI_Datatype senddatatype, void* recbuf, int reccount, MPI_Datatype recdatatype,int root,MPI_Comm comm), где: • sendbuf – адрес буфера для передачи данных; • sentcount – количество элементов, передаваемых на каждый процесс (общее количество элементов в буфере равно произведению sentcount на количество процессов в коммуникаторе); • senddatatype – тип передаваемых данных; • recbuf – буфер для приема данных; • reccount – размер буфера recbuf; • recdatatype – тип данных для приемки; • root – ранг процесса, с которого рассылаются данные; • comm – коммуникатор. При вызове этой процедуры произойдет следующее. Процесс с рангом root произведет передачу данных всем другим процессам в коммуникаторе. Каждому процессу будет отправлено sendcount элементов. Процесс с рангом 0 получит порцию из sendbuf, начиная с 0-го и заканчивая sendcount-1 элементом. Процесс с рангом 1 получит порцию, начиная с sendcount, заканчивая 2* sendcount-1 и т.д. Подпрограмма MPI_Gather собирает данные от остальных процессов. int MPI_Gather(void* sendbuf, int sentcount, MPI_Datatype senddatatype, void* recbuf, int reccount, MPI_Datatype recdatatype,int root,MPI_Comm comm), где: • sendbuf – адрес буфера для передачи данных; • sentcount – количество элементов, передаваемое на главный процесс; 26 • senddatatype – тип передаваемых данных; • recbuf – буфер для приема данных; • reccount – размер буфера recbuf; • recdatatype – тип данных для приемки; • root – ранг процесса, на котором собираются данные; • comm – коммуникатор. Посредством MPI_Gather каждый процесс в коммуникаторе передает данные из буфера sendbuf на процесс с рангом root. Этот "ведущий" процесс осуществляет склейку поступающих данных в буфере recbuf. Склейка данных осуществляется линейно, положение пришедшего фрагмента данных определяется рангом процесса, его приславшего. В целом процедура MPI_Gather обратна по своему действию процедуре MPI_Scatter. Следует заметить, что при использовании MPI_Gather сборка осуществляется только на одном процессе. Во всех остальных процессах заполнение буфера recbuf не определено. Для некоторых задач необходимо, чтобы данные, рассчитанные на каждом из процессов, были собраны в единый объект опять же на каждом процессе. В таком случае, вместо функции MPI_Gather следует использовать функцию MPI_Allgather. При использовании функции MPI_Allgather на всех процессах в буфере recbuf будут собраны одинаковые данные - "большой" объект, полученный как объединение фрагментов, переданных с каждого из процессов. Другая полезная процедура MPI_Alltoall пересылает данные по принципу "все - всем" Рис. 2.4. Работа MPI_Alltoall Кроме перечисленных, в MPI существует еще десяток функций, осуществляющих различные коллективные операции. При работе с ними следует помнить следующие основные моменты: 27 все коллективные операции выполняются в рамках коммуникатора. Если необходимо выполнить коллективную операцию над подмножеством процессов, следует создать для этой цели свой коммуникатор. коллективные операции должны вызываться во всех процессах, которые в них участвуют. разумное использование коллективных операций - хорошее средство повышения производительности. 2.6 Эффективность параллельных вычислений Практически сразу же после разработки первых параллельных программ возникает необходимость определения времени выполнения вычислений для оценки достигаемого ускорения процессов решения задач за счет использования параллелизма. Используемые обычно средства для измерения времени работы программ зависят, как правило, от аппаратной платформы, операционной системы, алгоритмического языка и т.п. Стандарт MPI включает определение специальных функций для измерения времени, применение которых позволяет устранить зависимость от среды выполнения параллельных программ [4,8,9]. Получение текущего момента времени обеспечивается при помощи функции: double MPI_Wtime(void), результат ее вызова есть количество секунд, прошедшее от некоторого определенного момента времени в прошлом. Этот момент времени в прошлом, от которого происходит отсчет секунд, может зависеть от среды реализации библиотеки MPI, и, тем самым, для ухода от такой зависимости функцию MPI_Wtime следует использовать только для определения длительности выполнения тех или иных фрагментов кода параллельных программ. Возможная схема применения функции MPI_Wtime может состоять в следующем: double t1, t2, dt; t1 = MPI_Wtime(); //параллельный код t2 = MPI_Wtime(); dt = t2 – t1; Для выполнения анализа эффективности необходимо иметь некоторый набор критериев для оценки параллельного алгоритма. 28 Одним из важнейших понятий при анализе параллельных алгоритмов является ускорение параллельного алгоритма. Ускорение – это отношение времени вычислений на одном процессоре ко времени вычислений на процессорах. Ускорение показывает, во сколько раз быстрее проходят вычисления в параллельном режиме по сравнению с однопроцессорным режимом. В идеальном случае ускорение на процессорах равно . В реальности ускорение обычно ниже из-за затрат времени на обмен данными и другие операции. Еще одним понятием при анализе параллельного алгоритма является эффективность. Эффективность параллельных вычислений – это отношение полученного ускорения к числу процессоров, а именно 2.7 Примеры параллельных алгоритмов и программ 2.7.1 Алгоритм суммирования ряда чисел Требуется найти сумму ряда . Последовательный алгоритм выглядит следующим образом: Шаг 1: формируется массив Шаг 2: Шаг 3: Параллельный алгоритм можно построить из соображений того, что при расчетах обычно (количество процессов) много меньше и, следовательно, на каждом процессоре можно параллельно вычислить частичные суммы, переслать их значения на один процессор, выполнить суммирование чисел и получить окончательный результат. Заметим, что параллельный алгоритм вычисления суммы ряда на практике будет выполняться медленнее, чем последовательный. Это объясняется тем, что для нахождения частичных сумм приходится осуществлять рассылку данных, причем количество выполняемых арифметических операций примерно равно числу посылаемых данных, а так как выполнение одной арифметической операции занимает меньше времени, чем пересылка одного машинного слова, то в итоге 29 реализации такого параллельного алгоритма получается проигрыш по времени по сравнению с последовательным. Следовательно, распараллеливать алгоритм суммирования имеет смысл лишь в том случае, если члены ряда формируются независимо на каждом процессоре или в процессе выполнения глобального расчета они уже распределены по процессорам [2,7]. Приведем пример программного кода суммирования числовой последовательности с помощью функций MPI_Bcast и MPI_Reduce. Программа. Параллельная программа суммирования числовых значений #include #include #include #include "mpi.h" int main(int argc, char* argv[]){ double x[100], TotalSum, ProcSum = 0.0; int ProcRank, ProcNum, N=100, k, i1, i2; MPI_Status Status; // Инициализация MPI_Init(&argc,&argv); MPI_Comm_size(MPI_COMM_WORLD,&ProcNum); MPI_Comm_rank(MPI_COMM_WORLD,&ProcRank); // Подготовка данных if ( ProcRank == 0 ) DataInitialization(x,N); // Рассылка данных на все процессы MPI_Bcast(x, N, MPI_DOUBLE, 0, MPI_COMM_WORLD); // Вычисление частичной суммы на каждом из процессов // на каждом процессе суммируются элементы вектора x от i1 до i2 k = N / ProcNum; i1 = k * ProcRank; i2 = k * ( ProcRank + 1 ); if ( ProcRank == ProcNum-1 ) i2 = N; for ( int i = i1; i < i2; i++ ) ProcSum = ProcSum + x[i]; MPI_Reduce(&ProcSum,&TotalSum,1,MPI_DOUBLE,MPI_SUM,0,MPI_CO MM_WORLD); // Вывод результата if ( ProcRank == 0 ) printf("\nTotal Sum = %10.2f",TotalSum); MPI_Finalize(); return 0;} 30 2.7.2 Алгоритм умножения матрицы на вектор Для многих методов матричных вычислений характерным является повторение одних и тех же вычислительных действий для разных элементов матриц. Данное свойство свидетельствует о наличии параллелизма по данным при выполнении матричных расчетов, и, как результат, распараллеливание матричных операций сводится в большинстве случаев к разделению обрабатываемых матриц между процессорами используемой вычислительной системы. Выбор способа разделения матриц приводит к определению конкретного метода параллельных вычислений; существование разных схем распределения данных порождает целый ряд параллельных алгоритмов матричных вычислений. Наиболее общие и широко используемые способы разделения матриц состоят в разбиении данных на полосы (по вертикали или горизонтали) или на прямоугольные фрагменты (блоки). Рис. 2.5. Варианты разбиения данных матрицы Рассмотрим подробнее вариант разбиения данных на полосы (ленточное разбиение). При ленточном (block-striped) разбиении каждому процессору выделяется то или иное подмножество строк (rowwise или горизонтальное разбиение) или столбцов (columnwise или вертикальное разбиение) матрицы. Разделение строк и столбцов на полосы в большинстве случаев происходит на непрерывной (последовательной) основе. При таком подходе для горизонтального разбиения по строкам, например, матрица представляется в виде где , есть -я строка матрицы (предполагается, что количество строк m кратно числу процессоров p, т.е. ). Здесь применяется разделение данных на непрерывной основе. Другой возможный подход к формированию полос состоит в применении той или иной схемы чередования (цикличности) строк или 31 столбцов. Как правило, для чередования используется число процессоров p – в этом случае при горизонтальном разбиении матрица принимает вид В результате умножения матрицы A размерности n m и вектора b , состоящего из n элементов, получается вектор c размера m , каждый i -й элемент которого есть результат скалярного умножения i -й строки матрицы A (обозначим эту строчку ) и вектора : Тем самым получение результирующего вектора c предполагает повторение m однотипных операций по умножению строк матрицы A и вектора b Последовательный алгоритм умножения матрицы на вектор может быть представлен следующим образом. for (i = 0; i < m; i++){ c[i] = 0; for (j = 0; j < n; j++){ c[i] += A[i][j]*b[j] }} Рассмотрим алгоритм умножения матрицы на вектор, основанный на представлении матрицы непрерывными наборами (горизонтальными полосами) строк. При таком способе разделения данных в качестве базовой подзадачи может быть выбрана операция скалярного умножения одной строки матрицы на вектор. Для выполнения базовой подзадачи скалярного произведения процессор должен содержать соответствующую строку матрицы A и копию вектора b . После завершения вычислений каждая базовая подзадача определяет один из элементов вектора результата c Для объединения результатов расчета и получения полного вектора c на каждом из процессоров вычислительной системы необходимо выполнить операцию обобщенного сбора данных, в которой каждый процессор передает свой вычисленный элемент вектора c всем остальным процессорам. В общем виде схема информационного взаимодействия подзадач в ходе выполняемых вычислений показана на рисунке 2.6. 32 Рис. 2.6. Схема взаимодействия подзадач В процессе умножения матрицы на вектор количество вычислительных операций для получения скалярного произведения одинаково для всех базовых подзадач. Поэтому в случае, когда число процессоров p меньше числа базовых подзадач m , мы можем объединить базовые подзадачи таким образом, чтобы каждый процессор выполнял несколько таких задач, соответствующих непрерывной последовательности строк матрицы A . В этом случае по окончании вычислений каждая базовая подзадача определяет набор элементов результирующего вектора c [5,10]. |