Технологии высокопроизводительных вычислений

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

Для сравнительного рассмотрения моделей и технологий параллельного программирования у нас недостаточно примеров того, как именно пишутся параллельные программы. Мы пока рассмотрели (в Разделе 1.5) лишь один пример модельной программы, и построили «на бумаге» ее параллельную реализацию. Естественно, в настоящем разделе мы будем, по мере надобности, использовать этот пример в иллюстративных целях. Однако, способ параллельной реализации алгоритма Якоби обманчиво прост, и не хотелось бы создавать ложного впечатления, что все или почти все техники параллельной реализации вычислений в главном на него похожи. Ниже мы встретим несколько примеров технологий параллельного программирования, с помощью которых метод Якоби записывается легко и изящно, в то время как целый класс широко применяемых методов параллельных вычислений не записывается вообще. В следующем разделе приводится пример модельного алгоритма, принципиально отличающегося от метода Якоби по технике параллельной реализации.

6.1. Два способа параллельной обработки данных.

В монографии Воеводиных «Параллельные вычисления» [2] отмечается, что существуют всего два принципиально различных способа параллельной обработки данных – собственно параллелизм и конвейер. Пример собственно параллелизма мы видели – это параллельный вариант метода Якоби. В критическом цикле программы выделяются независимые вычисления, и они «раздаются» равными порциями разным процессорам, работающим «в фазе»: каждый выполнил очередной шаг обработки – все, кому надо, обменялись недостающими данными – все перешли к следующему шагу. В каждый момент времени каждый процессор выполняет одну и ту же итерацию, но с разными данными, обработка которых на этой итерации не зависит от обработки других порций данных на этой же итерации. 

Конвейерная обработка данных принципиально отличается от этого простого шаблона. Рассмотрим пример альтернативного численного метода решения той же (по физическому смыслу) задачи математической физики, то есть задачи Дирихле для уравнения Лапласа. Это – метод верхней релаксации, и записывается он так:

#include <stdio.h>

/***/

#define MX 640

#define MY 480

#define W 0.5

#define NITER 10000

#define STEPITER 100

       static float  f[MX][MY];

/***/

       int main( int argc, char **argv )

{

       int i, j, n, mb, me, m;         

/***/

              printf( "Solving heat conduction task on %d by %d grid\n",

                 MX, MY );             

              fflush( stdout );

/* Initial conditions: */

       for ( i = 0; i < MX; i++ )

        {

              for ( j = 0; j < MY; j++ )

                {

                 f[i][j] = df[i][j] = 0.0;

                 if      ( (i == 0)

                        || (j == 0) ) f[i][j] = 1.0;

                 else if ( (i == (mx-1))

                        || (j == (my-1)) ) f[i][j] = 0.5;

                }

              }

/* Iteration loop: */

       for ( n = 0; n < NITER; n++ )

        {

//                 if ( !(n%STEPITER) )

            printf( "Iteration %d\n", n );

/* Step of calculation starts here: */

              for ( i = 1; i < (MX-1); i++ )

                {

                 for ( j = 1; j < (MY-1); j++ )

                  {

                   f[i][j] = W * ( f[i][j+1] + f[i][j-1] + f[i-1][j] + f[i+1][j] )

                               * 0.25 + (1-W) * f[i][j];

                  }

                }

/* Step is over: */

              }

       return 0;

}

Как и в случае рассмотрения метода Якоби, не будем обсуждать ни физическую, ни вычислительно – математическую сторону вопроса: нас волнует параллельная реализация записанного здесь алгоритма, и ничего более.

При всем кажущемся сходстве с методом Якоби, этот алгоритм обладает крайне неприятным для нас свойством: в его итерации нет независимых вычислений. Расчет движется «слева направо и сверху вниз» по полю величин, и каждое новое значение этого поля зависит от всех, вычисленных ранее. Зачем математики придумали такой неудобный для параллельной реализации метод? Затем, что он быстрее сходится. Иногда – на порядок быстрее. Как выполнить параллельную реализацию, если все данные зависят друг от друга?

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

- третий процессор приступил к первой итерации,

- в это время второй процессор уже выполняет вторую,

- а первый – третью,

- наконец, нулевой – четвертую.

Цель достигнута – процессоры работают одновременно, правда, не сразу, а лишь начиная с момента, когда «фронт вычислений» дойдет до последнего процессора. Если число итераций много больше числа процессоров (а это практически всегда так), этой неприятностью можно пренебречь.

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

Проще говоря, если параллелизм независимых вычислений можно назвать параллелизмом в пространстве, то конвейерный параллелизм естественно называть параллелизмом во времени.

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

6.2. Два лица программистской модели.

Модель параллельного программирования, как и любая программистская модель, имеет два аспекта, или два «лица».

С одной стороны, она призвана быть возможно более удобной для программиста – это «лицо, обращенное к программисту». В этом смысле программистская модель – чистая «игра ума», логическая абстракция, созданная одним программистом для другого.

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

Например, для многих программистов очень удобна была бы модель виртуальной общей памяти, разделяемой всеми узлами кластера на условиях равной доступности. Осуществима ли ее реализация? Конечно. Ничто не мешает нам воспользоваться рассмотренной выше, в Разделе 2.3.5, технологией организации виртуальной памяти, реализовав подкачку отсутствующих страниц не с жесткого диска, а из сети, то есть от других процессоров. Формально работоспособная общая память будет построена. Пусть для ее физической реализации используется такая сравнительно медленная и высоколатентная сеть, как Ethernet. Это будет означать, что всякое взаимодействие процессоров, даже требующее передачи всего лишь одного байта, будет заключаться в передаче страниц (ведь подкачка работает с точностью до страниц, как мы знаем). В этих условиях о всякой эффективности коммуникаций придется забыть навсегда. В то же время, имей программист в своем распоряжении MPI, он никогда не стал бы выписывать обмен страницей там, где достаточно обменяться единственным байтом (или небольшим числом байтов, разбросанных по разным страницам). Это – типичный пример модели, удобной для программиста, но не адекватной аппаратуре, то есть не допускающей достаточно эффективной реализации.

