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

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

выявил неск о лько обобщающих особенностей этог о направле-

ния исследований:

1. Несмотря на разнообразие конкретных постановок задач

распараллеливания, возник ающих на различных уровнях и эта-

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

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

дения эффективног о преобраз ования программ или специфика-

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

осуществляющие, в ообще гов оря, асинхронную обработку дан-

ных со взаимо действием над общей памятью. Понятие общей

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

между операт орами и сформулировать проблему организации

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

ными от памяти в обычном смысле этого слова .

2. При рассмо трении всего мног ообразия методов оказалось

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

да чи распараллеливания. Особенно отчетлив о прослеживается

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

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

первона чально запрещается выполнение всех вычислительных

акт ов и для инициации какого-либо действия нужно дать указа-

ние об его выполнении. Вт орой тип к онтроля применяется к сре-

де вычислителей, осуществляющих св обо дное х аотическ ое фун-

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

либо ак тов. Оказалось, чт о первый и в т орой ме ханиз мы контроля

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

помощью одног о и того же ма тема тического аппара та. К онкрет-

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

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

леливании массовых вычислений. Помимо того, что трактовк а

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

нять приро ду вещей, это дает еще и определенную техническую

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

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

3. Обнаружилось, что в наиболее «чистых» постановках

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

пиально разрешимой. Речь идет о задаче максимального распа-

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

пускающую все воз мо жные вычисления, не нарушающие экви-

валентность исх одной сх еме. Так, о дин из результа тов можно

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

стрых вычислений», т.е. без учета особенностей интерпретации

быстрее осуществлять все необходимые вычисления в принци-

пе нельзя.

И, нак онец, следует отметить, что тот или иной мето д рас-

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

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

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

результат ов и представлять собой синтез некоторой совок упно-

сти универсальных и специальных мет о дов.

ДВА ПОДХОДА К РАСПАРАЛЛЕЛИВАНИЮ ВЫЧИСЛЕНИЙ -

ПАРАЛЛЕЛИЗМ ДАННЫХ И ПАРАЛЛЕЛИЗМ ЗАДАЧ

В наст о ящее время существ ую т два основных подхода к рас-

параллеливанию вычислений. Эт о параллелизм данных и парал-

лелизм зада ч. В англоязычной литерат уре соответств ующие тер-

мины data parallel и message passing [3]. В основе обоих подхо-

дов лежит распределение вычислительной работы по доступ-

ным пользова телю процессорам параллельного к о мпьютера. При

этом прих одится решать разнообразные проблемы. Прежде все-

го это достат о чно равномерная загрузка процессоров, так как

если основная вычислительная работа б удет ложиться на один

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

тельных вычислений и никаког о выигрыша за счет распаралле-

ливания зада чи не будет. Сбалансированная рабо та процессоров

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

ции параллельных вычислений. Другая и не менее важная про-

б лем а - скорость обмена инфор м ацией между процессорами.

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

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

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

тратиться впуст ую на ожидание инфор мации, необ хо димой для

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

собы программирования различаются мето дами решения этих

дв ух проблем. Разберем их более подробно.

1. Параллелиз м данных. Основная идея по дх ода, основанно-

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

ция выполняется сраз у над всеми элементами массива данных.

Различные фрагменты таког о м ассива обраба тываю тся на вект ор-

ном процессоре или на разных процессорах параллельной систе-

мы. Распределением данных между процессорами занимается

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

этом случае чаще всего выполняется уже на этап е к о мпиляции -

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

программиста в это м случае обычно сво дится к заданию опций

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

тив параллельной к о мпиляции, использов анию специализирован-

ных язык ов для параллельных вычислений. Наиболее распрост-

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

высокопроизводительный ФОРТРАН (High Performance

FORTRAN) и параллельные версии язык а С (например, С*).

Более детальное описание рассматриваемог о по дхода по-

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

Обрабо ткой данных управляет о дна программ а;

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

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

