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

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

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

изменяющих ся условиях ф ункционирования.

По степени централизации управления ВС делятся на цен-

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

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

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

о дна из ЭВМ, называемая машиной-директором, или централь-

ный процессор. В децентрализованной ВС каждый процессор

или ЭВМ действ ует ав т ономно, решая свои зада чи. В системе со

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

ств ующих ЭВМ (или процессоров), в каждой из к о торых осу-

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

– децентрализованное.

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

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

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

ется новый класс ВС, имеющих большое число рассредо т очен-

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

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

ки, ф ункционир ующих авт оно мно, но, в месте с тем, согласо-

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

ня, объе диняющей их в е диное целое и обеспе чивающей их вза-

имодействие через сеть связи. Распределенные ВС воплощают

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

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

ств ующих мини- и микропроцессорных систем.

Следует выделить вычислите льные сети. Они состоят из

территориально разнесенных центров (узлов), образ у емых са-

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

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

ные центры ф ункционир уют в той или иной ав т оно мно др уг от

друга и взаимодействуют между собой через систему связи.

Вычислительные сети, в силу своих особенностей, существен-

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

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

нирования, так и в части программног о обеспечения. Их целе-

сообразно рассма трив а ть особо. Мы рассмотрим соотношение

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

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

Различие между распределенной ВС и вычислительной се-

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

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

между ними. Если все ко мпоненты системы о тносительно малы,

зависимы и локализованы, то их мо жно счита ть частями о дной

распределенной вычислительной системы (м ашины). Если, на-

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

сматривать как разные машины сети. Мно ж ество разнообраз-

ных смешанных форм, веро ятно , станет обычным в ближайшие

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

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

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

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

ти кристалла), у каждог о из которых будет сво я ф ункция. Неко-

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

ко мпиляции программ (для каждого язык а - о дин процессор),

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

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

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

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

целей.

Одно из направ лений развития ВС имеет дело с высок опа-

