Файл: 481-550.pdf

Классификация параллельных вычислительных систем  4 9 1

MISD

MISD

 (Multiple Instruction Stream/Single Data Stream) — множественный поток

команд и одиночный поток данных (рис. 10.5, б). Из определения следует, что в ар-

хитектуре ВС присутствует множество процессоров, обрабатывающих один и тот
же поток данных. Примером могла бы служить ВС, на процессоры которой пода-
ется искаженный сигнал, а каждый из процессоров обрабатывает этот сигнал с по-

мощью своего алгоритма фильтрации. Тем не менее ни Флинн, ни другие специа-

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

убедительный пример реально существующей вычислительной системы, постро-
енной на данном принципе. Ряд исследователей [117,121,213] относят к данному
классу конвейерные системы, однако это не нашло окончательного признания.
Отсюда принято считать, что пока данный класс пуст. Наличие пустого класса не
следует считать недостатком классификации Флинна. Такие классы, по мнению
некоторых исследователей [84,192], могут стать чрезвычайно полезными для раз-
работки принципиально новых концепций в теории и практике построения вы-
числительных систем.

Рис. 10.5. Архитектура вычислительных систем по Флинну:

 а —

 SISD;

 б —

 MISD;

в —SIMD;г —MIMD

SIMD

SIMD

 (Single Instruction Stream/Multiple Data Stream) — одиночный поток команд

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

 в).

 ВМ данной архитектуры позволяют

выполнять одну арифметическую операцию сразу над многими данными — эле-
ментами вектора. Бесспорными представителями класса SIMD считаются матрицы

4 9 2 Глава 10. Параллелизм как основа высокопроизводительных вычислений

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

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

В принципе в этот класс можно включить и векторно-конвейерные ВС, если каж-

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

MIMD

MIMD

 (Multiple Instruction Stream/Multiple Data Stream) — множественный по-

ток команд и множественный поток данных (рис. 10.5, г). Класс предполагает на-
личие в вычислительной системе множества устройств обработки команд, объе-

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

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

зависит от трактовки. Так, ранее упоминавшиеся векторно-конвейерные ВС мож-

но вполне отнести и к классу MIMD, если конвейерную обработку рассматривать
как выполнение множества команд (операций ступеней конвейера) над множе-
ственным скалярным потоком.

Схема классификации Флинна вплоть до настоящего времени является наибо-

лее распространенной при первоначальной оценке той или иной ВС, поскольку

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

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

иному классу. Другая слабость — это чрезмерная насыщенность класса MIMD. Все

это породило множественные попытки либо модифицировать классификацию
Флинна, либо предложить иную систему классификации.

Контрольные вопросы

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

Каковы, на ваш взгляд, достоинства, недостатки и области применения этих
схем классификации?

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

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

3. Поясните суть закона Амдала, приведите примеры, поясняющие его ограничения.
4. Какую проблему закона Амдала решает закон Густафсона? Как он это делает?

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

5. Укажите достоинства и недостатки схемы классификации Флинна.

Глава 11

Организация памяти

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

В вычислительных системах, объединяющих множество параллельно работающих
процессоров или машин, задача правильной организации памяти является одной
из важнейших. Различие между быстродействием процессора и памяти всегда было
камнем преткновения в однопроцессорных ВМ. Многопроцессорность ВС приво-

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

ны нескольких процессоров.

В зависимости от того, каким образом организована память многопроцессор-

ных (многомашинных) систем, различают вычислительные системы с общей па-
мятью (shared memory) и ВС с распределенной памятью (distributed memory). В

 си-

