ПАРАЛЛЕЛЬНЫЕ МЕТОДЫ ВЫЧИСЛЕНИЙ. АЛГОРИТМЫ И ЯЗЫКИ

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

Понятие распараллеливания алгоритма подразумевает пред­ставление алгоритма (программы) в таком виде, чтобы можно было совмещать во времени выполнение отдельных участков алгоритма (его ветвей). Процесс распараллеливания алгоритма состоит в выделении ветвей, описании структуры параллельно­го процесса и синхронизации выполнения ветвей при его реа­лизации. Для облегчения распараллеливания в некоторых языках (например, PL-1) предусмотрены специальные средства для вы­деления ветвей в алгоритме и синхронизации их. В этом случае программист в явной форме указывает на возможности распа­раллеливания, а транслятор и операционная система машины ре­ализуют параллельный процесс. Если исходный алгоритм запи­сан на языке, не имеющем подобных средств, то его распаралле­ливание сводится к сегментации алгоритма и объединению сег­ментов в ветви по определенным правилам. Эту работу выполня­ет либо программист, либо машина по специальной программе сегментации. В вычислительной машине могут быть специаль­ные блоки, предназначенные для сегментации программ.

Основой построения параллельного алгоритма может слу­жить как последовательный алгоритм, так и задача сама по себе. При распараллеливании последовательного алгоритма наибо­лее разумным представляется прагматический подход, т.е. в пос­ледовательных алгоритмах выявляются часто встречаемые эле­менты, которые затем трансформируются в параллельную фор­му. Далее этот подход иллюстрируется на примерах арифмети­ческих выражений, а также на распараллеливании с помощью перестановок и рекурсий. Очевидно, что по крайней мере неко­торые из этих преобразований могут быть выполнены автома­тически. Подобный путь исключительно важен, поскольку ока­зывается возможным использование на параллельных ЭВМ со­зданного для обычных машин дорогостоящего программного обеспечения. Указанные принципы распараллеливания относят­ся к определенным последовательным алгоритмам. Это соот­ветствует общепринятому в численном анализе последователь­ному характеру мышления. При программировании на парал­лельных ЭВМ необходим параллельный тип мышления. Отме­тим, что параллельный тип мышления характерен для аналого-гибридных вычислений.

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

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

Распараллеливание таких алгоритмов, как в методе исклю­чения по Гауссу при решении систем линейных уравнений, вы­полняется весьма несложно. Ядро этой программы - вычисле­ние скалярных произведений. На параллельной ЭВМ оно мо­жет быть выполнено достаточно эффективно. С другой сторо­ны, параллельная реализация даже весьма простых алгоритмов, например, выбора разрешающего элемента, иногда сильно зат­руднена.

Многие итерационные методы, в частности, методы линей­ной алгебры, формулируются в терминах матриц и векторов. Однако встречаются важные итерационные методы, например, метод последовательной верхней релаксации (БСЖ), для распа­раллеливания которых необходимы некоторые ухищрения.

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

Если отвлечься от математического смысла программы, то потенциальные возможности распараллеливания программ, например, на Фортране скрыты в циклах типа БО. По этой при­чине большинство компиляторов для параллельных ЭВМ рас­параллеливает последовательные циклы типа БО. Этот тип ав­томатического распараллеливания программ имеет важное зна­чение для переноса существующего (последовательного) мате­матического обеспечения на параллельные ЭВМ.

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

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

При рассмотрении вопросов разработки параллельных ал­горитмов и языков для однородных вычислительных систем необходимо учитывать следующие соображения:

• Режим параллельной обработки должен использоваться в основном для тех задач, которые не могут быть реализованы достаточно эффективно (т.е. с нужной точностью, временем ре­шения) с помощью одной ЭВМ.

• Распараллеливание вычислительного процесса необходи­мо для получения нужной эффективности решения сложных задач; в общем случае не требуется прибегать к максимальному параллелизму.