туры данных, доступа к памяти и межпроцессорного обмена

данными от него скрыты;

Слабая синхронизация вычислений на параллельных

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

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

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

граммных конструкций - их синхронизация. Каждый процес-

сор выполняет один и тот же фрагмент программы, но нет га-

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

выполняется о дна и та же машинная к о манда;

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

няются одновременно на всех доступных данной программе

процессорах.

Т аким образом, в рамк ах данног о по дх ода от программиста не

требу ется больших усилий по векторизации или распараллелива-

нию вычислений. Даже при программировании сложных вычис-

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

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

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

Подход, основанный на параллелизме данных, базируется

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

операций: операции управления данными; операции над масси-

вами в целом и их фрагментами; условные операции; операции

приведения; операции сдвига; операции сканирования; опера-

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

Рассмотрим подробнее эти базовые наборы операций.

У правление данными. В опре деленных ситу ациях возник а-

ет необ ходимость в управ лении распределением данных между

процессорами. Это мо ж ет потребоваться, например, для обес-

печения равномерной загрузки процессоров. Чем более равно-

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

будет работа ко мпью тера.

Операции над массивами. Аргументами таких операций

являются массивы в целом или их фрагменты (се чения), при этом

данная операция применяется одновременно (параллельно) ко

всем элементам массив а. Примерами операций такого типа яв-

ляются вычисление поэ лементной с уммы массив ов, умно жение

элемент ов массива на скалярный или векторный множитель и

т.д. Операции могут быть и бо лее сло жными - вычисление фун-

кций от массива, например.

Условные операции. Эти операции могут выполняться лишь

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

то опре деленно му условию. В сето чных методах это мо ж ет быть

четный или нечетный номер строки (сто лбца) сетки или нера-

венство ну лю э лемент ов ма трицы.

Операции приведения. Операции прив едения применяются

ко всем элементам массива (или его се чения), а результа том их

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

тов массива или максимальное зна чение его элемент ов.

Операции сдвига. Для эф фективной реализации некот орых

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

вов. Примерами служат алгоритмы обработки изображений,

коне чно-разностные алг оритмы и неко т орые другие.

Операции ск анирования. Операции ск анирования еще на-

зываются префик сными/су ффиксными операциями. Префиксная

операция, например, суммирование, выполняется следующим

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

рез ульта т очере дног о суммиров ания заносится в о чередную ячей-

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

ки совпадает с числом просуммиров анных элемент ов исх одно-

го массива.

Операции пересылки данных. Это, например, операции пе-

ресылки данных между массивами разной формы (т.е. имею-

щими разную размерность и разную протя женность по каждо-

му измерению) и неко т орые другие.

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

то использ уются специализированные языки - CM FORTRAN, C*,

FORTRAN+, MPP FORTRAN, Vienna FORTRAN, H. P. FORTRAN

(основанный на языке программирования FORTRAN 90), чт о свя-

зано с наличием в последнем удобных операций над массивами).

2. Паралле лиз м задач. Стиль программирования, основан-

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

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

по дзада ч и каждый процессор загру жается своей собственной

подзадачей. К омпью тер при этом представляет собой MIMD-

машину. Для каждой подзадачи пишется сво я собственная про-

грамма на обычном язык е программирования, обычно это Фор-

тран или С. Чем бо льше по дзадач, тем большее число процессо-

ров можно использов а ть, тем бо льшей эффективности мо жно

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

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

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

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

ление данных между процессорами и подзадачами и обмен дан-

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

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

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

нованно м на параллелизме данных, это т подход более трудоем-

кий, поск о льку с ним связаны сле дующие проб лемы:

повышенная трудоемкость разработки программы и ее

от ладки;

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

мерную загрузк у процессоров параллельного ко мпьютера;

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

ми между зада чами, т.к. пересылка данных - наиболее «время-

емкий» процесс;

повышенная опасность возникновения т упиковых ситуа-

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

