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

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

да. Однако, если иметь минимальную информацию о структуре

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

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

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

фик сиру ется, как только фик сир уется как ая-то гипотеза о дос-

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

это представление тела цикла в виде «черног о ящик а».

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

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

лическое (интраитерационное) и интерциклическ ое (интерите-

рационное) распараллеливание. Первое прово дится внутри тела

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

фраг ментов. Второе предпо лагает совмещение при вычислении

различных итераций цикла. Именно интерциклическое распа-

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

мы и рассмотрим.

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

Методы первой из них тем или иным способом использу ют

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

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

тков. Ведь в конечном ит ог е любой цикл задает последователь-

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

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

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

рабо тах пре длагаются различные приемы для «сжа тия» инфор-

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

информ ации о связях итераций. К мето дам этог о класса можно

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

ав т оно мных ветвей из всех информационно-св язанных итера-

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

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

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

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

некоторая параллельная фор ма, состо ящая из набора ветвей, либо

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

назна чение итераций на обработку.

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

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

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

ледовательных и параллельных циклов. Обычно это некоторая

форм а векторных и матричных операций.

Методы третьей к а тег ории основываются на анализе тела

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

ного цикла. По характеру резуль тир ующей формы эти мето ды

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

более важное различие мет одов вт орой и третьей катег ории в

то м, что после дние не использ ую т или по чти не испо льз ую т

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

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

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

ОПЕРАЦИИ НАД МАССИВАМИ И МНОЖЕСТВАМИ

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

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

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

ричных процессоров. Но только с появ лением этих процессо-

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

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

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

В большинстве случаев операции над массив ами – есте-

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

обычно по следующим правилам.

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

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

именными элементами операндов. Если о дин из операндов би-

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

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

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

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

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

рации над соответств ующим элемент о м массива-операнда.

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

скаляр. В набор стандартных функций соответств ующих язы-

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

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

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

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

ных операций, ко т орые реализую т сле дующие функции: генера-

цию вектора целых чисел с шагом 1 по заданным верхней и ниж-

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

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

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

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

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

также набор операций над множ ествами: определение числа

элемент ов множ ества, пересе чение, об ъединение множ еств, сум-

ма и разность мно жеств и т.д.

ПРИНЦИПЫ ПОСТРОЕНИЯ ПАРАЛЛЕЛЬНЫХ

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

ПРИЗНАКИ И ПОЛНАЯ СХЕМА КЛАССИФИКАЦИИ

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

В качестве основных признаков классифик ации, характе-

ризующих организацию струк туры и функционирования вычис-

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

берем следующие:

1) тип поток а команд в центральной части ВС;

2) тип пот ока данных в центральной части ВС;

3) способ обработки данных в центральных устройствах

обрабо тки;

4) степень связанности к о мпонент ВС;

5) степень однородности основных к о мпонент ВС;

6) тип внутренних св язей в ВС.

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

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

от каждог о i-го уровня к следующему более низк ому (i+1)-му

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

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

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

ВС - вычислительные системы;

ОК, МК - о диночный и мно жественный пот оки команд

соответственно (SI, MI);

ОД, МД - о дино чный и множ ественный потоки данных

соответственно (SD, MD);

С, Р – пословная и поразрядная обрабо тка данных в цен-

тральных обраба тывающих устройствах соо тветственно;

Нс, Вс – низкая и высок ая степень связанности ВС соот-

ветственно;

Ор, Нр – о дноро дная и неодноро дная ВС соо тв етственно;

Кн, Пм, Пр – системы со связями «канал-к анал», через

общую внешнюю память и непосредственно между процессо-

рами соответственно;

Ош, Мш, Пк – системы со связями через о дну общую

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

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

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

мутат ора соотв етственно.

Обозна чения (нотации) классов систем будем состав лять из

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

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

ВС до узла данног о класса систем вклю чительно (рис.3.1).

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

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

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

и поэтому образ у ют в совокупности 8 классов систем (классы 4-

го уровня). Переход от первог о ко в т оро му уровню соответств у-

ет разделению систем по типу пот ока команд – о дино чный или

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

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

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

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

памяти. Далее при переходе к четверт о му уровню иерархии сис-

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

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

с одиночными потоками к о манд и данных и с пословной обра-

боткой данных (ОКОДС) представ ляют собой обычные процес-

соры, а с поразрядной обрабо ткой (ОКОДР) – одноразрядные

процессоры. Эти системы соответств уют SISD-типу машин клас-

сификации Флинна. Системы с одино чным потоком к о м анд и

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

представителей с пословной обработкой (ОКМДС) ма тричные

Рис. 3.1. Схема классификации вычислительных машин

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

(ОКМДР) – ассоциативные системы (SIMD-тип по Ф линну). Ти-

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

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

обработке (МКОДС) являются магистральные (конвейерные)

системы; при поразрядной обработк е (МК ОДР) – системы с кон-

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

1 2 3 4 5 6 7 8

ВС

ОК

МК

ОД

МД

ОД

МД

1 уровень

2 уровень

3 уровень

4 уровень

Обычные

процессоры

Одноразрядные

процессоры

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

системы

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

сис темы

НС

ВС

НС

