На этом шаге мы рассмотрим организацию обмена данными между процессорами.
Параллельный вариант метода сеток при ленточном разделении данных состоит в обработке полос на всех имеющихся процессорах одновременно в соответствии со следующей схемой работы:
// действия, выполняемые на каждом процессоре do { // <обмен граничных строк полос с соседями> // <обработка полосы> // <вычисление общей погрешности вычислений dmax>} while ( dmax > eps ); // eps - точность решения
Для конкретизации представленных в алгоритме действий введем обозначения:
- ProcNum - номер процессора, на котором выполняются описываемые действия,
- PrevProc, NextProc - номера соседних процессоров, содержащих предшествующую и следующую полосы,
- NP - количество процессоров,
- M - количество строк в полосе (без учета продублированных граничных строк),
- N - количество внутренних узлов в строке сетки (т.е. всего в строке N+2 узла).
Для нумерации строк полосы будем использовать нумерацию, при которой строки 0 и M+1 есть продублированные из соседних полос граничные строки, а строки собственной полосы процессора имеют номера от 1 до M.
Процедура обмена граничных строк между соседними процессорами может быть разделена на две последовательные операции, во время первой из которых каждый процессор передает свою нижнюю граничную строку следующему процессору и принимает такую же строку от предыдущего процессора. Вторая часть передачи строк выполняется в обратном направлении: процессоры передают свои верхние граничные строки своим предыдущим соседям и принимают переданные строки от следующих процессоров.
Выполнение подобных операций передачи данных в общем виде может быть представлено следующим образом (для краткости рассмотрим только первую часть процедуры обмена):
// передача нижней граничной строки следующему // процессору и прием передаваемой строки от // предыдущего процессора if ( ProcNum != NP-1 ) Send(u[M][*],N+2,NextProc); if ( ProcNum != 0 ) Receive(u[0][*],N+2,PrevProc);
(для записи процедур приема-передачи используется близкий к стандарту MPI формат, где первый и второй параметры представляют пересылаемые данные и их объем, а третий параметр определяет адресат (для операции Send) или источник (для операции Receive) пересылки данных). Для организации пересылки данных во всех последующих примерах будут использоваться операции приема-передачи блокирующего типа.
Приведенная выше последовательность блокирующих операций приема-передачи данных (вначале Send, затем Receive) приводит к строго последовательной схеме выполнения процесса пересылок строк, т.к. все процессоры одновременно обращаются к операции Send и переходят в режим ожидания. Первым процессором, который окажется готовым к приему пересылаемых данных, окажется сервер с номером NP-1. В результате процессор NP-2 выполнит операцию передачи своей граничной строки и перейдет к приему строки от процессора NP-3 и т.д. Общее количество повторений таких операций равно NP-1.
Аналогично происходит выполнение и второй части процедуры пересылки граничных строк перед началом обработки строк.
Последовательный характер рассмотренных операций пересылок данных определяется выбранным способом очередности выполнения. Изменим этот порядок очередности при помощи чередования приема и передачи для процессоров с четными и нечетными номерами:
// передача нижней граничной строки следующему // процессору и прием передаваемой строки от // предыдущего процессора if ( ProcNum % 2 == 1 ) { // нечетный процессор if ( ProcNum != NP-1 ) Send(u[M][*],N+2,NextProc); if ( ProcNum != 0 ) Receive(u[0][*],N+2,PrevProc); } else { // процессор с четным номером if ( ProcNum != 0 ) Receive(u[0][*],N+2,PrevProc); if ( ProcNum != NP-1 ) Send(u[M][*],N+2,NextProc); }
Данный прием позволяет выполнить все необходимые операции передачи всего за два последовательных шага. На первом шаге все процессоры с нечетными номерами отправляют данные, а процессоры с четными номерами осуществляют прием этих данных. На втором шаге роли процессоров меняются - четные процессоры выполняют Send, нечетные процессоры исполняют операцию приема Receive.
В стандарте MPI предусмотрена операция Sendrecv, с использованием которой предыдущий фрагмент программного кода может быть записан более кратко:
// передача нижней граничной строки следующему // процессору и прием передаваемой строки от // предыдущего процессора Sendrecv(u[M][*],N+2,NextProc,u[0][*],N+2,PrevProc);
Реализация подобной объединенной функции Sendrecv обычно осуществляется таким образом, чтобы обеспечить и корректную работу на крайних процессорах, когда не нужно выполнять одну из операций передачи или приема, и организацию чередования процедур передачи на процессорах для ухода от тупиковых ситуаций, и возможности параллельного выполнения всех необходимых пересылок данных.
На следующем шаге мы рассмотрим коллективные операции обмена информацией.
