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

Архитектуры параллельных компьютеров могут значительно отличаться друг от друга. Рассмотрим некоторые существенные понятия и компоненты параллельных компьютеров. Параллельные компьютеры состоят из трех основных компонент:

· процессоры;

· модули памяти;

· коммутирующая сеть.

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

Классификация по числу потоков команд/данных.

Это одна из первых классификаций, ссылки на которую наиболее часто встречаются в литературе, была предложена М. Флинном в конце 60-х годов прошлого века. Она базируется на понятиях двух потоков: команд и данных.(Single Instruction Single Data). Такую архитектуру имеют все однопроцессорные системы.

MISD (Multiple Instruction Single Data). Эта архитектура не получила распространения, хотя формально может существовать. М. Флинн не смог привести ни одного примера реально существующей системы, работающей на этом принципе. Некоторые авторы в качестве представителей такой архитектуры называют векторно-конвейерные компьютеры, однако такая точка зрения не получила широкой поддержки. Считается, что есть только один представитель данного семейства - мультипроцессор C. mpp университета Карнеги-Мелон. Но он может работать как в MISD, так и в MIMD режимах, причем, второй считается штатным.

SIMD (Single Instruction Multiple Data). SIMD компьютер (рисунок 1.1) имеет N идентичных синхронно работающих процессоров, N потоков данных и один поток команд.

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

Рисунок 1.1. SIMD-архитектура.

MIMD (Multiple Instruction Multiple Data). MIMD компьютер имеет N процессоров, N потоков команд и N потоков данных. Каждый процессор функционирует под управлением собственного потока команд. Схема MIMD-модели показана на рисунке 2.2

Рисунок 1.2. MIMD-архитектура.

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

Классификация по организации памяти.

Другим свойством, различающим параллельные компьютеры, является способ доступа к модулям памяти, то есть имеет ли каждый процессор локальную память и обращается к другим блокам памяти, используя коммутирующую сеть, или коммутирующая сеть соединяет все процессоры с общей памятью. Исходя из способа доступа к памяти, различают следующие (довольно условные) типы параллельных архитектур:

Компьютеры с распределенной памятью (Distributed memory). Каждый процессор имеет доступ только к локальной собственной памяти. Процессоры объединены в сеть (рисунок 1.3). Доступ к удаленной памяти возможен только с помощью системы обмена сообщениями.

Рисунок 1.3. Системы с распределенной памятью.

Компьютеры с общей (разделяемой) памятью (True shared memory). Каждый процессор компьютера обладает возможностью прямого доступа к общей памяти, используя общую шину. В таких компьютерах нельзя существенно увеличить число процессоров, поскольку при этом происходит резкое увеличение числа конфликтов доступа к шине. Схема подобной системы приведена на рисунке 1.4.

Рисунок 1.4. Системы с разделяемой памятью.

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

Рисунок 1.5. Системы с неоднородной памятью.

Компьютеры с виртуальной общей (разделяемой) памятью (Virtual shared memory). В таких системах общая память как таковая отсутствует. Каждый процессор имеет собственную локальную память. Он может обращаться к локальной памяти других процессоров, используя " глобальный адрес". Если " глобальный адрес" указывает не на локальную память, то доступ к памяти реализуется по сети, соединяющей процессоры.

Системы с виртуальной разделяемой памятью имеют ту же схему, что и системы с распределенной памятью. Их отличие состоит в том, что в системах с виртуальной разделяемой памятью процессоры при необходимости взаимодействия не обмениваются сообщениями, а генерируют обращение к памяти другого процессора, как к своей. Обращение к " чужой" памяти идет на порядок (или даже более) медленнее.

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

Классификация Хэндлера.

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

· уровень выполнения программы - опираясь на счетчик команд и некоторые другие регистры, устройство управления (УУ) производит выборку и дешифрацию команд программы;

· уровень выполнения команд - арифметико-логическое устройство компьютера (АЛУ) исполняет команду, выданную ему устройством управления;

· уровень битовой обработки - все элементарные логические схемы процессора (ЭЛС) разбиваются на группы, необходимые для выполнения операций над одним двоичным разрядом.

Например, процессор CDC 6600 имеет ЦПУ с десятью процессорами ввода/вывода. Один управляющий блок контролирует одно АЛУ с длиной слова 60 бит. АЛУ имеет 10 функциональных блоков, которые могут быть организованны в конвейер.10 процессоров ввода/вывода могут работать параллельно друг с другом и с ЦПУ. Каждый процессор ввода/вывода содержит 12-ти битное АЛУ. Структура такой вычислительной системы описывается следующим образом:

CDC 6600I/O = (10, 1, 12), 6600main = (1, 1× 10, 60), 6600 = (I/O processors) × (central processor) = (10, 1, 12) × (1, 1 × 10, 60).

Процессор Cray-1 - это 64-х битный процессор, его АЛУ имеет 12 функциональных блоков, восемь из которых могут быть связаны в конвейер, различные функциональные устройства имеют от 1 до 14 сегментов, которые также могут работать в конвейере. Описатель в этом случае будет иметь следующий вид:

 1 = (1, 12× 8, 64 *× (1 14)).

Классификация Джонсона.

Е. Джонсон предложил проводить классификацию MIMD архитектур на основе структуры памяти и реализации механизма взаимодействия и синхронизации между процессорами.

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

