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

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

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

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

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

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

2. На рынк е нет спроса на эти системы. Другой т упик: отку-

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

раллельные структ уры могут существова ть?

3. Ограниченная область применения; отсутствие «парал-

лельной» м а тем а тики ; недостат ок знаний о возмо жности разби-

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

бо тку язык а и программ.

Еще о дно нем аловажное для синтеза ПВС заме чание мо ж-

но сформулирова ть следующим образо м: «Хороший разработ-

чик ЭВМ должен в первую очередь зна ть задачи потенциальных

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

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

разработку аппаратуры и программ для проектиру емой ЭВМ».

Область применения ПВС не так ограничена, как это

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

дующие области приложений: задача фильтрации, трасси-

ровка, поиск документов, манипулирование файлами, управ-

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

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

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

распознавание образов, обработка изображений, динамичес-

кое программирование, решение дифференциаль-ных урав-

нений и выполнение матричных операций. Таким образом,

область применения ПВС очень разнообразна и включает в

себя большинство задач, т ребующих большого объема вы-

числительной работы.

КЛАССИФИКАЦИЯ АППАРАТНЫХ СРЕДСТВ ПВС.

КЛАССИФИКАЦИЯ ФЛИННА.

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

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

ных является классификация Ф линна. В ее основ у положено

описание работы компьютера с пот оком ком анд и пот оком дан-

ных. По Флинну принят о классифициров а ть все в озмо жные ар-

хитектуры компью теров на четыре катег ории (см. рис. 1.1):

SISD (Single Instruction Single Data) – о дин поток к ом анд,

о дин пот ок данных;

SIMD (Single Instruction Multiple Data) – о дин по ток команд,

мног о потоков данных;

MISD – много пот оков к о манд, один поток данных;

MIMD – много потоков команд, много потоков данных.

SISD-к омпью теры – эт о обычные, традиционные последо-

ва тельные к о мпью теры, в которых в каждый момент времени

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

(числовым или каким-либо другим значением). После доват ель-

ная ЭВМ выбирает ком анды и операнды из памяти, выполняет

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

манды образуют поток к о манд, а операнды – поток данных между

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

ная ЭВМ – это машина, содержащая память – для хранения про-

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

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

ций на арифметическом логическ ом устройстве (АЛУ); АЛУ,

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

памяти, и за писывает резуль таты в ту же память. При это м адре-

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

управления.

SIMD-компьютеры состоят из одного командного про-

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

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

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

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

ются данные, контроллер рассылает на все процессорные эле-

менты команду, и эта команда выполняется на нескольких или

на всех процессорных элементах. Каждый процессорный эле-

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

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

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

лений. До половины логических инструкций обычного про-

цессора связано с управлением выполнением машинных ко-

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

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

ций. В SIMD-компьютере управление выполняется контрол-

лером, а «арифметика» отдана проце ссорным элементам.

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

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

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

сорам, которые выполняют их синхронно, но каждый – над

своими собственными данными.

К онвейерные ЭВМ мо жно о тнести к MISD-системам (мно-

го пот оков ко манд, о дин поток данных), учитывая, что каждый

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

частях конвейера. В этом случае S

обозна чают к этапов обра-

ботки о дной ком анды. Когда на этапе S

заканчивается вычисле-

ние ре зультата, он передается на этап S

i+1

, но мо жет случиться,

что в этот момент S

i+1

еще про до лжает работать над предыду-

щим э лементо м данных. Поэтому этапы должны о тделяться друг

от друга б у ферами. В данной системе ПЭ (процессорные эле-

менты) – эт о не процессоры, а скорее части одног о центрально-

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

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

Му льтипроцесс орные системы, АПВС и СПВС (асинхрон-

ные и синхронные) – это представители MIMD-систем (много

пот оков команд, много потоков данных). Эта ка тегория архи-

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

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

метричные параллельные вычислительные системы, рабочие

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

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

цессорные элементы (ПЭ) работают асинхронно. В СПВС ПЭ

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

