Ситкевич Т.А., Сюрин В.Н. Параллельные вычислительные среды

Подождите немного. Документ загружается.

тельных алгоритмов, которые содержат векторные элементы, т.е.

операции над матрицами или ма трицами и векторами. Распа-

раллеливание таких операций выполняется непосредственно. По

эт ой причине термины «векторизация» и «распараллеливание»

часто использ ую тся как синонимы. Тем не менее, векторизация

– частный случай распараллелив ания.

Распараллеливание таких алг оритмов, как в методе исклю-

чения по Г ауссу при решении систем линейных уравнений, вы-

полняется весьма несложно. Ядро этой программы – вычисле-

ние скалярных произведений. На параллельной ЭВМ оно мо-

жет быть выполнено доста то чно эффективно. С другой сторо-

ны, параллельная реализация даже весьма простых алгоритмов,

например , выбора разрешающего элемента, иног да сильно за т-

руднена.

Многие итерационные мето ды, в частности, мет о ды линей-

ной алгебры, формулир ую тся в терминах матриц и векторов.

Однако встре чаю тся важные итерационные методы, например,

мето д последова тельной в ерхней релак сации (SOR), для распа-

раллеливания к о торых необ хо димы нек о т орые ухищрения.

Многие алг оритмы вычисляют не отдельные значения, а

б локи зна чений. Примерами таких алг оритмов служат решения

уравнений и алг оритмы минимизации. Другие алг оритмы мо ж-

но мо дифицирова ть так , что они б удут вычислять б лок перемен-

ных.

Если отвл ечься от ма тем а тическ ого смысла программы, то

потенциальные возможности распараллеливания программ,

например , на Фортране скрыты в циклах типа DO. По этой при-

чине большинство к о мпилят оров для параллельных ЭВМ рас-

параллеливает последов а тельные циклы типа DO. Этот тип ав-

то ма тическ ого распараллеливания программ имеет в ажное зна-

чение для переноса существующего (последов а тельног о) мате-

ма тическ ого обеспе чения на параллельные ЭВМ.

Т рансфор мирующие программы для авто м а тическ ого рас-

параллеливания последов а тельных алгоритмов, вообще г ов оря,

проводят анализ пот ока данных последова тельног о алг оритма.

Использ уя нек о торые понятия операционных систем, это т пос-

ледовательный граф пот ок а данных мо ж ет быть преобразов ан в

потоковый граф с мак симальным параллелизмом .

И, нак онец, третий по дход основан на изучении програм-

мы, полученной в результа те работы после дова тельног о компи-

лятора. Если такая программа содержит достат о чно «бо льшие»

арифметические выражения, то она может быть распараллеле-

на с помощью численных алгоритмов.

При рассмотрении вопросов разработки параллельных ал-

горитмов и языков для о днородных вычислительных систем

необходимо учитыв ать следующие соображ ения:

Режим параллельной обработки должен использов а ться

в основном для тех зада ч, которые не могут быть реализованы

достаточно эффек тивно (т.е. с нужной то чностью, временем ре-

шения) с помощью одной ЭВМ.

Распараллеливание вычислительного процесса необ хо ди-

мо для получения нужной эффективности решения сложных

задач; в общем случае не требуется приб ега ть к мак симально му

параллелизму.

Сх емы алг оритмов (программ) являются иерар-хически-

ми структурами, высший уровень которых – крупные блоки, а

низший уровень – опера торы (машинные к о манды).

Процесс распараллеливания долж ен начинаться с самого

высокого уровня; перех од на более низкий уровень происх одит

то лько в том случае, если не удалось достичь нужной степени

распараллеливания на данном уровне.

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

Рис. 4.1. Параллельный алгоритм вычислений.

...

... .

…

При разработке Р-алг оритм а главное внимание уделяется

выявлению циклов и распределению массивов. Испо льз уется 2

основные сх емы распараллеливания: групповая и конвейерная.

Все многообразие взаимодействий между ветвями Р-алгоритм а

мож ет быть сведено к шести основным процедурам:

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

ной ветви во все остальные).

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

ляционный обмен в цикле по ветвям.