• Схемы алгоритмов (программ) являются иерар-хически-ми структурами, высший уровень которых - крупные блоки, а низший уровень - операторы (машинные команды).

• Процесс распараллеливания должен начинаться с самого высокого уровня; переход на более низкий уровень происходит только в том случае, если не удалось достичь нужной степени распараллеливания на данном уровне.

Схема параллельного алгоритма показана на рис. 4.1.

При разработке Р-алгоритма главное внимание уделяется выявлению циклов и распределению массивов. Используется 2 основные схемы распараллеливания: групповая и конвейерная. Все многообразие взаимодействий между ветвями Р-алгоритма может быть сведено к шести основным процедурам:

1. Трансляционный обмен (информация передается из од­ной ветви во все остальные).

2. Трансляционно-циклический обмен - реализует транс­ляционный обмен в цикле по ветвям.

3. Обмен сдвигом (передача информации из данной ветви в следующую или предыдущую).

4. Дифференцированный обмен (информация передается из данной ветви в некоторые выделенные).

5. Коллекторный обмен (информация собирается из всех ветвей в одну выделенную).

6. Обобщенный условный переход - изменяется естествен­ный порядок реализации операторов во всех ветвях при выпол­нении обобщенного условия.

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

Параллельные языки или языки высокого уровня, предназ­наченные для записи Р-алгоритмов, отличаются от известных языков средствами задания обменных взаимодействий Р-ветвей: системными операторами и системными программными функ­циями. Вместе с обычными операторами они образуют набор, позволяющий описывать как последовательные, так и параллель­ные вычислительные процессы. Примерами этих языков могут служить Бейсик, Фортран, Ассемблер.

Системные операторы, введенные в эти языки, позволяют задавать взаимодействия ветвей Р-процесса на микроуровне. Это освобождает программиста от необходимости знать структуру системы, в частности, такие команды, как «прием», «передача», «настройка». Специальные операторы ввода-вывода обеспечи­вают удобное задание распределения массивов по ветвям. В ка­честве стандартных системных функций могут использоваться функции, определяющие значение максимального и минималь­ного элемента массива, сумму всех значений массива, распреде­ленного по ветвям, общее число ветвей и т.д. Для данных язы­ков каждая ветвь Р-программы оформляется как последователь­ная программа. Особенность такой последовательной програм­мы - наличие операторов обменных взаимодействий, которые вводятся в операционную систему в виде блоков или библио­течных модулей. Библиотечные модули позволяют использовать операторы обменных взаимодействий в языках высокого уров­ня. Описанный подход постепенного расширения последователь­ных алгоритмов и языков средствами параллелизма позволяет полностью сохранить преемственность и при развитии языков и алгоритмов в направлении структуризации приблизиться к естественным наукам.

Касаясь проблемы языка программирования, необходимо отметить, что совершенно не обязательно разрабатывать для ПВС специальный язык высокого уровня. Для того, чтобы писать Р-программы, достаточно незначительного расширения языка РЬ/ 1 (или любого другого языка высокого уровня) с целью выпол­нения следующих задач:

• для программирования на существующей уже работаю­щей ПВС,

• для моделирования на последовательной машине процесса выполнения Р-программ,

• для анализа алгоритмов (в математических терминах). Программа, выполняемая на любой ЭВМ, - это в конечном

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

• Овладеть их синтаксисом нетрудно; программа же, написанная на языке высокого уровня, получается более понят­ной, с легко воспринимаемой структурой.

• Языки высокого уровня лаконичны.

• Так как эти языки универсальны, программу, написаннуюна одном из них, можно рассматривать как математическую формулировку метода решения задачи.

• В литературе широко представлены не только стандарт­ные конструкции этих языков, но и некоторые специальные конструкции, предназначенные для параллельной обработки (например, существуют соответствующие расширения Фортра­на, Алгола 60 и Паскаля) [5].

В качестве наилучшего кандидата, пригодного для состав­ления Р-программ (по крайней мере, программ подчиненных процессоров), был предложен язык РЬ1. Имеются следующие соображения в пользу РЬ/1:

