Разработка параллельных программ является весьма трудоемким процессом, особенно для систем MPP типа, поэтому, прежде чем приступать к этой работе, важно правильно оценить как ожидаемый эффект от распараллеливания, так и трудоемкость выполнения этой работы. Очевидно, что без распараллеливания не обойтись при программировании алгоритмов решения тех задач, которые в принципе не могут быть решены на однопроцессорных системах. Это может проявиться в двух случаях: либо когда для решения задачи требуется слишком много времени, либо когда для программы недостаточно оперативной памяти на однопроцессорной системе. Для небольших задач зачастую оказывается, что параллельная версия работает медленнее, чем однопроцессорная. Такая ситуация наблюдается, например, при решении на nCUBE2 систем линейных алгебраических уравнений, содержащих менее 100 неизвестных. Заметный эффект от распараллеливания начинает наблюдаться при решении систем с 1000 и более неизвестными. На кластерных системах ситуация еще хуже. Разработчики уже упоминавшегося ранее пакета ScaLAPACK для многопроцессорных систем с приемлемым соотношением между производительностью узла и скоростью обмена (сформулированного в разделе 1.4) дают следующую формулу для количества процессоров, которое рекомендуется использовать при решении задач линейной алгебры:
P=M x N/10⁶, где M x N - размерность матрицы.

Или, другими словами, количество процессоров должно быть таково, чтобы на процессор приходился блок матрицы размером примерно 1000x1000. Эта формула, конечно, носит рекомендательный характер, но, тем не менее, наглядно иллюстрирует, для задач какого масштаба разрабатывался пакет ScaLAPACK. Рост эффективности распараллеливания при увеличении размера решаемой системы уравнений объясняется очень просто: при увеличении размерности решаемой системы уравнений объем вычислительной работы растет пропорционально n³, а объем обменов между процессорами пропорционально n². Это снижает относительную долю коммуникационных затрат при увеличении размерности системы уравнений. Однако, как мы увидим далее, не только коммуникационные издержки влияют на эффективность параллельного приложения.

Параллельные технологии на MPP системах допускают две модели программирования (похожие на классификацию М. Флинна):

1. SPMD (Single Program Multiple Date) - на всех процессорах выполняются копии одной программы, обрабатывающие разные блоки данных;
2. MPMD (Multiple Program Multiple Date) - на процессорах выполняются разные программы, обрабатывающие разные данные.

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

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

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

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 формирует некий глобальный результат на основе локальных результатов, полученных на каждом процессоре. В этом случае одна и та же копия программы будет выполняться на P процессорах, но каждый процессор будет решать только свою подзадачу. Если разбиение на подзадачи достаточно равномерное, а накладные расходы на обмены не слишком велики, то можно ожидать близкого к P коэффициента ускорения решения задачи.

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

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

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

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

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

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

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

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

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

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

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