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

Достаточно  ясно, что не нужно рассматривать  все возможные комбинации описателей 's', 'c' и 'm', так как архитектура реальных компьютеров накладывает ряд вполне разумных ограничений. Очевидно, что число адресов w(S_a) не должно превышать числа возвращенных значений w(S_v), которое компьютер может обработать. Отсюда следуют неравенства: w(I_a) <= w(I_v) и w(D_a) <= w(D_v). Другим естественным предположением является тот факт, что число выполняемых команд не должно превышать числа обрабатываемых данных: w(I_v) <= w(D_v).

Подводя итог, можно отметить два положительных  момента в классификации Шнайдера: более избирательная систематизация SIMD компьютеров и возможность  описания нетрадиционных архитектур типа систолических массивов или компьютеров  с длинным командным словом. Однако почти все вычислительные системы  типа MIMD опять попали в один и  тот же класс I_mmD_mm. Это и не удивительно, так как критерий классификации, основанный лишь на потоках команд и данных без учета распределенности памяти и топологии межпроцессорной связи, слишком слаб для подобных систем.

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

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

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

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

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

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

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

Второй  уровень в классификационном  дереве фиксирует метод реализации алгоритма. С появлением сверхбольших интегральных схем (СБИС) стало возможным  реализовывать аппаратно не только простые арифметические операции, но и алгоритмы целиком. Например, быстрое  преобразование Фурье, произведение матриц и LU-разложение относятся к классу тех алгоритмов, которые могут  быть эффективно реализованы в СБИС'ах. Данный уровень классификации разделяет системы с аппаратной реализацией алгоритмов (буква C на схеме) и системы, использующие традиционный способ программной реализации (буква P).

Третий  уровень конкретизирует тип параллелизма, используемого для обработки  инструкций машины: конвейеризация инструкций (P_i) или их независимое (параллельное) выполнение (P_a). В большей степени этот выбор относится к компьютерам с программной реализацией алгоритмов, так как аппаратная реализация всегда предполагает параллельное исполнение команд. Отметим, что в случае конвейерного исполнения имеется в виду лишь конвейеризация самих команд, разбивающая весь цикл обработки на выборку команды, дешифрацию, вычисление адресов и т.д., - возможная конвейеризация вычислений на данном уровне не принимается во внимание.

Последний уровень данной классификации определяет способ управления, принятый в вычислительной системе: синхронный (S) или асинхронный (A). Если выполнение команд происходит в строгом порядке, определяемом только сигналами таймера и счетчиком команд, то будем говорить о синхронном способе управления. Если же для инициации команды определяющими являются такие факторы, как, например, готовность данных, то попадаем в класс машин с асинхронным управлением. Наиболее характерными представителями систем с асинхронным управлением являются data-driven и demand-driven компьютеры

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

Изучение  систолических массивов, имеющих, как  правило, одномерную или двумерную  структуру, показывает, что обозначения DCP_aS и DCP_aA могут быть использованы для их описания в зависимости от того, как происходит обмен данными: синхронно или асинхронно. Систолические деревья, введенные Кунгом для вычисления арифметических выражений могут быть описаны как OCP_aS либо OCP_aA по аналогичным соображениям. Конвейерные компьютеры, такие, как IBM 360/91, Amdahl 470/6 и многие современные RISC процессоры, разбивающие исполнение всех инструкций на несколько этапов, в данной классификации имеют обозначение OPP_iS. Более естественное применение конвейеризации происходит в векторных машинах, в которых одна команда применяется к вектору независимых данных, и за счет непрерывного использования арифметического конвейера достигается значительное ускорение. К таким компьютерам подходит обозначение DPP_iS. Матричные процессоры, в которых целое множество арифметических устройств работает одновременно в строго синхронном режиме, принадлежат к группе DPP_aS. Если вычислительная система подобно CDC 6600 имеет процессор с отдельными функциональными устройствами, управляемыми централизованно, то ее описание выглядит так: OPP_aS. Data-flow компьютеры, в зависимости от особенностей реализации, могут быть описаны либо как OPP_iA, либо OPP_aA.

Системы с несколькими процессорами, использующими  параллелизм на уровне задач, не всегда можно корректно описать в  рамках предложенного формализма. Если процессоры дополнительно не используют параллелизм на уровне операций или  данных, то для описания можно использовать лишь букву T. В противном случае, Базу предлагает использовать знак '*' между символами, обозначающими уровни параллелизма, одновременно присутствующие в системе. Например, комбинация T*D означает, что некоторая система может одновременно исполнять несколько задач, причем каждая из них может использовать векторные команды.

Очень часто в реальных системах присутствуют особенности, характерные для компьютеров  из разных групп данной классификации. В этом случае для корректного  описания автор использует знак '+'. Например, практически все векторные  компьютеры имеют скалярную и  векторную части, что можно описать  как OPP_iS+DPP_iS (пример - это TI ASC и CDC STAR-100). Если в системе есть возможность одновременного выполнения более одной векторной команды (как в CRAY-1) то для описания векторной части можно использовать запись O*DPP_iS, а полное описание данного компьютера выглядит так:O*DPP_iS+OPP_iS. Действуя по такому же принципу, можно найти описание и для систем CRAY X-MP и CRAY Y-MP. В самом деле, данные системы объединяют несколько процессоров, имеющих схожую с CRAY-1 структуру, и потому их описание имеет вид: T*(O*DPP_iS+OPP_iS).

Классификация Кришнамарфи

Е.Кришнамарфи для классификации параллельных вычислительных систем предлагает использовать четыре характеристики, очень похожие на характеристики классификации А.Базу:

1. степень гранулярности;
2. способ реализации параллелизма;
3. топология и природа связи процессоров;
4. способ управления процессорами.

Принцип построения классификации  очень прост. Для каждой степени  гранулярности будем рассматривать  все возможные способы реализации параллелизма. Для каждого полученного  таким образом варианта рассмотрим все комбинации топологии связи  и способов управления процессорами. В результате получим дерево (см. pисунок 14), в котором каждый ярус соответствует своей характеристике, каждый лист представляет отдельную группу компьютеров в данной классификации, а путь от вершины дерева однозначно определяет значения указанных выше характеристик. Разберем характеристики подробнее.

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

Наконец, последний, четвертый  уровень - способ управления процессорами, определяет общий принцип функционирования всей совокупности процессоров вычислительной системы: синхронный, dataflow или асинхронный.

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

Векторно-конвейерные компьютеры:

• гранулярность - на уровне данных;
• реализация параллелизма - аппаратная;
• связь процессоров - простая топология со средней связностью;
• способ управления - синхронный.

Классические мультипроцессоры:

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

Матрицы процессоров:

• гранулярность - на уровне данных;
• реализация параллелизма - аппаратная;
• связь процессоров - двумерные массивы с сильной связностью;
• способ управления - синхронный.

Систолические массивы:

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

Архитектура типа wavefront:

• гранулярность - на уровне данных;
• реализация параллелизма - аппаратная;
• связь процессоров - двумерная топология с сильной связностью;
• способ управления - dataflow.

Архитектура типа dataflow:

• гранулярность - на уровне команд;
• реализация параллелизма - комбинированная;
• связь процессоров - простая топология с сильной либо средней связностью и использованием принципа dataflow;
• способ управления - асинхронно-dataflow.