не прих одит к месту назначения.

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

ются большая гибкость и большая свобо да, предоставляемая

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

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

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

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

(Message Passing Interface), PVM (Parallel Virtual Machines). Эти

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

ют в ис ходных кодах.

ПРЕОБРАЗОВАНИЕ ПОСЛЕДОВАТЕЛЬНЫХ ПРОГРАММ

В ПАРАЛЛЕЛЬНЫЕ

В многопроцессорных системах различных типов от дель-

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

выполняться параллельно. В тех случаях, когда программы на-

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

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

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

ведение дополнительного анализа.

В зависимости от типа вычислительного процесса во вре-

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

раллеливания. Поэто му дать общую сх ему фазы распараллели-

вания для любой системы трудно. Однако можно выявить ти-

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

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

конкретной системы. Перечислим эти этап ы.

1. Распараллеливание линейных участк ов. Линейным учас-

тк о м программы назовем часть программы, операт оры которой

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

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

ограничен начальным и конечным операт орами. Начальным

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

выполняется по крайней мере одно из следующих условий: у

опера т ора не один непосредственный предшественник; у непос-

редственног о предшественника более о дного непосредственно-

го последова теля. К оне чным оператором линейного участка

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

о дног о из следующих условий: у операт ора не один непосред-

ственный последователь; у непосредственног о последов ателя

опера тора больше одног о непосредственног о предшественни-

ка. Исходя из этих определений, легко построить алгоритм на-

х ождения линейных участк ов. Внутри линейног о участк а распа-

раллеливание может производиться по операт орам, а внутри

опера т оров - распараллеливание арифметических выражений.

Распараллеливание по операт орам позволяет при наличии вы-

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

что ускоряет проведение вычислений.

2. Р аспаралле ливание циклов. Границы циклов нах о дятся по

фор мальным признакам описания циклов в соответствующих язы-

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

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

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

няются век торные операции. Поскольк у векторные операции

выполняются параллельно над в семи или частью элемент ов век-

торов (в зависимости от имеющихся вычислительных ресурсов),

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

3. Распаралле ливание по процесс ам. В вычислительных си-

стемах с мно жественным по током команд о дновременно мо ж ет

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

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

между собой может быть различна. Каждый пот ок к о манд мо-

жет быть совершенно независимой задачей. Потоки команд мо-

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

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

по дзада ча – это, как правило, доста т о чно большая программа,

слабо связанная с др угими подзада чами по управлению.

Нак онец, программа мож ет быть разбита на относительно

небольшие части, достат о чно тесно связанные между собой как

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

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

вем процессами. Разбиение программы на асинхронные парал-

лельно выполняемые процессы мо жет оказа ться существенным

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

4. Р азбиение программы на слабо связанные участки. Та-

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

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

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

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

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

это время, хотя, конечно, повлияет на полноту распараллелива-

ния. Мето д разбиения программ на слабо связанные участки

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

лам (вычислительным машинам) локальной сети. Он может

позволить сокра тить число межмашинных обменов.

ПАРАЛЛЕЛЬНАЯ РЕАЛИЗАЦИЯ

ЦИКЛИЧЕСКИХ УЧАСТКОВ ПРОГРАММ

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

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

х о дов - универс ального и специального. При универсальном по д-

ходе нас не интересует со держание тела цикла. Оно рассматрива-

ется как нек о торый «черный ящик», имеющий мно жество вх о дов

и множество выхо дов. Дополнительно на тело налагаются нек о-

торые условия, г лавное из них - отсутствие отсылок вне тела цик-

ла по операт орам условного или безусловног о перехо дов. При

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

основе лишь формального анализа информационных св язей, по-

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

на чально му при любой интерпретации операторов тела. Унив ер-

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

ние в распараллеливающих трансляторах и в меньшей - на анализ

вычислительног о мето да или алгоритма.

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