управляющий процессор (УП), его программа работает асинх-

ронно с программами ПЭ. Мультипроцессорные системы и

АПВС совсем не имеют УП, и поэт ому их процессоры могут

работать над абсолютно различными заданиями. Данные же,

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

системы являются MIMD-системами.

РЕШАЕМЫЕ ЗАДАЧИ И ИХ КЛАССИФИКАЦИЯ

MD MD

ПЭ ПЭ SI ПЭ ПЭ ПЭ MI ПЭ

SIMD УУ УУ УУ

MIMD

D S

D SD

ПЭ ПЭ ПЭ MI

MISD

Дешифратор команд

Устр-во управления

Арифметическое

устройство

Дешифратор адресов

ПАМЯТЬ

Рис. 1.1. Последовательная и параллельные вычислительные системы.

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

ной системы, состоящей из нескольких процессоров, а именно:

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

тног о наращивания и о чень высокую пропускную способность,

необходимо уметь представить решаемую задачу в виде несколь-

ких параллельных взаимодейств ующих процессов. На сег о дняш-

ний день эт о достигнуто лишь для небольшог о числа специали-

зированных задач и специалистами, х орошо знающими эти за-

да чи. Одной из таких задач является пре дсказание погоды – вы-

полнение наб людений и обработка по лученных данных парал-

лельно в разных географических районах (одновременно и не-

зависимо, т.е. разбиение зада чи по пространств у и по данным) с

последующим централизованным сог ласов анием рез уль тат ов.

От личительной чертой этой прикладной зада чи яв ляется то, что

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

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

параллелизмо м и называют их p-задачами (не использ у я при это м

никаким образом числовог о значения p). Другой от личительной

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

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

пространству.

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

это зада ча противорак етной обороны (ПРО), к от орая обычно сво-

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

между собой и их классификации. При это м машина должна

инициировать отдельный файл для каждого обнаруженного

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

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

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

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

что в ответ на каждый отраженный сигнал (от неск о льких сотен

до неск ольких тысяч таких сигналов в секунду) ну жно сгенери-

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

сдела ть это ну жно за заданный временной интервал (обычно от

25 до 200 мсек). Простой расчет показывает, что так а я зада ча

ник оим образо м не мож ет быть решена на традиционных пос-

ледовательных ЭВМ, даже на самых больших и мощных. Ре-

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

данными о цели, хранящимися в файле. Сравнение m отражен-

ных сигналов с n целями при обычном способе сравнения тре-

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

ние произво дится ассоциативно. Такая ассоциативная память,

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

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

ме РЕРЕ, применяемой для решения данной зада чи.

В добавление к трем основным требованиям, ко торые за-

да ча ПРО предъявляет к обработке данных (выпо лнение срав-

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

лах), ЭВМ должна иметь чрезвычайно высокую надежность, и

жела тельно, чтобы эта надежность была неотъемлемой чертой

архитектуры ВС. Параллельная ассоциативная архитект ура по-

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

случае, когда о т дельные параллельно работающие элементы

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

не влияет на работу других элемент ов и на решение зада чи в

целом .

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

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

ти. В терминах этой классифик ации задача ПРО является неав-

тономной p-задачей. Кро ме нее к неав тоно мным p-задачам мо ж-

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

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

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

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

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

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

рации данных по мере необ ходимости. Телефонная к о ммутация

также является неав т оно мной p-задачей.

К ав т ономным не p-задачам относятся среди прочих: обра-

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

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

К наиболее важно му случаю – неав тоно мным не p-зада чам –

относятся сле дующие зада чи: управление распределением э лект-

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

ления в реальном масштабе времени (управление реальными про-

цессами), обработка изображений и распознавание образов, не-

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

гических и других систем, управление транспорто м (особенно

воз душным), дифференциальные анализат оры (для целей моде-

лирования, к о торые в нек от орых военных прилож ениях работа-

ют со ск оростью, превышающей темп реального времени).