стемах с общей памятью

 (ее часто называют также совместно используемой или

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

с общей памятью называют

 сильно связанными

 (closely coupled systems). Подобное

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

MIMD. Иногда, чтобы подчеркнуть это обстоятельство, вводят специальные под-

классы, используя для их обозначения аббревиатуры SM-SIMD (Shared Memory

SIMD) и SM-MIMD (Shared Memory MIMD).

В варианте

 с распределенной памятью

 каждому из процессоров придается соб-

ственная память. Процессоры объединяются в сеть и могут при необходимости
обмениваться данными, хранящимися в их памяти, передавая друг другу так назы-
ваемые

 сообщения.

 Такой вид ВС называют

 слабо связанными

 (loosely coupled

systems). Слабо связанные системы также встречаются как в классе SIMD, так и в

классе MIMD, и иной раз, чтобы подчеркнуть данную особенность, вводят под-
классы DM-SIMD (Distributed Memory SIMD) и DM-MIMD (Distributed Memory
MIMD).

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

мультипроцессорами,

 а системы с распределенной памятью —

 мулътикомпьюте-

рами.

4 9 4 Глава 11. Организация памяти вычислительных систем

Различие между общей и распределенной памятью — это разница в структуре

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

доступ

 к

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

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

ший от процессора адрес ячейки. Для примера положим, что процессор выполняет
команду Load RO, i, означающую "Загрузить регистр R0 содержимым ячейки i". В слу-

чае общей памяти i — это глобальный адрес, и для любого процессора указывает на
одну и ту же ячейку. В распределенной системе памяти i — это локальный адрес.

Если два процессора выполняют команду load RO, i, то каждый из них обращается
к i-й ячейке в своей локальной памяти, то есть к разным ячейкам, и в регистры R0

могут быть загружены неодинаковые значения.

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

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

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

данных и передавать в параллельно используемые подпрограммы ссылки на эту
структуру. В системе с распределенной памятью необходимо в каждой локальной
памяти иметь копию совместно используемых данных. Эти копии создаются пу-
тем вкладывания разделяемых данных в сообщения, посылаемые другим процес-
сорам.

Память с чередованием адресов

Физически память вычислительной системы состоит из нескольких модулей (бан-
ков), при этом существенным вопросом является то, как в этом случае распределе-
но адресное пространство (набор всех адресов, которые может сформировать про-

цессор). Один из способов распределения виртуальных адресов по модулям памяти
состоит в разбиении адресного пространства на последовательные блоки. Если
память состоит из

 п

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

находиться в банке с номером i

/п.

 В системе

 памяти с чередованием адресов

 (inter-

leaved memory) последовательные адреса располагаются в различных банках: ячей-
ка с адресом i находится в банке с номером

 i

 mod

 п.

 Пусть, например, память состо-

ит из четырех банков, по 256 байт в каждом. В схеме, ориентированной на блочную
адресацию, первому банку будут выделены виртуальные адреса 0-255, второму -
256-511 и т. д. В схеме с чередованием адресов последовательные ячейки в первом
банке будут иметь виртуальные адреса 0, 4, 8, ..„ во втором банке — 1, 5, 9 и т. д.
(рис. 11.1, а).

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

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

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

 i,

 а в следующем цикле — к ячейке j Если

 i и j

 находятся в разных банках,

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

мается цикл процессора, в то время как полный цикл памяти занимает несколько
циклов процессора. Таким образом, в данном случае процессор не должен ждать,
пока будет завершен полный цикл обращения к ячейке

 i.

 Рассмотренный прием

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

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

а б

Рис. 11.1. Память с чередованием адресов: а — распределение адресов;

 б —

 элементы,

извлекаемые с шагом 9 из массива 8х8

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

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

длительности цикла памяти.

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

с расслоением), зависит от ожидаемого порядка доступа к информации. Програм-
мы компилируются так, что последовательные команды располагаются в ячейках
с последовательными адресами, поэтому высока вероятность, что после команды,
извлеченной из ячейки с адресом

 i,

 будет выполняться команда из ячейки i + 1.

Элементы векторов компилятор также помещает в последовательные ячейки, по-
этому в операциях с векторами можно использовать преимущества метода чередо-
вания. По этой причине в векторных процессорах обычно применяется какой-либо
вариант чередования адресов. В мультипроцессорах с совместно используемой
памятью тем не менее используется поблочная адресация, поскольку схемы обра-
щения к памяти в MIMD-системах могут сильно различаться. В таких системах
целью является соединить процессор с блоком памяти и задействовать максимум
находящейся в нем информации, прежде чем переключиться на другой блок памяти.

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

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

v

1

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

vО,

 v4, v

8. Интервал между элементами называют

 шагом по индексу

 или

 «страй-

Ъомъ

 (stride). Одним из интересных применений этого свойства может служить

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

рицы (рис. 11.1,

 б).

 Ответственность за то, чтобы все извлекаемые элементы мат-

рицы располагались в разных банках, ложится на программиста.

Модели архитектуры памяти

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

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