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

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

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

ми на о дин контроллер или одно средств о синхронизации. Дос-

тупность к аждог о общего ресурса ограничена. Если общий темп

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

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

вызывает ув еличения уск орения. Поэтому каждый общий ресурс

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

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

граммах:

максим альное число процессоров =

=1 / (темп за просов * время цикла ресурса).

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

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

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

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

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

сурсов.

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

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

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

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

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

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

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

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

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

процессоров, чт о определяется особенностями вычислительной

системы, то возникающие эффек ты можно оценить аналогич-

ным образом.

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

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

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

ветви. Тогда в общем случае по алгоритму можно определить

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

цессоров (или, по крайней мере, максим альное их число). Осо-

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

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

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

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

щих из-за необ ходимости разделения ресурса.

Возмо жности конкретной параллельной вычислительной

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

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

ной системы. Однако если все системы близки по своим воз-

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

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

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

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

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

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

ства алгоритмов.

КОЛИЧЕСТВЕННЫЕ ХАРАКТЕРИСТИКИ СТРУКТУР

ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ

Существу ет неск о лько по дх одов к построению количествен-

ных характеристик струк тур вычислительных систем [6].

Выбираются два параметра – длина основного машинног о

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

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

ного разряда множества слов v, т. е. ширина обраба тываемог о

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

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

ность этих параметров (w, v). Тогда получаем:

а) (1, 1) – по лностью последов а тельная обработка о дног о

бита информ ации за другим (одноразрядный процессор);

б) (w, 1) – последова тельная обработк а w-разрядных слов

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

ном процессоре (w>1);

в) (1, v) – последовательная обработк а разрядных срезов

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

да множества слов (v>1) как, например, в системах с ассоциа-

тивными процессорами;

г) (w, v) – полностью параллельная обрабо тка всех w разря-

дов каждог о из v слов о дновременно (v > 1, w > 1).

При по мощи этой дв умерной характеристики максимально

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