Можно привести и обратный пример. Дав прикладному программисту вместо MPI набор системных вызовов, служащих для работы со стеком tcp/ip, мы, возможно, обеспечим физическую возможность некоторого ускорения прикладной программы. Но достигаться это будет таким ее усложнением, что прикладной программист вряд ли на это пойдет. Это – типичный пример модели, допускающей очень эффективную реализацию, но крайне, неоправданно неудобной для программиста.

До недавних пор оборудование было логически весьма однородно, и очень хорошо абстрагировалось моделью явного двустороннего обмена сообщениями. На основе этой базовой модели был построен целый ряд производных моделей, то есть предполагающих, что «внутри себя» они «сделаны из» двусторонних обменов. Это и технологически было так: соответствующие технологии реализовывались на основе MPI, то есть результирующая программа, написанная человеком, вообще говоря, не знающим MPI, запускалась на счет командой mpirun.

Аппаратура, тем не менее, не стоит на месте. Постепенно стали появляться аппаратные возможности, которые в модель двустороннего обмена сообщениями не укладываются. Конечно, реализовать двусторонний обмен сообщений можно на чем угодно, но, скажем,  для аппаратуры, реализующей симметрично адресуемую общую память, реализация «поверх» нее MPI – не очень хорошо, возможности аппаратуры при этом не полностью используются. Современные сети быстро развиваются в сторону таких базовых моделей, как односторонние обмены и NUMA. В связи с этим интересно посмотреть, какие производные модели могут быть получены на этой новой базе.

6.3. Модель: явный двусторонний обмен сообщениями.

Это самая старая и самая «ручная» (наименее автоматизированная, наиболее близкая к аппаратуре) модель. В «до – кластерную эру» она была представлена многочисленными библиотеками, каждая из которых была ориентирована на конкретную модель суперкомпьютера. Затем появилась PVM [3], технология, предназначенная, в основном, для кластеров невыделенных рабочих станций. Разработчики этой технологии изначально не стремились к высокой эффективности, поскольку сетевое оборудование все равно было довольно слабым, и уделяли основное внимание простоте программистских интерфейсов. В результате получилась система, не допускающая действительно эффективной реализации. В силу исторических причин она используется до сих пор в некоторых старых программистских коллективах, в основном – в Европе.

Затем появился стандарт MPI [3], на сегодня – главная технология этой программистской модели.

Все технологии этой модели базируются на двустороннем рандеву, но что-то добавляют. Рассмотрим кратко набор добавлений к стандартным возможностям двустороннего рандеву, сделанный в MPI.

-         Типы передаваемых данных. Простые и производные. Простые типы нужны для гетерогенных установок, производные – для передачи одним обращением к функции MPI совокупностей данных, расположенных в памяти не подряд, но некоторым регулярным образом (например, для передачи столбца двумерного массива в C).

-         Теги и коммуникаторы. Возможность принимать сообщения не в том порядке, в каком они были посланы. Это – очень «дорогая» в реализации возможность, к тому же, очень часто вообще не используемая программистами. Потребовалось несколько лет, чтобы разработчики MPI научились реализовывать эту возможность эффективно. То есть так, чтобы она не повышала латентности даже тех обменов, где она по существу не используется.

-         Широковещание и коллективные операции обмена. Очень полезные возможности.

-         Барьерная синхронизация.

-         ROMIO – согласованная работа вычислительных узлов с файлами общей файловой системы.

-         Асинхронность и буферизация. Три режима посылки, плюс асинхронность как таковая.

MPI_Bsend – либо буферизуется, либо ошибка.

MPI_Ssend – завершается, только если прием уже запущен.

MPI_Rsend – либо мы знаем, что прием уже запущен, либо непредсказуемо.

Асинхронность в MPI называется “non-blocking”.

В целом MPI можно охарактеризовать как удачно спроектированную систему,  допускающую эффективную реализацию. Очень важно, что при использовании простейших возможностей наличие не используемых в данной программе более «дорогих» возможностей, вроде коммуникаторов или производных типов, не снижает эффективности. Так, реализации MPI на базе tcp/ip практически не добавляют латентности по сравнению с непосредственным использованием tcp/ip.

6.4. Модель: односторонний обмен сообщениями.

Это очень интересная модель, которую можно рассматривать и как базовую (продиктованную свойствами аппаратуры), и как производную (надстроенную над аппаратурой, возможно, и не имеющей подходящих свойств, просто для удобства программиста). Смысл модели состоит в том, что для передачи данных достаточно инициативы одной стороны. Процессор может «насильно засунуть» данные в указанное им же место памяти другого процессора, безо всякого ведома последнего. Также можно и «насильно вытащить» указанные данные из другого процессора без его ведома. Очевидно, такой стиль коммуникаций подразумевает наличие двух возможностей, которые в случае двустороннего рандеву отсутствуют или могут отсутствовать.

-         Необходимость иметь расширенную систему глобальной адресации. Чтобы «насильно» поместить данные в указанное мной место памяти в другом процессоре, я должен иметь систему координат для указания мест в чужой памяти. Иначе непонятно, как именно я скажу, куда помещать.

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

Исторически эта модель сначала возникла как производная, то есть дающая дополнительные удобства программисту, возможно, ценой некоторого снижения эффективности, вне всякой связи со свойствами коммуникационного оборудования. Типичный пример такого подхода – библиотека Global Arrays [15].