Т аким образом, в терминах выбранной классификации мож-

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

ав тоно мные , p-задачи и не p-зада чи), для решения которых це-

лесообразно и, более того, необ х одимо использова ть ПВС.

ПРИНЦИПЫ РАСПАРАЛЛЕЛИВАНИЯ

ВЫЧИСЛЕНИЙ

ЗАДАЧИ РАСПАРАЛЛЕЛИВАНИЯ И ИХ АКТУАЛЬНОСТЬ

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

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

ки бо льшог о количества быстро поступающей инфор мации оп-

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

направ лений на современном этапе развития науки и техники. С

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

раллеливание алгоритмов обработки информации. От ее реше-

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

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

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

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

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

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

ботки информации. Опре деление классов алг оритмов, допуск а-

ющих распараллеливание на заданном уровне и позволяющих

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

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

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

лительных сре дств для решения зада ч в реальном времени. Эт о

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

разраба тыв аемой вычислительной системы. Такое соответствие

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

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

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

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

М у ль тиобрабо тка информации, архитек тура му ль типроцес-

сорных систем, место и масштабы «ручног о» и ав т о ма тическо-

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

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

работчиков и пользова телей [2]. С одной стороны, естествен-

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

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

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

ледова тельный характер мышления человек а, мног о летний опыт

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

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

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

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

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

мощных многопроцессорных вычислительных систем и сетей

ЭВМ, яв ляются еще о дним важным дово до м в по льз у авто м ати -

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

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

Следу ет отметить, чт о в связи с повышением мощности и

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

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

ливания) на различных операционных уровнях. Важное место в

этой проблем а тике занимают теоретические вопросы, вклю ча-

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

лентности программ, опре деление степени параллелизма и син-

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

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

ного параллелизма и др.

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

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

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

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

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

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

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

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

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

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

при мелк облочно м распараллеливании. Кро ме того, имеются

алгоритмы микрораспараллелив ания, сх емная (либо программ-

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

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

ющей при этом проблемы параллельного программирования,

о дной из важнейших составных частей которой является зада ча

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

непосредственно вычислений. Первона чально под распаралле-

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

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

новременно на неск о льких процессорах. В насто ящее время это т

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

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

тект уре конкретног о или гипотетического вычислительног о ком-

плекса.

Общая проблема «подг онки» струк туры программы по д

архитект ур у ЭВМ не является новой. Известны различные ме-

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

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

устройств вво да-вывода и т.д. Специфика обрабо тки, связанная

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

Разные типы архитектур об условили разные грани постановки

задачи распараллеливания. Так, для конвейерных ЭВМ ак ту аль-

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

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

во льно большое время. Поэтому наиболее эффективно на кон-

вейерных ЭВМ реализую тся программы, состоящие из длин-

ных серий однотипных операций и как можно меньшег о числа

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

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

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

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

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

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

ее пов т оряющих ся участков. Это приво дит к образов анию «вер-

тикальных» серий о дно типных операций, которые, в частности,

могут быть выполнены и «горизонтально» в к онвейере. Эт о лишь

о дин пример преобразования программ, который можно трак-

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

Характерными особенностями современных мето дов рас-

параллеливания являются сле дующие:

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

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

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

мере освобождения треб уемого оборудов ания;

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

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

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

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

результир ующая программа должна облада ть наилучши-

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

Преобразование распараллеливания, как правило, произво-

дится в два этапа. На первом эта пе «вскрывается» и фик сиру ется

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

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

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

ЭВМ. На любо м из этих этапов можно использов ать два подход а:

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

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

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

к онкретным вычислительным к о мплексо м. При универсальном

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

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

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

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

(алгоритма), выполняющей ав т о матическ ое преобразование пос-

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

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

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

Вычислительные средств а классифицирую т такж е дово льно гру-

бо, выделяя лишь их типы или схемы архитект уры ЭВМ. Т аким

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

устойчивые зак оно мерности и разраба тываю тся наиболее общие

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

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