Использование многопроцессорных вычислительных систем с распределенной памятью в качестве вычислительного ресурса позволяет успешно решать как минимум две задачи:

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

Следует оговориться, что разработка параллельных программ является достаточно трудоемким процессом, поэтому распараллеливание оправдано только для критических приложений, которые не могут быть решены на однопроцессорных системах либо за разумное время, либо из-за недостаточного объема оперативной памяти на однопроцессорной системе. Для небольших задач зачастую оказывается, что параллельная версия работает медленнее, чем однопроцессорная. Для того, чтобы конкретизировать понятие малая задача, укажем, что при решении системы линейных алгебраических уравнений со 100 неизвестными на nCUBE2 распараллеливание не дает никакого выигрыша.

Эффект от распараллеливания начинает наблюдаться на системах с 1000 и более неизвестными. Разработчики уже упоминавшегося ранее пакета ScaLAPACK для многопроцессорных систем с приемлемым соотношением между производительностью узла и скоростью обмена дают следующую формулу для количества процессоров, которое рекомендуется использовать при решении задач линейной алгебры: , где M x N - размерность матрицы. Или, другими словами, количество процессоров должно быть таково, чтобы на процессор приходился блок матрицы размером 1000 х 1000. Эта формула, конечно, носит рекомендательный характер, но, тем не менее, наглядно иллюстрирует, для задач какого масштаба разрабатывался пакет ScaLAPACK

В предыдущем разделе мы рассмотрели общую структуру системного программного обеспечения классической многопроцессорной системы с распределенной памятью. Наиболее распространенным режимом работы на таких системах является загрузка одной и той же копии программы в некоторое число процессоров. В данном разделе мы рассмотрим вопрос, каким образом при этом можно достичь большей скорости решения задачи по сравнению с однопроцессорной системой. В идеале решение задачи на P процессорах должно выполняться в P раз быстрее, чем на одном процессоре, или/и должно позволить решить задачу с объемами данных, в P раз большими . На самом деле такое ускорение практически никогда не достигается. Причина этого хорошо иллюстрируется законом Амдала [10]:

(1)

где S - ускорение работы программы на P процессорах, а f - доля непараллельного кода в программе. Из формулы следует, что P-кратное ускорение может быть достигнуто, только когда доля непараллельного кода равна 0, что достигается только для полностью независимых программ. Очень наглядно действие этого закона демонстрирует таблица 1.

Из таблицы хорошо видно, что если, например, доля последовательного кода составляет 2%, то более чем 50-кратное ускорение в принципе получить невозможно. Тем не менее, такая задача достаточно эффективно будет считаться на 8 процессорах, а в некоторых случаях потеря производительности на 37% может быть вполне приемлемой (при выполнении задачи на 32 процессорах). Следует иметь в виду, что эта формула не учитывает накладные расходы на обмены между процессорами. Доля последовательных вычислений здесь понимается, конечно, не как количество строк программы с последовательным кодом, а как количество выполняемых машинных операций, которое приходится дублировать всем процессорам. Оценить эту величину из анализа текста программы практически невозможно. Такую оценку могут дать только реальные просчеты на различном числе процессоров.

Итак, рассмотрим, какими свойствами должна обладать многопроцессорная система для разработки и исполнения на ней параллельной программы. Минимально необходимый набор требуемых для этого средств удивительно мал:

1. Процессоры в системе должны иметь уникальные идентификаторы (номера).
2. Должна существовать функция идентификации процессором самого себя.
3. Должны существовать функции обмена между двумя процессорами: посылка сообщения одним процессором и прием сообщения другим процессором.

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

Разработка параллельной программы подразумевает разбиение задачи на N подзадач, каждая из которых решается на отдельном процессоре. Таким образом, упрощенную схему параллельной программы, использующей механизм передачи сообщений, можно представить следующим образом:
. . . . . .
IF( proc_id.EQ.0)
CALL task1
END IF
IF(proc_id.EQ.1)
CALL task2
END IF
. . . . . .
result = reduce(result_task1, result_task2, . . . )
END

Здесь proc_id - идентификатор процессора, а функция reduce формирует некий глобальный результат на основе локальных результатов, полученных на каждом процессоре.