менее зафик сированную фор му тела цикла и область, над кото-

рой производится вычисление. Нередко параллелизм извлек а-

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

метной области. Методы этог о типа также можно испо льзов а ть

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

параллелизм, чем универсальные. Но это треб уе т более глубо-

кого анализа для опре деления специфических к онструкций. Боль-

шое разнообразие этих конструкций требует и большей предв а-

рительной рабо ты по анализ у их распараллеливаемости. Кроме

того, естественно, увеличиваются объем транслятора и время

трансляции. Это заставляет рассматривать специальные мето-

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

программировании.

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

либо их классификацию, так как в каждо м из них присутств у ет

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

лать. Ключом классификации выберем тип преобразования

структурных данных. Можно различить четыре типа обрабо тки

и соответственно четыре типа циклов.

1. Тип «скалярный ® скалярный». В циклах этог о типа не

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

за ть, что он либо эквивалентен нек о т орой циклическ ой к онст-

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

быть, достато чно сложной составной операции вида: WHILE P

DO x : = f (x). Стандартный прием «извлечения быстро действия»

для такого цикла - сдваив ание, т.е. следующая замена:

WHILE P DO x : = f (f (x)).

Выигрыш получается за с чет того, чт о к о мпозиция ff вы-

числяется, как правило, быстрее, чем дважды f.

На пример, f есть линейное преобразование: x : = ax + b.

Для вычисления двух таких итераций требуется два умно ж ения,

два сложения и два обращения к памяти. В то же время итера-

ция x : = a(ax + b) + b = a

x + ab + b при совмещении операций

, ab и предпо ло ж ении, что время умно жения бо льше времени

слож ения, требует дв ух умножений, одног о слож ения и одног о

обращения к памяти. Этот прием может быть пов торен произ-

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

ного сдваивания.

2. Тип «скалярный ® векторный» производит на основе

нек о т орой скалярной информации генерацию нек о т орог о мас-

сива, зависящего от параметра цикла i. Пример таког о цикла

можно по лучить, мо дифициров ав цикл WHILE P DO x : = f (x) :

WHILE P DO x (i) : = f (x (i - 1)); i = i + 1.

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

ко оконча тельное зна чение х, но и со храняются все промежу-

то чные.

3. Тип «вект орный ® скалярный» задает выполнение неко-

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

получается скаляр. Простейший пример - «свертывание» мас-

сива посредство м нек о торой ассоциативной операции A:

х = х (1) Е х (2) Е х (3) Е ... Е х (n).

Конструкции такого рода х орошо изучены и реализу ются

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

рифмическому дереву.

4. Тип «век т орный ® векторный». Преобразование инфор-

мации, задаваемое такими циклами, заключается в перерабо тк е

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

смотрим упорядо чение э лементов массива Х путем вычисления

позиции p(i) i-го элемента в упорядоченном массиве:

FOR i = 1, n DO,

FOR j = 1, n DO,

IF x (j) < x (i) THEN p(i) : = p(i) + 1.

Цикл вычисляет для к аждог о i число p(i) э лемент ов масси-

ва Х, строг о меньших x(i). Первоначально массив Р ну левой. В

итоге p(i) будет указыва ть номер элемента, после которог о до л-

жен сто ять x(i). Параллельную версию цикла можно записат ь

так :

FOR i = 1, n DO PARALLEL p(i) : =

kx x

().<

∑

Для каждог о i одновременно суммир ую тся все рез уль та ты

сравнений, а вычисление p(i) мо жно организова ть по типу пол-

ного логарифмическ ого дерева.

Характерной особенностью всех пере численных примеров

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

чины порядка n (в последнем случае - даже n

) до величины O (log

n). Но никакой даже самый глубокий формальный анализ не по-

зволил бы осуществить эти преобразования без обращения

«внутрь» тела цикла. Во всех случаях использ овались некоторые

специфические зак оны: ассоциативность, дистрибутивность, а в

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