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

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

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

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

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

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Несмотря на то, что классификация  Е. Кришнамарфи построена лишь на четырех признаках, она позволяет выделить и описать такие "нетрадиционные" параллельные системы, как систолические массивы, машины типа dataflow и wavefront. Однако эта же простота является и основной причиной ее недостатков: некоторые архитектуры нельзя однозначно отнести к тому или иному классу, например, компьютеры с архитектурой гиперкуба и ассоциативные процессоры. Для более точного описания таких машин потребуется ввести еще целый ряд характеристик, таких, как размещение задач по процессорам, способ маршрутизации сообщений, возможность реконфигурации, аппаратная поддержка языков программирования и другие. Вместе с тем ясно, что эти признаки формализовать гораздо труднее, поэтому есть опасность вместо ясности внести в описание лишь дополнительные трудности.

11. Классификация Дазгупты

Одним из последних исследований по классификации архитектур, по-видимому, является работа С. Дазгупты (S.Dasgupta), вышедшая в 1990 году. Автор использовал позитивные идеи работы Скилликорна, которая была рассмотрена ранее в данном обзоре. Пытаясь расширить описательные возможности классификации, он разработал иерархическую систему для классификации архитектур. Изложим ее основные идеи.

Предлагаемая  система построена на основе семи элементарных понятий - базовых элементов архитектуры.

Базовые элементы архитектуры:

• iM - память с расслоением - память, из которой можно выбрать несколько единиц информации за один цикл памяти;
• sM - простая память - память, из которой можно выбрать единицу информации за цикл памяти;
• C - программируемая или непрограммируемая кэш-память. Буферные регистры, подобные регистрам CRAY-1, также описываются, как кэш-память;
• sI - простой (неконвейерный) процессор для подготовки команды к исполнению;
• pI - конвейерный процессор для подготовки команды к исполнению;
• sX - простой процессор для исполнения команды;
• pX - конвейерный процессор для исполнения команды.

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

Если  архитектура содержит N элементов  типа A, которые могут работать в  системе параллельно и независимо (обозначим эту возможность A_N), то A_N будем называть сложным элементом типа A. Считается, что составляющие сложного элемента не имеют между собой физической связи. Например:

sM₃ - три блока простой памяти, к которым можно обращаться параллельно и независимо;

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

Назовем кэш-процессором CP объединение C-элемента с I, X или другими CP.

Процессором для подготовки команд I" назовем MCP, который представляет собой законченную подсистему подготовки команды к исполнению.

Процессором для исполнения команд X" назовем MCP, который представляет собой законченную подсистему для выполнения команды.

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

Полным  описанием архитектуры может  служить одиночная или повторяющаяся  последовательность, составленная из I" и X" процессоров.

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

Каждая  формула служит описанием некоторой  структуры. Введем два оператора, устанавливающих соответствие между формулой и структурой.

1. Пусть R - формула. Тогда оператор Rep(R) описывает следующую структуру:

Другими словами, если R = AN, то структура описывается  оператором Rep(R).

2. Пусть R = R1.R2. ... .Rn - формула, где Ri может быть базовым или сложным элементом, простым или сложным процессором. Обозначим head(R) = R1 - самую левую составляющую в формуле; tail(R) = Rn - самую правую составляющую в формуле.

Введем  второй оператор Link. Пусть R1 и R2 - формулы. Тогда Link(R1, R2):

а) если tail(R1) и head(R2) - простые составляющие, то

б) если tail(R1) простая, а head(R2) - сложная составляющая вида Z_n, то

в) если tail(R1) - сложная составляющая вида W_n, а head(R2) - простая, то

г) если tail(R1) - сложная составляющая вида W_n, а head(R2) - сложная составляющая вида Z_m, то

Легко понять, что оператор Link явно описывает связи между элементами архитектуры. В классификации Скилликорна этим целям служили переключатели четырех типов (см. классификацию Д.Скилликорна).

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

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

Множество свойств, которые являются определяющими  при отнесении объекта к какому-либо классу, назовем классификационными характеристиками (TC - taxonomic characters). В нашем случае введенные выше базовые элементы архитектуры определяют эти классификационные характеристики.

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

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