Разработка параллельных программ является весьма трудоемким процессом, особенно для систем MIMD-вычислительных систем. Поэтому до начала работы по разработке параллельной программы важно правильно оценить как трудоемкость этой работы, так и ожидаемый эффект.
Очевидно, что без параллельного программирования не обойтись при решении тех задач, которые в принципе не могут быть решены на однопроцессорных системах (когда для решения задачи на однопроцессорной ЭВМ требуется слишком много времени, либо слишком много оперативной памяти).
Для небольших задач зачастую оказывается, что параллельная версия работает медленнее, чем однопроцессорная. Особенно выпукло этот эффект можно наблюдать на вычислительных кластерах. Разработчики широко известной параллельной библиотеки прикладных программ в области линейной алгебры ScaLAPACK дают следующую рекомендацию: для обеспечения приемлемой эффективности на один процессор должны приходиться блоки матриц размером не менее примерно 1000×1000. Причина роста эффективности распараллеливания при увеличении размера решаемой задачи линейной алгебры проста — при увеличении размерности n решаемой задачи объем вычислительной работы растет пропорционально , а объем обменов между процессорами пропорционально . Т.е. с ростом размерности решаемой задачи снижается относительная доля коммуникационных затрат.
Принято выделять следующие этапы общей схемы решения задач на многопроцессорных вычислительных системах:
  1. разбиение задачи на минимально независимые подзадачи (partitioning);
  2. установление связей между подзадачами (communication);
  3. объединение подзадач с целью минимизации коммуникаций (agglomeration);
  4. распределение укрупненных подзадач по процессорам таким образом, чтобы обеспечить равномерную загрузку процессоров (mapping).
Можно выделить две следующие парадигмы высокоуровневого программирования для мультипроцессоров и мультикомпьютеров.
  1. MPMD-парадигма программирования (Multiple Program Multiple Date). В этом случае на разных процессорах вычислительной системы выполняются разные программы, обрабатывающие разные данные. MPMD-парадигма программирования адекватна функциональному параллелизму.
  2. SPMD-парадигма программирования (Single Program Multiple Date). В соответствие с этой парадигмой на всех процессорах вычислительной системы выполняются копии одной программы, обрабатывающие разные блоки данных. SPMD-парадигма программирования адекватна параллелизму по данным.
Начнем рассмотрение языков высокого уровня (ЯВУ) для программирования мультипроцессоров и мультикомпьютеров с более широко распространенной MPMD-парадигмы. Будем называть далее такие языки высокого уровня MPMD-языками высокого уровня.
В MPMD-ЯВУ различают следующие основные средства организации параллельных вычислений:
Основным понятием параллельного MPMD-ЯВУ является понятие процесса. Элементарный процесс состоит из одного или совокупности последовательно выполняемых операторов в виде блоков, подпрограмм, процедур, функций, задач и пр. Объем элементарного процесса определяет степень гранулированности параллельной программы или степень зернистости параллельной программы.
Программа в параллельном MPMD-ЯВУ – это система процессов, выполняемых конкурентно (путем разделения времени одного или нескольких процессоров) либо параллельно (путем выделения каждому процессору индивидуального процессора). В первом случае имеет место мультипрограммирование, которое обычно поддерживается ядром операционной системы. Во втором случае осуществляется мультипроцессорная обработка, если речь идет о мультипроцессоре, или распределенная обработка – для мультикомпьютера.
Средства описания процессов.
При описании параллельных процессов используют разного рода операторные скобки:
parbegin
  Процесс 1;
  Процесс 2;
  ...
  Процесс n
parend

cobegin
  Процесс 1;
  Процесс 2;
  ...
  Процесс n
coend
Пример 1
В языке OCCAM описание параллельных процессов имеет вид
PAR
  chen1?a
  chen2?b
Данная конструкция вызывает два параллельных процесса:
  • первый процесс - чтение из канала с именем chen1 значения и присваивание его переменной a.
  • второй процесс - чтение из канала с именем chen2 значения и присваивание его переменной b
Кроме операторных скобок используются также специальные операторы, отмечающие начало и конец параллельного сегмента, например,
fork (a,b,c,...,x)
  a: Процесс 1;
  b: Процесс 2;
  c: Процесс 3;
  ...
  x: Процесс n
join (a,b,c,...,x)
Здесь первый оператор открывает параллельный сегмент с ветвями, помеченными метками , а второй оператор – закрывает этот сегмент.
Важнейшим классом параллельных процессов являются параллельные циклические процессы. Для описания циклических процессов используют конструкции вида
FOR <индексное множество> DO <тип параллелизма>
где – параметр цикла, – тело цикла. Индексное множество может задаваться тройкой чисел , , — тело цикла выполняется при всех от до с шагом ; набором допустимых значений параметра цикла — тело цикла выполняется при всех из числа ; логическим выражением (предикатом) — тело цикла выполняется при всех , для которых (цикл типа WHILE). Параллельный циклический процесс может содержать указание на тип параллелизма, который должен быть использован при выполнении этого процесса. Например, тип параллелизма CONC – параллельные ветви, соответствующие телу цикла при различных значениях параметра цикла, должны выполняться на одном процессоре конкурентно; AUTON – каждая из указанных ветвей должна выполняться асинхронно на своем процессоре; SIM – все ветви одинаковы и должны выполняться синхронно (на SIMD машине).
Пример 2
В языке Occam конструкция
PAR i=0 FOR n
  buffer(i)
создает параллельный процесс buffer, buffer,…, buffer, где buffer – именованный процесс
Средства инициализации и завершения процессов.
Инициализация и завершение процессов в параллельных MPMD-ЯВУ могут быть выражены явно или косвенно.
Инициализация процессов. Косвенно обычно вызывают процессы, оформленные в виде блоков. Их можно рассматривать как безымянные процедуры, неявно вызываемые в том месте, где находится определение процесса.
Для процессов, которые описаны как подпрограммы, процедуры, функции, задачи и т.п., языковые средства инициализации близки к конструкциям вызова аналогичных программных единиц в традиционных ЯВУ (по имени процесса со списком параметров). Существуют также модифицированные варианты этих средств, когда имени вызываемого процесса предшествует ключевое слово типа PARCALL, CREATE. Отметим, что при внешнем сходстве средств инициализации параллельных процессов с вызовом именованных программных единиц в последовательных ЯВУ, выполняемые при этом действия (и необходимое время) существенно отличаются.
Существуют и более развитые средства инициализации, например, управляющее выражение в языке параллельный Паскаль
PATCH <управляющее выражение> END;
где <управляющее выражение> содержит имена процессов и порядок их выполнения (последовательно или параллельно).
Завершение процессов. Процесс оканчивается нормально, если управление достигло конца процесса (последнего его оператора) и если все подчиненные процессы (если они есть) уже закончили свое выполнение. Для нормального завершения процессов используют традиционные операторы parend, coend, end, return, stop (для завершения все задачи).
Для принудительного завершения процесса используется, как в языке ADA, например, оператор ABORT. Отметим, что при этом принудительно завершаются также все подчиненные процессы.