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

 

6. Классификация Скилликорна

В 1989 году была сделана очередная  попытка расширить классификацию  Флинна и, тем самым, преодолеть ее недостатки. Д.Скилликорн разработал подход, пригодный для описания свойств многопроцессорных систем и некоторых нетрадиционных архитектур, в частности dataflow и reduction machine.

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

• процессор команд (IP - Instruction Processor) - функциональное устройство, работающее, как интерпретатор команд; в системе, вообще говоря, может отсутствовать;
• процессор данных (DP - Data Processor) - функциональное устройство, работающее как преобразователь данных, в соответствии с арифметическими операциями;
• иерархия памяти (IM - Instruction Memory, DM - Data Memory) - запоминающее устройство, в котором хранятся данные и команды, пересылаемые между процессорами;
• переключатель - абстрактное устройство, обеспечивающее связь между процессорами и памятью.

Функции процессора команд во многом схожи с функциями устройств  управления последовательных машин и, согласно Д.Скилликорну, сводятся к следующим:

• на основе своего состояния и полученной от DP информации IP определяет адрес команды, которая будет выполняться следующей;
• осуществляет доступ к IM для выборки команды;
• получает и декодирует выбранную команду;
• сообщает DP команду, которую надо выполнить;
• определяет адреса операндов и посылает их в DP;
• получает от DP информацию о результате выполнения команды.

Функции процессора данных делают его , во многом, похожим на арифметическое устройство традиционных процессоров:

• DP получает от IP команду, которую надо выполнить;
• получает от IP адреса операндов;
• выбирает операнды из DM;
• выполняет команду;
• запоминает результат в DM;
• возвращает в IP информацию о состоянии после выполнения команды.

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

Это один из самых простых  видов архитектуры, не содержащих переключателей. Для описания параллельных вычислительных систем автор зафиксировал четыре типа переключателей, без какой-либо явной связи с типом устройств, которые они соединяют:

• 1-1 - переключатель такого типа связывает пару функциональных устройств;
• n-n - переключатель связывает i-е устройство из одного множества устройств с i-м устройством из другого множества, т.е. фиксирует попарную связь;
• 1-n - переключатель соединяет одно выделенное устройство со всеми функциональными устройствами из некоторого набора;
• nxn - каждое функциональное устройство одного множества может быть связано с любым устройством другого множества, и наоборот.

Примеров подобных переключателей можно привести очень много. Так, все матричные процессоры имеют переключатель типа 1-n для связи единственного процессора команд со всеми процессорами данных. В компьютерах семейства Connection Machine каждый процессор данных имеет свою локальную память, следовательно, связь будет описываться как n-n. В тоже время, каждый процессор команд может связаться с любым другим процессором, поэтому данная связь будет описана как nxn.

Классификация Д.Скилликорна состоит из двух уровней. На первом уровне она проводится на основе восьми характеристик:

1. количество процессоров команд (IP);
2. число запоминающих устройств (модулей памяти) команд (IM);
3. тип переключателя между IP и IM;
4. количество процессоров данных (DP);
5. число запоминающих устройств (модулей памяти) данных (DM);
6. тип переключателя между DP и DM;
7. тип переключателя между IP и DP;
8. тип переключателя между DP и DP.

Используя введенные характеристики и предполагая, что рассмотрение количественных характеристик можно ограничить только тремя возможными вариантами значений: 0, 1 и n (т.е. больше одного), можно получить 28 классов архитектур.

В классах 1-5 находятся компьютеры типа dataflow и reduction, не имеющие процессоров команд в обычном понимании этого слова. Класс 6 это классическая фон-неймановская последовательная машина. Все разновидности матричных процессоров содержатся в классах 7-10. Классы 11 и 12 отвечают компьютерам типа MISD классификации Флинна и на настоящий момент, по мнению автора, пусты. Классы с 13-го по 28-й занимают всесозможные варианты мультипроцессоров, причем в 13-20 классах находятся машины с достаточно привычной архитектурой, в то время, как архитектура классов 21-28 пока выглядит экзотично.

На втором уровне классификации  Д.Скилликорн просто уточняет описание, сделанное на первом уровне, добавляя возможность конвейерной обработки в процессорах команд и данных.

В конце данного описания имеет смысл привести сформулированные автором три цели, которым должна служить хорошо построенная классификация:

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

 

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

Классификация Дж.Шора, появившаяся в начале 70-х годов, интересна тем, что представляет собой попытку выделения типичных способов компоновки вычислительных систем на основе фиксированного числа базисных блоков: устройства управления, арифметико-логического устройства, памяти команд и памяти данных. Дополнительно предполагается, что выборка из памяти данных может осуществляться словами, то есть выбираются все разряды одного слова, и/или битовым слоем - по одному разряду из одной и той же позиции каждого слова (иногда эти два способа называют горизонтальной и вертикальной выборками соответственно). Итак, согласно классификации Шора все компьютеры разбиваются на шесть классов, которые он так и называет: машина типа 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, построенные в прямом соответствии с концепцией ортогональной машины.

 

Если в машине I увеличить  число пар арифметико-логическое устройство <==> память данных (иногда эту пару называют процессорным элементом) то получим машину IV. Единственное устройство управления выдает команду за командой сразу всем процессорным элементам. С одной стороны, отсутствие соединений между процессорными элементами делает дальнейшее наращивание их числа относительно простым, но с другой, сильно ограничивает применимость машин этого класса. Такую структуру имеет вычислительная система PEPE, объединяющая 288 процессорных элементов.

 

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

 

Заметим, что все машины с I-ой по V-ю придерживаются концепции разделения памяти данных и арифметико-логических устройств, предполагая наличие шины данных или какого-либо коммутирующего элемента между ними. Машина VI, названная матрицей с функциональной памятью (или памятью с встроенной логикой), представляет собой другой подход, предусматривающий распределение логики процессора по всему запоминающему устройству. Примерами могут служить как простые ассоциативные запоминающие устройства, так и сложные ассоциативные процессоры.

 

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

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

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

1. общая память - разделяемые переменные (GMSV);
2. распределенная память - разделяемые переменные (DMSV);
3. распределенная память - передача сообщений (DMMP);
4. общая память - передача сообщений (GMMP).

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

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

 

9. Классификация Базу

По мнению А.Базу (A.Basu), любую параллельную вычислительную систему можно однозначно описать последовательностью решений, принятых на этапе ее проектирования, а сам процесс проектирования представить в виде дерева. В самом деле, корень дерева - это вычислительная система, а последующие ярусы дерева, фиксируя уровень параллелизма, метод реализации алгоритма, параллелизм инструкций и способ управления, последовательно дополняют друг друга, формируя описание системы.

 

На первом этапе мы определяем, какой уровень параллелизма используется в вычислительной системе. Одна и та же операция может одновременно выполняться над целым набором данных, определяя параллелизм на уровне данных (обозначается буквой D на рисунке). Способность выполнять более одной операции одновременно говорит о параллелизме на уровне команд (буква O на рисунке). Если же компьютер спроектирован так, что целые последовательности команд могут быть выполнены одновременно, то будем говорить о параллелизме на уровне задач (буква T).