3. Об мен сдвигом (передача информации из данной ветви в

следующую или пре дыдущую).

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

данной ветви в некоторые выделенные).

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

ветвей в одну выделенную).

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

ный порядок реализации операт оров во всех ветвях при выпо л-

нении обобщенног о условия.

Приведенные операторы обеспечив ают доступ к общим

данным и синхронизацию процессов в разных ветвях. Процеду-

ры обменных взаимо действий могут пополняться. В частности,

могут быть введены процедуры обобщенног о безусловного пе-

рехода, на чальной загрузки, с помощью которых мо жно иници-

иров а ть работ у системы.

Параллельные языки или языки высокого уровня, предназ-

наченные для записи Р-алг оритмов, отличаю тся от известных

языков средств ами задания обменных взаимодействий Р-ветвей:

системными операторами и системными программными функ-

циями. Вместе с обычными операт орами они образу ют набор,

позволяющий описыва ть как последова тельные, та к и параллель-

ные вычислительные процессы. Примерами этих языков могут

служить Бейсик, Фортран, Ассемблер.

Системные операторы, введенные в эти языки, позволяю т

задава ть взаимодействия ветвей Р-процесса на микро уровне. Это

освобо ждает программиста от необходимости знать структур у

системы, в частности, такие ком анды, как «прием», «переда ча»,

«настройка». Специальные опера т оры вво да-вывода обеспечи-

вают удобное задание распределения массивов по ветвям. В ка-

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

функции, опре деляющие зна чение максим ального и минималь-

ного элемента массива, с у мму всех значений м ассива, распреде-

ленного по ветвям, общее число ветвей и т.д. Для данных язы-

ков к аждая ветвь Р-программы оформляется как последова тель-

ная программа. Особенность такой последов а тельной програм-

мы – наличие операт оров обменных взаимо действий, которые

вво дятся в операционную систему в виде б локов или биб лио-

течных мо дулей. Библио те чные моду ли позволяю т использова ть

опера торы обменных взаимо действий в язык ах высокого уров-

ня. Описанный подход постепенного расширения последова тель-

ных алгоритмов и языков средствами параллелизм а позво ляет

полностью сохранить преемственность и при развитии язык ов

и алг оритмов в на правлении структ уризации приблизиться к

естественным наук ам.

Касаясь проб лемы язык а программирования, необходимо

отметить, что совершенно не обяза тельно разрабатыв ать для ПВС

специальный язык высокого уровня. Для того, чтобы писа ть Р-

программы, достато чно незна чительног о расширения язык а РL/

1 (или любог о друг ог о языка высокого уровня) с целью выпол-

нения сле дующих зада ч:

для программирования на существующей уже работаю-

щей ПВС,

для мо делиров ания на последова тельной м ашине процесса

выполнения Р-программ,

для анализа алг оритмов (в м а тема тических терминах).

Программа, выпо лняемая на любой ЭВМ, – это в к онечном

счете машинная программа, т.е. программа на соо тветств ующем

машинно м язык е. Но поскольку в распоряжении программиста

имеются компиляторы, программы обычно пишут на язык ах

высокого уровня. Языки высок ого уровня имею т следующие

преимущества:

Овладеть их синт аксисом нетрудно; программа же,

написанная на язык е высок ого уровня, по лучается более понят-

ной, с легк о воспринимаемой структ урой.

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

Так как эти языки универсальны, программу, на писанную

на одном из них, можно рассматривать как математическую

формулировку мет ода решения зада чи.

В литерат уре широк о представлены не только стандарт-

ные конструкции этих языков, но и некоторые специальные

конструкции, предназначенные для параллельной обработки

(например, существ ую т соответств ующие расширения Фортра-

на, Алгола 60 и Паскаля) [5].

В качестве наилучшег о кандидата, приго дног о для состав-

ления Р-программ (по крайней мере, программ по дчиненных

процессоров), был предло жен язык РL1. Имеются следующие

соображения в польз у РL/1:

Эт от язык мож ет быть реализован (и в основном уже

реализован) на с уществующих ЭВМ. Бо лее тог о, этот язык, воз-

мо жно, станет наиболее широко использу емым язык о м програм-