Как отмечалось ранее, одна и та же копия откомпилированной программы будет загружаться в N процессоров, но каждый процессор будет решать только свою подзадачу. Если разбиение на подзадачи достаточно равномерное, а накладные расходы на обмены не слишком велики, то можно ожидать близкого к N коэффициента ускорения решения задачи.

Отдельного обсуждения требует понятие подзадача. В параллельном программировании это понятие имеет весьма широкий смысл. Под подзадачами можно понимать некий набор выделенных фрагментов программы, которые могут выполняться независимо (в этом случае говорят о функциональном распараллеливании). Такой подход, в частности, используется в системах обработки видеоинформации, когда множество квантов данных должны проходить несколько этапов обработки. В этом случае вполне оправданной будет конвейерная организация вычислений, при которой каждый этап вычислений выполняется на отдельном процессоре. Однако, такой подход имеет весьма ограниченное применение, поскольку организовать достаточно длинный конвейер, да еще с равномерной загрузкой всех процессоров, весьма сложно. На практике процедура распараллеливания чаще всего применяется к циклам. Тогда в качестве отдельных подзадач могут выступать экземпляры тела цикла, выполняемые для различных значений переменной цикла. Рассмотрим простейший пример:

DO I = 1,1000
C(I) = C(I) + A(I+1)
END DO

В этом примере можно выделить 1000 независимых подзадач вычисления компонентов вектора C, каждая из которых, в принципе, может быть выполнена на отдельном процессоре. Предположим, что в распоряжении программиста имеется 10-ти процессорная система, тогда в качестве независимой подзадачи можно оформить вычисление 100 элементов вектора C. При этом до выполнения вычислений необходимо принять решение о способе размещения этих массивов в памяти процессоров. Здесь возможны два варианта:

1. Массивы целиком хранятся в каждом процессоре, тогда задача сводится к вычислению стартового и конечного значений переменной цикла для каждого процессора. В каждом процессоре будет храниться своя копия массива, в которой будет модифицирована только часть элементов. В конце вычислений, возможно, потребуется сборка модифицированных частей со всех процессоров.
2. Массивы распределены по процессорам, тогда в общем случае может потребоваться алгоритм установления связи индексов локального массива в некотором процессоре с глобальными индексами всего массива. Если в процессе вычислений окажется, что какие-то требующиеся компоненты массива отсутствуют в данном процессоре, то потребуется их пересылка из других процессоров.

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

Рассмотренный выше пример достаточно хорошо укладывается в схему методологического подхода к решению задачи на многопроцессорной системе, который излагается Фостером [11]. Автор выделяет 4 этапа разработки параллельного алгоритма:

1. разбиение задачи на минимальные независимые подзадачи (partitioning);
2. установление связей между подзадачами (communication);
3. объединение подзадач с целью минимизации коммуникаций (agglomeration);
4. распределение укрупненных подзадач по процессорам таким образом, чтобы обеспечить равномерную загрузку процессоров (mapping).

Эта схема, конечно, не более чем описание философии параллельного программирования, которая лишь подчеркивает отсутствие какого-либо формализованного подхода в параллельном программировании для MPP систем. Если 1-й и 2-й пункты имеют более или менее однозначное решение, то решение задач 3-го и 4-го пунктов основывается главным образом на интуиции программиста. Чтобы проиллюстрировать это обстоятельство, рассмотрим следующую задачу. Предположим, требуется исследовать поведение определителя матрицы в зависимости от некоторого параметра. Один из подходов состоит в том, чтобы написать параллельную версию подпрограммы вычисления определителя и вычислить его значения для исследуемого интервала значений параметра. Однако, если размер матрицы относительно невелик, то может оказаться, что значительные усилия на разработку параллельной подпрограммы вычисления определителя не дадут сколь либо существенного выигрыша в скорости работы программы. В этом случае, скорее всего, более продуктивным подходом будет использование для нахождения определителя стандартной однопроцессорной подпрограммы, а по процессорам разложить исследуемый диапазон изменений параметра.

Рассмотрим реализацию средств параллельного программирования на многопроцессорной системе nCUBE2.