Параллельное программирование: Учебное пособие, страница 23

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

Использование  развертки цикла  было продемонстрировано последним примером (2.20). Этот прием достаточно типичен для векторно-матричных операций при обработке алгебраических систем. Последнее в разделе 2.2.4 уже обсуждалось для случая умножения матриц .

2.2.6  Формальный подход к распараллеливанию циклов.

Рассмотренные выше подходы к распараллеливанию преследовали единственную цель, выявить максимально высокую степень параллелизма. Однако принцип неограниченного параллелизма для реализации параллельных вычислений практически мало пригоден из-за ограниченности аппаратных ресурсов вычислительных систем и их коммуникационной среды для осуществления взаимодействий. Так как посредником в постановке задач на вычислительную обработку служат специальные трансляторы языковых конструкций в конкретную последовательность машинных команд, то возникает проблема вложения распараллеленной вычислительной структуры в имеющуюся вычислительную систему. Для этого транслятору необходимо передавать много дополнительной информации, которая позволяла бы операционной системе управлять взаимодействующими параллельно идущими процессами. Важным ограничивающим параметром является число выделенных для использования процессоров. Их ограниченное число вынуждает максимально параллельную структуру вычислений сжать до степени параллелизма, равной числу процессоров. Это далеко не тривиальная задача особенно для структур сдваивания и различных циклических структур (см. рисунки 2.2, 2.3, 2.8).

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

,

где      – множество индексных переменных , определяющее одновременное выполнение группы итераций , или по множеству логических выражений (предикатов) , запускающее группу одновременно выполняемых итераций типа while:          ;

           {тип параллельности} – множество ключевых слов, предписывающих операционной системе порядок обработки зависимых или независимых друг от друга проходов тела цикла. В ряде языков описания параллельных программ в множество типов параллельности входили следующие ключевые слова: {PAR, SEQ, CONC, AUTON, SYNCH(J), SIM, EXCL, ...}. Каждое из этих слов определяло поведение параллельных ветвей, то есть семантику параллельного цикла. Смысл этих предписаний, вкратце, заключался в следующем:

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