миров ания. Существу ет много к омпилят оров с этого языка (в

том числе оптимизирующих).

Эт о очень лаконичный язык, особенно когда дело касает-

ся обрабо тки вект оров и ма триц. Например, если А, В и С – это

ма трицы (n x n), то операт ор (А-В+С) означает поэлементное

слож ение м а триц В и С с за писью резул ьтата в А.

Язык РL/1 имеет ряд других полезных свойств, на пример

возможность работы с подчиненными задачами.

То, что зада чи , решаемые последова тельно-параллельно и

имеющие в основном арифметический характер, мо жно запрог-

раммирова ть на РL/1, не вызывает сомнений. Для тог о, чтобы

использов а ть РL/1 и в качестве языка программирования задач

управляющег о процессора, он долж ен дав ать воз мо жность реа-

лизовать сле дующие свойств а Р-задач:

Вся программа разбита на части, о дни из которых выполня-

ются последова тельно, др угие – параллельно. В памяти должна

храниться как инфор мация, о тносящаяся к каждой такой части,

так и своего рода «граф предшествования», описывающий

последова тельность выпо лнения частей, их расположение в па-

мяти и т. п., – эт ой информ ацией польз у ется управ ляющий про-

цессор (УП).

Та об ласть памяти, где записаны эти программы, должна

быть доступна для УП, но недоступна для подчиненных про-

цессоров (ПП).

В зада чу УП входят пересылки данных по шине, поэтому

он должен располага ть командами, которые обеспе чиваю т та-

кие пересылки. Пересылки не должны перекрываться по време-

ни.

УП до лжен принимать прерыв ания от всех ПП. Програм-

ма УП за пуск ается по сигналам от ПП. Б удучи запущенной, она

нах о дит о чередную по дзадачу и, поручив ее о дно му из ПП, пе-

ресылает некоторый файл в память этог о ПП, пересылает неко-

торые переменные между файлами неко т орых ПП или запуск а-

ет о дин или все ПП.

Нетрудно видеть, чт о язык управляющего процессора мож-

но реализова ть как некоторое расширение системного язык а (т.

е. языка ОС), поско льку он предпо лагает пересылку файлов,

обработку прерываний и за пуск по дчиненных процессов.

«Параллельный» РL/1 или РРL/1 должен быть определен

таким образо м, чтобы программы, написанные на нем, можно

было бы легко преобразовывать в программы мо делирования.

И как мы уже г о ворили, расширение существ ующег о языка для

применения ег о к «параллельному программированию» яв ляет-

ся широко распространенным приемом (таким образом были

расширены Фортран, Алго л и Паскаль). Точно таким же обра-

зом для системы РЕРЕ был разрабо тан язык РРОК, основанный

на Фортране [1]. Принимая за основу язык РL/1, необходимо

добавить в него следующие дополнительные возмо жности:

Индек сы в РРL/1 будут испо льзов аться не только для зада-

ния номеров э лемент ов м ассива, но и для указания но мера кон-

кретной лок альной памяти. В этом случае такой индек с ставит-

ся в ск обк ах слев а от имени переменной. Если зна чение индекса

в ск обк ах равно ну лю или же «лев осторонний» индекс вообще

отсутствует , то имеется в виду обращение к общей памяти.

Существу ют два способа хранения зна чений переменных

(особенно массивов) в лок альных устройствах памяти: под раз-

ными или по д о динаковыми именами. В общей памяти разме-

щается вектор С размерности m. Каждый ПП мо ж ет обраща ть-

ся только к своему «эк земпляру» переменной С; УП мо ж ет об-

раща ться ко всем эк земплярам этой переменной. Если все объяв -