обычной о днопроцессорной системой IBM 360/50 (для основ-

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

мы с ансамб лем процессоров РЕРЕ, одним квадрант о м матрич-

ной системы ILLIAC IV или о дним моду лем ассоциативной си-

стемы STARAN [5, 6].

Характеристики параллельности стр укт ур в совокупности

с часто той синхронизации работы устройств вычислительных

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

в более общем случае, мак сим альную полосу пропуск ания, ко-

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

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

за единицу времени.

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

ственно связаны с классификацией вычислительных систем.

Действительно, системы с характеристик ами (1, 1) составляю т

класс ОКОДР; системы с характеристик ами (w, 1), где w>1, –

класс ОКОДС; с харак теристик ами (1, v), где v > 1, относятся к

класс у ОКМДР, а с харак теристик ами (W, V), где w> 1 и v > 1,

классифициру ются нео днозначно.

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

лизм а структур вычислительных систем. Отметим, что ширина

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

систем, таких как обычные однопроце ссорные, с ассоциа-

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

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

ным число м одновременно (параллельно) обраба тыв аемых слов

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

Характеристики структур систем в виде двоек чисел (w v)

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

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

ширина обрабатыв аемог о разрядног о среза v мож ет быть пред-

ставлена как количество процессоров в мног опроцессорной си-

стеме и как количество обраба тывающих процессоров в мат-

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

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

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

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

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

гопроцессорными системами и ма тричными системами и т. п.

Подобные трудности встре чаются при попытк ах состав ления

харак теристик для структ ур магистральных систем. Таким об-

разом , характеристики струк тур систем в виде двоек чисел (w, v)

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

поток о м к о м анд, т. е. систем классов ОКОД и ОКМД.

Другим естественным и простым подходом к построению

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

зование двоек чисел (k, n), где k и n – ко личества потоков ком анд

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

но связаны с классификацией систем в зависимости от един-

ственности и мно ж ественности потоков команд и данных. Они

применяются в ряде рабо т.

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

ночными пот оками команд и данных ОКОД (обычные процес-

соры), с одино чным потоком ко м анд и множ ественным пото-

ком данных ОКМД (ассоциативные и ма тричные системы, сис-

темы с ансамб лем процессоров и с векторным потоком данных),

с множ ественным потоком команд и одиночным потоком дан-

ных МКОД (магистральные системы) и с множ ественными по-

токами команд и данных МКМД (мног о машинные и многопро-

цессорные системы) – характериз у ются двойками целых чисел

(1,1), (1,n), (k, 1), (k,n) соответственно, где k > 1 и п > 1. Здесь,

в от личие от предыдущего по дхода, фактически указыв ается

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

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

чае, количество обрабатыв ающих процессоров (n = v), но при

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

не находит отражения.

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

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

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

ние.

Рассмотрим такой ко мбиниров анный по дхо д. В качестве

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

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

щие. Описание до лжно о хв а тыв а ть широкий круг вычислитель-

ных систем всех четырех классов ОКОД, ОКМД, МКОД и

МКМД, вклю чая обычные процессоры, ассоциативные и мат-

ричные системы, магистральные системы, многомашинные и

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

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

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

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

вать соотношениям между струк турами. При этом для каждой

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

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

харак теризов а ть не то лько собственно струк тур у и ее воз мо жно-

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

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

структур алг оритмов и программ.

В качестве основной цели описания примем количествен-

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

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

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

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

ны ниже.

Обработка первого уровня осуществляется в устройстве

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

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

гие регистры. Арифметик о-логическое устройство по лучает вне-

шние управляющие сигналы от устройства управ ления, выраба-

тывает соотв етств ующую исполнительную последов а тельность

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

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

разрядов данных (третий уровень обработки).

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

о дно или несколько устройств управления. Каждое устройство

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

кими арифметико-логическими устройствами. Наконец, каждое

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

группу разрядов (слово), хотя в ряде простейших случаев оно

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

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

тельная, так и параллельная обработк а. В соответствии с этим

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

ченной тройки: t(a) •= (k, d, w), где а — наименов ание или тип

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

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

полняемых программ в системе; d – количество арифметико-

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

ления; w – к о личество разрядов, содержимое которых обраба-

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

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

личины k и w имеют тот же смысл, что и в описаниях для двух

первых подходов, а величины v, k и d связаны соотношением v =

k - d для случая, когда арифметико-логические устройства по де-

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

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

при построении троек (k, d, w).

Рассмотрим теперь кратко вопросы соответствия описания

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

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

Параллелизм независимых ветвей задачи (первый тип) со-

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

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

ниваясь между собой рез ультатами.

Параллелизм смежных операций (вт орой тип) состоит в том,

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

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

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

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

няться одновременно.

Параллелизм обработки данных о множ естве об ъектов (тре -

тий тип) состоит в том, чт о для зада ч, имеющих дело с массив а-

ми информации, нередк о можно одновременно проводить по-

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

вых или почти одинаковых объек тов. В более общем случае в

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

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

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

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

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

машинные и многопроцессорные системы. Параллелизму смеж-

ных операций соответств у ет d > 1, т. е. командно-магистральная

обработка. Наконец, параллелизму обработки данных о мно же-

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

ная им обрабо тка. Сле дует отметить, что здесь речь идет о наи-

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

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

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

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

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

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

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

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

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

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

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

вычислительных систем это снижение мо жет быть зна читель-

ным.

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

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

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

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

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

боткой разрядов слов (w > 1). Возможность рас членения ариф-

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

построению систем с арифметико-магистральной обработкой (w’

> 1, где w’ – к о личеств о этапов обработки данных в арифмети-

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

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

ки (k’ > 1, где k’ – к о личество одновременно работающих уст-

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

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

вычислений.

Пусть треб у ется решить на мног опроцессорной системе

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

большим объемо м вычислений. Тогда рабо ту процессоров мо жно

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

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

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

ствляет свою часть обработки данных, нак опленных в (i – 1)-м

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

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

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

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

первым процессором в (I – 1)-M цикле по данным, принятым в

(i – 2)-м цикле, и готовит массив данных для той части програм-

мы, которая должна исполняться третьим процессором, и так

далее. Ясно, что программа мо ж ет быть распре делена между

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

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

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

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

няя ск орость обработки мож ет быть близкой к с умм арной ско-

рости работы процессоров организованной магистрали.

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

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

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

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

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

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

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

Последнее мож ет привести к уменьшению отношения произво-

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

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

ных вычислительных систем.

Возмо жность реализации магистральной обрабо тки на раз-

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

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

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

магистральные системы». Действительно, примеры реальных

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

мах сделан акцент на магистральную обработку, но в цело м они

являю тся все же системами с ко мбиниров анной струк турой. В

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

са МКОД как самосто ятельного класса вычислительных систем,

к к от оро му и только к к о торо му могут быть отнесены те или

иные вычислительные системы.

МНОГОПРОЦЕССОРНЫЕ ВЫЧИСЛИТЕЛЬНЫЕ СИСТЕМЫ

С ПРОГРАММИРУЕМОЙ АРХИТЕКТУРОЙ

Опыт разрабо тки и эк сплуатации многопроцессорных сис-

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

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

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

ципам синтеза архитек туры многопроцессорных систем. От

принципа жестк ой архитектуры следу ет перейти к принципу

программиру емой архитек туры многопроцес-сорной ВС. Прин-

цип проце дурной реализации зада ч в ВС необ ходимо заменить

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

ния. Важ ен перехо д от фон-нейм ановского принципа пот ок а

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

С ущественное значение имеет пере ход от принципа сосре-

дот о ченной общей для всех ВС памяти к распределенной памя-

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

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

ного принципа выполнения макроопераций в процессорах сис-

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

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

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

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

и перейти от принципа внутренних машинных языков низкого

уровня, стро ящих ся на основе набора простейших элементар-

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

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

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

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

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

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

Нак онец, серьезное значение имеет замена процедурног о прин-

ципа организации обменов данными между процессорами, а

также между процессорами и памятью системы, принципо м

программирования в мощной коммутационной системе прямых

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

ными между пере численными узлами.

Мног опроцессорные системы с программир уемой архитек-

турой существенно от личаются от таковых с жестк ой архитек-

100

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

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

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

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

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

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

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

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

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

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

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

основной составной частью МВС с программир уемой архитек-

турой.

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

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

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

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

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

ных операций должно быть таким, чтобы обмен информацией

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

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

Если в струк тур у МП вло жить алгоритм на основе более общей

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

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

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

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

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

операций подмнож ества. Это дает возможность синтезирова ть

относительно простой МП с программируемой стр укт урой, ра-

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

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

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

ру емой архитектурой должна иметь мощную универсальную

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

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

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

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

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