раллельными устройствами массовой обработки (на уровнях

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

числите льными сре дами. Вычислительная среда представляет

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

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

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

полног о набора. Основные принципы построения вычислитель-

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

граммная изменяемость структ уры.

Основные типы ПВС представлены на рис. 3.6. На этом

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

сорные ВС, поскольку х арак теристики о днородности и неодно-

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

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

шенной надежностью, а также распределенные ВС и сети по-

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

Параллельные вычислительные системы

ВС с одиночным

пото ком команд и

множественным

пото ком данных

ВС с

множественным

пото ком команд и

одиночным

ВС с

множественными

пото ками команд и

данных

ВС с

ко мбинированными

и переменными

пото ками команд и

Ансамбли

процессоров

Магистральные

(конвейерные) ВС

Многомашинные

ВС

ВС с

комбинированной

ВС с векторным

пото ком данных

Макромагистраль-

ные ВС

Многопроцессор-

ные ВС

Ортого нальные

ВС

Матричные ВС

Командно-

магистральные ВС

Одно родные

многопроцессорные

ВС

ВС с перестраива-

емой структурой

Ассоциативные

ВС

Арифметико-

магистральные ВС

Неоднородные

многопроцессорные

ВС

ВС с

ассоциативными

ВС с

ассоциативной

ВС с повышенной

надежностью

Распределенные

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

системы и сети

Рис. 3.6. Основные типы параллельных вычислительных систем

СТРУКТУРА СВЯЗЕЙ В ПАРАЛЛЕЛЬНЫХ

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

МЕЖПРОЦЕССОРНЫЕ СВЯЗИ В ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ

И СЕТЯХ И ИХ КЛАССИФИКАЦИЯ.

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

на инфор мацией между процессорами, об еспечив ающие соеди-

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

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

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

рисунке 3.7. Сх ем а имеет пять уровней, первый из которых яв-

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

обмена информацией, третий – мето д управления соеди-нением

тракт ов обмена, четвертый – структур у путей передачи инфор-

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

структур вычислительных систем и сетей.

Первый уровень – исхо дный, он вклю чает внутренние свя -

зи для об мена информацией. Второй уровень включает прямые

и косвенные (непрямые) тракты обмена. В первом случае

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

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

него сообщения. При этом в канале связи никакой логики не

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

и устройств повторения сообщений. Во втором случае

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

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

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

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

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

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

рализованным и децентрализованным (третий уровень). При

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

равление соединением трактов об мена. Непрямая переда ча при

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

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

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

исто чник а для всех дальнейших передач. Непрямая передача при

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

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

да чи информ ации.

Четвер тый уровень соо тветств ует дву м струк турам путей пе-

реда чи информации. Первая определяет индивидуальные (раз-

дельные) тракты обмена, кот орые назначаются (выделяются) для

Память

1 2 3 4 5 6 7 8 9 105 - уровень

индивидуальные

тракты

распределенные

тракты

индивидуальные

тракты

распределенные

тракты

индивидуальные

тракты

распределенные

тракты

4 - уровень

3 - уровень

2 - уровень

4 - уровень

ничего

централизованное

назначение трактов

обмена

децентрализованное

назначение трактов

обмена

прямые косвенные

Связи для обмена

информацией

коммутатор

Рис. 3.7. Структурная схема межпроцессорных связей в ПВС

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

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

при помощи разделения времени этих трактов. Прямая переда-

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

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

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

чем одним источником информации. Такая организация обес-

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

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

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

ляется для всех сообщений только по этому общему пути. Не-

прямая передача при помощи раздельных путей и централизо-

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

путь к промежуточному пункту и от нег о — к каждому прием-

нику. Непрямая передача при помощи общег о пути и централи-

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

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

емникам информ ации. Непрямая переда ча при помощи раз дель-

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

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

иметь мног о пунктов назна чения. Непрямая пере дача при по мо-

щи общего пути и децентрализованног о управления озна чает,

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

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

гими приемниками информации в режиме разделения времени

для обмена данными.

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

лительных систем и сетей (№№ 1, 2, ..., 10). Прямой переда че по

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

сорных элемент ов без к о ммутат оров (№1), каждый э лемент ко-

торой имеет соседа-предшественника и соседа-преемник а. Пе-

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

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

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

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

зна чения. Такая струк т ура от личается логическ ой простот ой и

об ладает явно выраженной модульностью, но она не обладает

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

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

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

САМАС. Др угим типом структуры при прямой передаче по

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

(№2). В этом случае каждый источник имеет пути ко всем

приемникам. Такая струк тура не от личается мо дульностью по-

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

бо льшо м числе элементов, но она обеспе чивает высокую ско-

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

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

имеет вычислительная сеть MERIT, в которой соединены CDC

6500 и две машины IBM 360/67.

Прямой передаче с общим путем соответств у ет классичес-

кая многопроцессорная структ ура с общей основной памятью

(№ 3). В таких системах все сообщения передаются через ос-

новную память. При это м обеспечивается очень высокая про-

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

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

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

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

местом системы. Другим типом структуры при прямой переда-

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

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

элементами в режиме разделения ее времени (№ 4). Т акие струк-

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

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

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

бора ториях. Они от личаются простотой и явно выраженной

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

ное планирование занятия времени шины в целях повышения

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

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

гурацию САМАС.

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

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

звезды (№ 5). При передаче сообщения проходят через цент-

ральный коммута т ор. Такая структура част о реализ у ется на ос-

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

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

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

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

ную сеть IBM Network/440. Другим типо м структ уры при не-

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

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

тов с центральным, коммута т оро м (№ 6). Такая структ ура со че-

тает в себе особенности кольцевой структуры (№ 1) и струк туры

в виде звез ды (№ 5). Пересылка сообщений осуществляется по

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

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

ществляет адресацию пересылок. В ка честве примера можно

отметить экспериментальную систему обмена информацией

SPIDER.

Непрямой переда че по общему пути при централизованно м

управлении соотв етств у ет стр уктура с общей шиной и централь-

ным к о ммутат ором (№7). Такая струк тура в ф ункционально м от-

ношении эквивалентна структуре в виде звезды (№ 5). При это м

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

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

центральным ко ммутат оро м, а при помощи общей шины и орга-

низации доступа к ней. При передаче информации процессор-

ный элемент посылает сообщение через общую шину к цент-

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

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

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

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

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

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

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

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

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

тельно невысокой надежностью.

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

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

ная струк т ура (№ 8). К аждый процессорный элемент связан с

ближайшим соседом слева, справа, сверху и снизу, причем

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

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

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

стороне. Сообщения прох одят через сеть от о дног о элемента к

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

тов выбирает тракт для отсылки сообщения. Можно считать,

что кольцевая структ ура без центральног о коммута т ора (№ 1)

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

каждый элемент имеет два св язанных с ним соседних э лемента

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

сообщения. Моду льность и высокие харак теристики надежнос-

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

туры. Вместе с тем, такая структура требу ет сло жной логики

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

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

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

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

представляю тся о чень обнадеживающими. Другим типом струк-

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

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

ная струк тура (№ 9). Она становится все более распространен-

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

имеют высок ую стоимость. Здесь не требуется связь процессо-

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

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

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

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

но, возможность ее наращивания новыми мо дулями. Основное

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

сетях с географически разнесенными узлами, пример — сеть

ARPA.

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

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

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

ных элементов (№ 10). Такая структ ура по добна нерегу лярной

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

можностей наращивания. Однако она обладает более низкими

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

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

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

Структ уры с общей шиной при комбинированно м подключении

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

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

вычислительных системах на базе мини-ЭВМ. В качестве при-

мера системы с такой структурой можно отметить систему

PLURIBUS, предназначенную для выполнения функций связи в

узлах сети ARPA.

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

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

пределенными вычислительными систем ами и сетями. Сре ди

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

теристик четыре «доминирующие» структ уры, а именно: коль-

цев ую структуру (№ 1), структуру с общей шиной (№4), структ у-

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

элементами в концах лучей (№ 5) и нерегулярную структ уру (№

9). Проведенный анализ показывает, что эта классификация или

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

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

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

зателям . Одно из достоинств классифик ации состоит в возмо ж-

ности систематического перебора и сравнения всех вариантов.

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

ной степенью условности. Некоторые существ ующие вычис-

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

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

структур бо лее чем о дног о типа.

ОСНОВНЫЕ ТИПЫ СТРУКТУРЫ СВЯЗЕЙ

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

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

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

типа («канал – центральный процессор») каналы подключаются

к центрально му процессору (рис. 3.8), и информация из канала

поступает в процессор (процессор фактически управ ляет обме-

но м между памятью и каналами). В струк турах вт орого типа («ка-

нал — основная память») все данные передаются непосредствен-

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