• Этот язык может быть реализован (и в основном уже реализован) на существующих ЭВМ. Более того, этот язык, воз­можно, станет наиболее широко используемым языком програм­мирования. Существует много компиляторов с этого языка (в том числе оптимизирующих).

• Это очень лаконичный язык, особенно когда дело касает­ся обработки векторов и матриц. Например, если А, В и С - это матрицы (п х п), то оператор (А-В+С) означает поэлементное сложение матриц В и С с записью результата в А.

• Язык РЬ/1 имеет ряд других полезных свойств, например возможность работы с подчиненными задачами.

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

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

• Та область памяти, где записаны эти программы, должна быть доступна для УП, но недоступна для подчиненных про­цессоров (ПП).

• В задачу УП входят пересылки данных по шине, поэтому он должен располагать командами, которые обеспечивают та­кие пересылки. Пересылки не должны перекрываться по време­ни.

• УП должен принимать прерывания от всех 1111. Програм­ма УП запускается по сигналам от ПП. Будучи запущенной, она находит очередную подзадачу и, поручив ее одному из ПП, пе­ресылает некоторый файл в память этого ПП, пересылает неко­торые переменные между файлами некоторых ПП или запуска­ет один или все ПП.

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

«Параллельный» PL/1 или PPL/1 должен быть определен таким образом, чтобы программы, написанные на нем, можно было бы легко преобразовывать в программы моделирования. И как мы уже говорили, расширение существующего языка для применения его к «параллельному программированию» являет­ся широко распространенным приемом (таким образом были расширены Фортран, Алгол и Паскаль). Точно таким же обра­зом для системы PEPE был разработан язык PPОK, основанный на Фортране [1 ]. Принимая за основу язык PL/1 , необходимо добавить в него следующие дополнительные возможности:

• Индексы в PPL/1 будут использоваться не только для зада­ния номеров элементов массива, но и для указания номера кон­кретной локальной памяти. В этом случае такой индекс ставит­ся в скобках слева от имени переменной. Если значение индекса в скобках равно нулю или же «левосторонний» индекс вообще отсутствует, то имеется в виду обращение к общей памяти.

• Существуют два способа хранения значений переменных (особенно массивов) в локальных устройствах памяти: под раз­ными или под одинаковыми именами. В общей памяти разме­щается вектор С размерности m. Каждый ПП может обращать­ся только к своему «экземпляру» переменной С; УП может об­ращаться ко всем экземплярам этой переменной. Если все объяв­ляемые переменные сопровождаются знаком (#), то его можно вынести за скобки. Каждый ПП знает свой номер; обращение ксвоему номеру имеет вид (#Р). Количество 1111 обозначается в программах УП как Р.

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

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

Программы, написанные на РРЬ/1 , можно транслировать «один к одному» на язык 81МРБ/1 [ГВМ 72] [5], поскольку этот язык имеет средства:

• Главная программа, написанная на языке 81МРБ/1, запус­кает или последовательно, или параллельно некоторое число так называемых процессов.

• В язык 51МРБ/1 встроены разнообразные средства для обработки списков.

• Предусмотрен оператор «ожидания».

• Приостановленный процесс может быть вновь активизи­рован, если выполнилось некоторое условие (событие). Язык позволяет моделировать весьма сложные взаимодействия меж­ду одновременно протекающими вычислительными процесса­ми.

• Для синхронизации выполнения всех программ (т. е. глав­ной программы и процессов) используется счетчик времени, имитирующий реальное время.

К сожалению, язык 81МРБ/1 не настолько широко извес­тен, чтобы его описание можно было найти в любой книге по вычислительной технике, но имеется другой выход из положе­ния - использовать средства для работы с подчиненными зада­чами, предусмотренные в РЬ/1 . Может быть, они не столь со­вершенны и представляют для моделирования ПВС меньше удобств, чем 81МРБ/1, но преимущество их заключается в том, что они составляют часть стандартного РЬ/1, а следовательно, более доступны.