Теория и практика параллельных вычислений
         

Обмен информацией между процессорами


Параллельный вариант метода сеток при ленточном разделении данных состоит в обработке полос на всех имеющихся серверах одновременно в соответствии со следующей схемой работы:

Алгоритм 11.8. Параллельный алгоритм, реализующий метод сеток при ленточном разделении данных

// Алгоритм 11.8 // схема Гаусса-Зейделя, ленточное разделение данных // действия, выполняемые на каждом процессоре do { // <обмен граничных строк полос с соседями> // <обработка полосы> // <вычисление общей погрешности вычислений dmax>} while ( dmax > eps ); // eps — точность решения

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

  • ProcNum – номер процессора, на котором выполняются описываемые действия,
  • PrevProc, NextProc – номера соседних процессоров, содержащих предшествующую и следующую полосы,
  • NP – количество процессоров,
  • M – количество строк в полосе (без учета продублированных граничных строк),
  • N – количество внутренних узлов в строке сетки (т.е. всего в строке N+2 узла).

При нумерации строк полосы будем считать, что строки 0 и M+1 есть продублированные из соседних полос граничные строки, а строки собственной полосы процессора имеют номера от 1 до M.


Рис. 11.11.  Схема передачи граничных строк между соседними процессорами

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

Выполнение подобных операций передачи данных в общем виде может быть представлено следующим образом (для краткости рассмотрим только первую часть процедуры обмена):

// передача нижней граничной строки следующему // процессору и прием передаваемой строки от // предыдущего процессора if ( ProcNum != NP-1 ) Send(u[M][*],N+2,NextProc); if ( ProcNum != 0 ) Receive(u[0][*],N+2,PrevProc);


(для записи процедур приема-передачи используется близкий к стандарту MPI (см. лекцию 5) формат, где первый и второй параметры представляют пересылаемые данные и их объем, а третий параметр определяет адресата (для операции Send) или источник (для операции Receive) пересылки данных).

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

Приведенная выше последовательность блокирующих операций приема-передачи данных (вначале Send, затем Receive) приводит к строго последовательной схеме выполнения процесса пересылок строк, т.к. все процессоры одновременно обращаются к операции Send и переходят в режим ожидания. Первым процессором, который окажется готовым к приему пересылаемых данных, будет сервер с номером NP-1. В результате процессор NP-2 выполнит операцию передачи своей граничной строки и перейдет к приему строки от процессора NP-3 и т.д.


Общее количество повторений таких операций равно NP-1. Аналогично происходит выполнение и второй части процедуры пересылки граничных строк перед началом обработки строк (см. рис. 11.11).

Последовательный характер рассмотренных операций пересылок данных определяется выбранным способом очередности выполнения. Изменим этот порядок очередности при помощи чередования приема и передачи для процессоров с четными и нечетными номерами.

// передача нижней граничной строки следующему // процессору и прием передаваемой строки от // предыдущего процессора 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 (см. лекцию 5) предусмотрена операция Sendrecv, с использованием которой предыдущий фрагмент программного кода может быть записан более кратко:

// передача нижней граничной строки следующему // процессору и прием передаваемой строки от // предыдущего процессора Sendrecv(u[M][*],N+2,NextProc,u[0][*],N+2,PrevProc);

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


Содержание раздела