ВС

ОР

НР

ОР

5 уровень

6 уровень

Системы с ансам-

блем процессоров

Матричные и

векторные

КН ПМ ПР КН ПМ ПР ОШ МШ ПК ОШ МШ ПР

7 уровень

Однородные

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

системы

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

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

системы

Однородные

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

е системы

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

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

ные системы

по Ф линну). Многопроцессорные и много машинные системы

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

данных и с пословной обработкой (МКМДС). В к ачестве сис-

тем с поразрядной обработкой (МКМДР) можно представить

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

(MIMD-тип по Ф линну).

Последние три признака с х емы классификации опре деляют

классы систем со сло жной струк турой. На с х еме пок азаны классы

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

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

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

шестому - на одноро дные и нео дноро дные системы и, нак онец,

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

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

Низкая степень связанности для систем типа ОКМДС озна-

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

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

ния, но не имею т непосредственных связей между собой. Высо-

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

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

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

ними обрабатывающими устройствами. Т ипичные представи-

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

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

имеющие общую оперативную память).

Наиболее сложную структуру имеют много м ашинные и

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

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

ют общую оперативную память. Много машинные системы обыч-

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

шины и могут состо ять как из о днотипных, так и из разнотип-

ных машин. В состав многопроцессорных могут входить как

однотипные, так и разнотипные процессоры. Характерными

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

бинациях, в о дноро дных и неодноро дных мног о машинных сис-

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

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

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

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

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

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

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

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

цией, многошинные связи с применением многовхо довых мо-

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

сосредо то ченног о или распределенног о перекрестного (матрич-

ного) ко ммутат ора. Шины и матричный ко ммутат ор использ у-

ются и для присоединения внешних устройств.

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

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

ные системы являются комбинацией систем типа ОКОДС и

ОКМДР. Так ого рода системы с признак ами о т личающихся друг

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

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

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

о дног о класса в друг ой. Такие системы называю т системами с

перестраиваемой структ урой.

ПОТОКИ КОМАНД И ДАННЫХ.

ОСНОВНЫЕ СТРУКТУРЫ И ОПРЕДЕЛЕНИЯ

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

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

стем (ОКОД, ОКМД, МКОД, МКМД), как уже указывалось, вве-

дены М.Дж.Флинном.

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

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

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

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

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

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

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

тке организационной структуры).

В системах типа ОКМД о дно устройство управления осу-

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

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

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

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

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

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

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

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

ностей распараллелив ания.

В системах типа МК ОД процесс обрабо тки разбивается на

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

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

ти магистраль обработки (конвейер процесс оров). Реальная ско-

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

рали. Наиболее высокая скорость обработки достигается при

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

ными операциями. При частых прерываниях линейных участ-

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

В системах типа МКМД неско лько устройств управления

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

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

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

системы обладают большой гибк остью. Реальная скорость об-

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

цессоров, о днако, если распараллеливание вычислений при вы-

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

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

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

рузку процессоров. Системы типа МКМД от личаю тся высоко й

надежностью вследствие хороших возмо жностей взаимного

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

Системы рассмотренных четырех классов вклю чены в ба-

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

по уровням иерархии ее первый, вт орой и третий уровни.

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

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

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

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

лительной системы. Ее следует отлича ть от му льтипрограмми-

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

времени и оборудования между дв умя или бо лее программами,

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

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

раммный режим параллельной обработки.

Вычислительные системы параллельной обработки инфор-

мации или, более коротк о, ПВС, содержат два или более про-

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

ОКМД, МК ОД, МКМД (см. п. 3.2.) Они представляют собой

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

более поток а к оманд и (или) данных.

Системой типа ОКМД называется нек о торая параллель-

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

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

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

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

с пословной (ОКМДС) и поразрядной (ОКМДР) обработкой.

Основными типами систем ОКМДС являются ансамбли

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

ные системы. Характерной особенностью таких систем яв ляет-

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

к ним при по мощи адресов, а не при помощи тэгов (признак ов -

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

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

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

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

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

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

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

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

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

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

ности. В первых системах процессоры обычно имеют общую

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

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

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

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

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

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

Если не счита ть машины Унг ера (1958г.) [4], которая была

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

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

ной системой следу ет счита ть систему SOLOMON [1]. Система

со держит 1024 процессорных элемента (ПЭ) (рис.3.2), соединен-

ных в виде ма трицы 32Х32. Каждый ПЭ в ма трице соединен с

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

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

ких и логических операций, а такж е оперативное ЗУ емк остью 16

Кбит, разбитое на мо дули по 4 Кбит каждый. Длина слова пере-

менная – от 1 до 128 разрядов. Разрядность слов устанавливается

программно. По каналам связи от устройства управления (УУ)

передаются к о м анды и общие константы. В ПЭ использ у ется та к

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

ПЭ выпо лнять (т.е. быть ак тивным) или не выполнять (быть пас-

сивным) общую операцию в зависимости от зна чений обраба ты-

ваемых данных. В каждый момент все активные ПЭ выполняют

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

ной памяти и имеющими один и тот же адрес. Идея много мо-

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

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

ПЭ

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

Рис. 3.2. Ст руктурная схема матричной системы