ляемые переменные сопрово ждаются знак о м (#), то его можно

вынести за скобки. Каждый ПП знает св ой но мер; обращение к

своему номер у имеет вид (#Р). Ко личеств о ПП обозна чается в

программах УП как Р.

Поскольку рассылка информации всег да происходит из

общей памяти во все локальные устройства памяти, можно не

указыв а ть, к акие именно локальные устройства имеются в виду.

Программная мо дель до лжна состо ять из главной програм-

мы для УП, которая инициирует запуск программ ПП в соотв ет-

ствии с некоторой управ ляющей информ ацией (веро ятно, пре д-

ставленной в виде списков). Так как программы ПП работают в

параллель, их можно трак т о в а ть как процессы, иницииру емые

главной программой о дновременно. Эти процессы до лжны вза-

имодейств ова ть с главной программой. Так, некоторые из про-

цессоров, возможно, должны б удут ждать, пока не произойдет

нек о т орое со бытие или же пока не наст упит некот орое заранее

назна ченное время. Это (реальное) время до лжно имитирова ть-

ся в модели при помощи специального счетчик а времени.

Программы, написанные на РРL/1, можно транслирова ть

«один к о дно му» на язык 81МРБ/1 [IВМ 72] [5], поскольку эт о т

язык имеет сре дства :

Главная программа, на писанная на язык е 81МРБ/1, за пус-

кает или последова тельно, или параллельно некот орое число так

называемых процесс ов.

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

обработки списк ов.

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

Приостановленный процесс мож ет быть вновь активизи-

рован, если выполнилось нек о т орое условие (с обытие). Язык

позволяет мо делиров а ть весьма сло жные взаимодействия меж-

ду одновременно протекающими вычислительными процесса-

ми.

Для синхронизации выполнения всех программ (т. е. глав-

ной программы и процессов) использу ется сче тчик времени,

имитирующий реальное время.

К сожалению, язык 81МРБ/1 не настолько широк о извес-

тен, чтобы его описание можно было найти в любой книге по

вычислительной техник е, но имеется друг ой вых од из поло же-

ния – использов а ть средства для работы с по дчиненными зада-

чами, предусмо тренные в РL/1. Может быть, они не столь со-

вершенны и представляют для моделирования ПВС меньше

удобств, чем 81МРБ/1, но преимущество их заключается в том,

что они состав ляют часть стандартного РL/1, а следова тельно,

более доступны.

ОЦЕНКА ПРОИЗВОДИТЕЛЬНОСТИ

ПАРАЛЛЕЛЬНЫХ АЛГОРИТМОВ

Все программы делятся на сегменты согласно логическ ой

структуре соответств ующей задачи. Для выполнения к аждог о

сегмента программы необходимы различные ресурсы, и, чтобы

достаточно точно оценить потенциально воз мо жную произво-

дительность (выявить узкие места в распределении ресурсов),

необходимо рассмо треть каждый сегмент о тдельно. О днако для

того, чтобы на основе анализа от дельных сегмент ов получить

полезные показатели производительности, необ ходимо опреде-

лить относительную важность или вычислительную сложность

различных сегмент ов. Сложность может быть задана в терми-

нах числа арифметических операций в сегменте программы, но,

поск о льку вычислительная сло жность от дельных операций мо-

жет сильно различаться, такая мера оказывается не всег да по-

лезной. Поэто му в дополнение к ней целесообразно привлечь

еще о дну мер у сложности, основанную на числе машинных так-

тов, треб у емых для реализации сегмента программы. Ясно, что

оценки, основанные на числе тактов, не яв ляю тся не зависящи-

ми от ЭВМ, но поск о льку о тношение между сложностью опе-

раций и относительным быстро действием процессора и основ-

ного запоминающего устройств а меняются незначительно, с

этим недостатком можно смириться.

Просмотр программы позволяет без труда оценить число

параллельных процессов, имеющихся в данном сегменте. Эта

степень параллелизма обычно является функцией размера сис-

темы и, о чевидно, мерой по тенциальног о параллелиз ма сегмента

программы.

Чтобы объе динить по тенциальный параллелизм различных

сегментов программы, необ ходим неск о лько иной показа тель,

ко т орый назыв ается ускорение м. Он о тражает тот факт, что про-

грамма мож ет исполняться на произвольном числе m > 1 про-

цессоров. Этот показа тель часто использ уется также для тог о,

чтобы о харак теризов а ть потенциальный параллелизм програм-

мы.

Пусть T(m) – время, необходимое для выполнения парал-

лельных ветвей сегмента программы на m процессорах. Тогда

ускорение на m процессорах можно определить как T(1)/T(m).

Факторы уск орения всех сегмент ов программы можно объеди-

нить, использу я оценки вычислительной сложности програм-

мы.

Обычно при оценке общего уск орения на m процессорах

предпо лагается, что все они рабо тают с о динаковой скоростью.

В это м случае рас чет ок азывается сов сем простым. Если в дан-

ной параллельной вычислительной системе имеются процессо-

ры с различным быстродействием, то мо жно оценить общее

ускорение, использу я наряду с оценк ами сло жности к аждой ча-

сти различные уровни параллелизма различных сегментов про-

граммы. Важно отметить, что это т показа тель ускорения будет

отража ть эф фекты , обычно называемые потерями на синхрони-

зацию. Так, если в программе имеется сегмент, содержащий две

параллельные ветви одинаковой длины, исполняемые на про-

цессорах с различным быстродействием, и следующая последо-

ва тельная ветвь может быть на ча та лишь после окончания вы-

по лнения этих двух параллельных ветвей, то один процессор

закончит св ою работу раньше друг ого. Поэтому первый процес-

сор б удет вынужден ждать, пока закончит свою работу в т орой

процессор, после чего один из них на чнет выполнять следую-

щую последов а тельную ветвь. Возникающая задержка об ъясня-

ется необ ходимостью синхронизации процессоров перед на ча-

ло м выполнения сле дующег о множества ветвей (в рассма трива-

емо м случае – последов а тельной ветви), и ее влияние учитыва-

ется в показателе ускорения.

В приве денных рассуждениях пре дпо лагалось, в частности,

что объем вычислений не зависит от числа работающих про-

цессоров. О днако известны алг оритмы, в которых об ъем вычис-

лений непредсказ у емо зависит от струк туры параллельног о ис-

полнения. Заметим, что общие данные являются общим ресур-

сом. Их можно разделить на два типа:

чувствительные данные: стр уктуры данных, к ко т орым в

каждый момент времени может обраща ться только о дин про-

цессор. Примерами могут служить общий с четчик, значение

ко т орого всегда должно соответствовать числу обращений к

нему, или расписание, разделяемое процессорами;

нечувствительные данные: структуры данных, доступ к

ко т орым или изменение которых могут о дновременно осуще-

ствлять несколько процессоров, или структ уры данных, кото-

рые в о дной части доступны одно му процессору, а в друг ой –

друго му процессору.

Все данные от ображаю тся на физические ресурсы памяти,

которые на к аждом цикле своей работы допуск ают т о лько одно

обращение. Кро ме того, чувствительные стр укт уры данных яв-

ляются логическими ресурсами, которые в полно м цикле «дос-

туп-мо дифик ация» допускаю т лишь о дно обращение. Доступы

к логическим ресурсам до лжны быть защищены средствами

синхронизации. При эт о м не имеет значения, б удут ли эти сре д-

ства доступа реализованы аппара тно или программно. Все об-

ращения к общим ресурсам приво дят к накладным расх одам,

имеющим два компонента:

к о мпонент, определяемый мех анизмо м доступа к ресур-

су; например, доступ к данным, нах одящимся на диск е или в

локальной памяти друг ого процессора, треб у е т большег о вре-

мени, чем доступ к локальной памяти своег о процессора;

к о мпонент, возникающий из-за конк уренции процессо-

ров, выну жденных ожида ть, когда общий ресурс станет доступ-

ным.

Заметим, что если общие данные хранятся в физически раз-

личных ресурсах, то анализ долж ен быть прове ден для к аждого

ресурса отдельно.

Средство м доступа к физически общим данным мож ет слу-

жить общая шина и общий модуль памяти или индивиду альный

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

прот окола межпроцессорного обмена. Механизмо м доступа к

логически разделяемому ресурсу является средство синхрони-

зации (хотя в конечном счете для доступа к данным должно быть

использовано некоторое физическ ое средств о). К аждая логичес-

ки независимая общая стр уктура данных является отдельным

общим ресурсом, и «спор» за каждый из них происх одит неза-

висимо от остальных ресурсов, если то лько вычислительная