Опираясь на такое деление, Джонсон вводит названия для некоторых классов. Так вычислительные системы, использующие общую разделяемую память для межпроцессорного взаимодействия и синхронизации, он называет системами с разделяемой памятью, например, CRAY Y-MP (по его классификации это класс 1). Системы, в которых память распределена по процессорам, а для взаимодействия и синхронизации используется механизм передачи сообщений он называет архитектурами с передачей сообщений, например NCube, (класс 3). Системы с распределенной памятью и синхронизацией через разделяемые переменные, как в BBN Butterfly, называются гибридными архитектурами (класс 2).

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

Классификация Хокни.

Р. Хокни - известный английский специалист в области параллельных вычислительных систем, разработал свой подход к классификации, введенной им для систематизации компьютеров, попадающих в класс MIMD по систематике Флинна.

Как отмечалось выше (см. классификацию Флинна), класс MIMD чрезвычайно широк, причем наряду с большим числом компьютеров он объединяет и целое множество различных типов архитектур. Хокни, пытаясь систематизировать архитектуры внутри этого класса, получил иерархическую структуру, представленную на рисунке 1.6

Рисунок 1.6. Классификация Хокни.

Основная идея классификации состоит в следующем. Множественный поток команд может быть обработан двумя способами: либо одним конвейерным устройством обработки, работающем в режиме разделения времени для отдельных потоков, либо каждый поток обрабатывается своим собственным устройством. Первая возможность используется в MIMD компьютерах, которые автор называет конвейерными (например, процессорные модули в Denelcor HEP). Архитектуры, использующие вторую возможность, в свою очередь опять делятся на два класса: компьютеры, в которых возможна прямая связь каждого процессора с каждым, реализуемая с помощью переключателя; компьютеры, в которых прямая связь каждого процессора возможна только с ближайшими соседями по сети, а взаимодействие удаленных процессоров поддерживается специальной системой маршрутизации через процессоры-посредники.

Далее, среди MIMD машин с переключателем Хокни выделяет те, в которых вся память распределена среди процессоров как их локальная память (например, PASM, PRINGLE). В этом случае общение самих процессоров реализуется с помощью очень сложного переключателя, составляющего значительную часть компьютера. Такие машины носят название MIMD машин с распределенной памятью. Если память это разделяемый ресурс, доступный всем процессорам через переключатель, то такие MIMD являются системами с общей памятью (CRAY X-MP, BBN Butterfly). В соответствии с типом переключателей можно проводить классификацию и далее: простой переключатель, многокаскадный переключатель, общая шина.

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

При рассмотрении MIMD машин с сетевой структурой считается, что все они имеют распределенную память, а дальнейшая классификация проводится в соответствии с топологией сети: звездообразная сеть (lCAP), регулярные решетки разной размерности (Intel Paragon, CRAY T3D), гиперкубы (NCube, Intel iPCS), сети с иерархической структурой, такой, как деревья, пирамиды, кластеры (Cm*, CEDAR) и, наконец, сети, изменяющие свою конфигурацию.

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

Классификация Шора.

Классификация Дж. Шора, появившаяся в начале 1973 году, интересна тем, что представляет собой попытку выделения типичных способов компоновки вычислительных систем на основе фиксированного числа базисных блоков: устройства управления, арифметико-логического устройства, памяти команд и памяти данных. Дополнительно предполагается, что выборка из памяти данных может осуществляться словами, то есть выбираются все разряды одного слова, и/или битовым слоем - по одному разряду из одной и той же позиции каждого слова (иногда эти два способа называют горизонтальной и вертикальной выборками соответственно). Конечно же, при анализе данной классификации надо делать скидку на время ее появления, так как предусмотреть невероятное разнообразие параллельных систем настоящего времени было в принципе невозможно. Итак, согласно классификации Шора все компьютеры разбиваются на шесть классов, которые он так и называет: машина типа I, II и т.д.

Машина I - это вычислительная система, которая содержит устройство управления, арифметико-логическое устройство, память команд и память данных с пословной выборкой. Считывание данных осуществляется выборкой всех разрядов некоторого слова для их параллельной обработки в арифметико-логическом устройстве. Состав АЛУ специально не оговаривается, что допускает наличие нескольких функциональных устройств, быть может конвейерного типа. По этим соображениям в данный класс попадают как классические последовательные машины (IBM 701, PDP-11, VAX 11/780), так и конвейерные скалярные (CDC 7600) и векторно-конвейерные (CRAY-1).

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

Структура машины II лежит в основе ассоциативных компьютеров (например, центральный процессор машины STARAN), причем фактически такие компьютеры имеют не одно арифметико-логическое устройство, а множество сравнительно простых устройств поразрядной обработки. Другим примером служит матричная система ICL DAP, которая может одновременно обрабатывать по одному разряду из 4096 слов.

Если объединить принципы построения машин I и II, то получим машину III. Эта машина имеет два арифметико-логических устройства - горизонтальное и вертикальное, и модифицированную память данных, которая обеспечивает доступ как к словам, так и к битовым слоям. Впервые идею построения таких систем в 1960 году выдвинул У. Шуман, называвший их ортогональными (если память представлять как матрицу слов, то доступ к данным осуществляется в направлении, " ортогональном" традиционному - не по словам (строкам), а по битовым слоям (столбцам)). В принципе, как машину STARAN, так и ICL DAP можно запрограммировать на выполнение функций машины III, но поскольку они не имеют отдельных АЛУ для обработки слов и битовых слоев, отнести их к данному классу нельзя. Полноправными представителями машин класса III являются вычислительные системы семейства OMEN-60 фирмы Sanders Associates, построенные в прямом соответствии с концепцией ортогональной машины.