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

Недостатки предложенной классификации достаточно очевидны и связаны со способом вычисления ширины битового слоя m. По существу Фенг не делает никакого различия между процессорными матрицами, векторно-конвейерными и многопроцессорными системами. Не делается акцент на том, за счет чего компьютер может одновременно обрабатывать более одного слова: множественности функциональных устройств, их конвейерности или же какого-то числа независимых процессоров. Если в системе N независимых процессоров имеют каждый по F конвейерных функциональных устройств с длиной конвейера L, то для вычисления ширины битового слоя надо просто найти произведение данных характеристик.

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

 

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

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

Предложенная классификация  базируется на различии между тремя  уровнями обработки данных в процессе выполнения программ:

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

 

Таким образом, подобная схема  выделения уровней предполагает, что вычислительная система включает какое-то число процессоров каждый со своим устройством управления. Каждое устройство управления связано с несколькими арифметико-логическими устройствами, исполняющими одну и ту же операцию в каждый конкретный момент времени. Наконец, каждое АЛУ объединяет несколько элементарных логических схем, ассоциированных с обработкой одного двоичного разряда (число ЭЛС есть ничто иное, как длина машинного слова). Если на какое-то время не рассматривать возможность конвейеризации, то число устройств управления k , число арифметико-логических устройств d в каждом устройстве управления и число элементарных логических схем w в каждом АЛУ составят тройку для описания данной вычислительной системы C:

t(C) = (k, d, w)

Теперь можно расширить  возможности описания, допустив возможность  конвейерной обработки на каждом из уровней. В самом деле, конвейерность на самом нижнем уровне (т.е. на уровне ЭЛС) это конвейерность функциональных устройств. Если функциональное устройство обрабатывает w-разрядные слова на каждой из w' ступеней конвейера, то для характеристики параллелизма данного уровня естественно рассмотреть произведение w×w'. Знак умножения × будем использовать на каждом уровне чтобы отделить число, представляющее степень параллелизма, от числа ступеней в конвейере. Компьютер TI ASC имеет четыре конвейерных устройства по восемь ступеней в каждом для обработки 64-х разрядных слов, следовательно, он может быть описан так:

t( TI ASC ) = (1,4,64×8)

Следующий уровень конвейерной  обработки - это конвейеризация на уровне команд. Предполагается, что в вычислительной системе есть несколько функциональных устройств, которые могут работать одновременно в рамках одного потока команд (в настоящее время используется специальный термин для обозначения данной возможности - сцепление функциональных устройств). Классическим примером этому могут служить компьютеры фирмы Cray Research. А исторически первой, по всей вероятности, является машина CDC 6600, содержащая десять независимых последовательных функциональных устройств, способных подавать результат своей работы на вход другим функциональным устройствам, образуя единый поток команд:

t(CDC 6600) = (1,1×10,~64)

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

Наконец, нам осталось рассмотреть  конвейеризацию на самом верхнем  уровне, известную как макро-конвейер. Поток данных, проходя через один процессор, поступает на вход другому, возможно через некоторую буферную память. Если независимо работают n процессоров, то в идеальной ситуации при отсутствии конфликтов и полной сбалансированности получаем ускорение в n раз по сравнению с использованием только одного процессора. Так компьютер PEPE, имея фактически три независимых системы из 288-ми устройств, описывается следующим образом:

t( PEPE ) = (1×3,288,32)

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

t( PEPE ) = (k×k',d×d',w×w')

интерпретируется так:

• k - число процессоров (каждый со своим УУ), работающих параллельно
• k' - глубина макроконвейера из отдельных процессоров
• d - число АЛУ в каждом процессоре, работающих параллельно
• d' - число функциональных устройств АЛУ в цепочке
• w - число разрядов в слове, обрабатываемых в АЛУ параллельно
• w' - число ступеней в конвейере функциональных устройств АЛУ

Очевидна связь между  классификацией Фенга и классификацией Хендлера: для получения максимальной степени параллелизма в терминах Фенга надо найти произведение всех шести величин в описании Хендлера. Здесь же заметим, что заложив в основу своей схемы явное указание на присутствующий параллелизм и возможную конвейеризацию, В.Хендлер сразу снимает массу вопросов, характерных для предшествующих схем Флинна, Шора и Фенга, по крайней мере, в плане описания векторно-конвейерных машин.

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

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

 

5. Классификация Шнайдера

В 1988 году Л.Шнайдер (L.Snyder) предложил новый подход к описанию архитектур параллельных вычислительных систем, попадающих в класс SIMD систематики Флинна. Основная идея заключается в выделении этапов выборки и непосредственно исполнения в потоках команд и данных. Именно разделение потоков на адреса и их содержимое позволяет описать такие ранее "неудобные" для классификации архитектуры, как компьютеры с длинным командным словом, систолические массивы и целый ряд других.

Введем необходимые для  дальнейшего изложения понятия  и обозначения. Назовем потоком ссылок ( reference stream ) S некоторой вычислительной системы конечное множество бесконечных последовательностей пар:

S = { (a₁ < t₁ > ) (a₂ < t₂ > )...,        

(b₁ < u₁ > ) (b₂ < u₂ > )...,        

(c₁ < v₁ > )(c₂ < v₂ > )...},

где первый компонент каждой пары - это неотрицательное целое  число, называемое адресом, второй компонент - это набор из n неотрицательных целых чисел, называемых значениями, причем n одинаково для всех наборов всех последовательностей. Например, пара (b₂ < u₂ > ) определяет адрес b₂ и значение < u₂ > . Если значения рассматривать как команды, то из потока ссылок получим поток команд I; если же значения интерпретировать как данные, то соответствующий поток - это поток данных D.

Пусть S произвольный поток ссылок. Последовательность адресов потока S, обозначаемая S_a, - это последовательность, чей i-й элемент - набор, сформированный из адресов i-х элементов каждой последовательности из S:

S_a = < a₁ b₁ ...c₁ > , < a₂ b₂ ...c₂ > ,...

потока S, обозначаемая S_v, - это последовательность, чей i-й элемент - набор, образованный слиянием наборов значений i-х элементов каждой последовательности из S:

S_v = < t₁ u₁ ...v₁ > , < t₂ u₂ ...v₂ > ,...

Если S_x - последовательность элементов, где каждый элемент - набор из n чисел, то для обозначения "ширины" последовательности будем пользоваться обозначением: w(S_x) = n.

Каждую пару (I, D) с потоком команд I и потоком данных D будем называть вычислительным шаблоном, а все компьютеры будем разбивать на классы в зависимости от того, какой шаблон они могут исполнить. В самом деле, компьютер может исполнить шаблон (I, D), если он в состоянии:

• выдать w(I_a) адресов команд для одновременной выборки из памяти;
• декодировать и проинтерпретировать одновременно w(I_v) команд;
• выдать одновременно w(D_a) адресов операндов и
• выполнить одновременно w(D_v) операций над различными данными.

Если все эти условия  выполнены, то компьютер может быть описан следующим образом:

I_w(Ia)w(Iv)D_w(Da)w(Dv)

Возьмем две машины из класса SIMD: Goodyear Aerospace MPP и ILLIAC IV, причем не будем принимать во внимание разницу в способах обработки данных отдельными процессорными элементами. Единственный поток команд означает |I| = 1 для обеих машин. По тем же соображениям, использованным только что для последовательной машины, для потока команд получаем равенство w(I_a) = w(I_v) = 1. Далее, вспомним, что для доступа к операндам устройство управления MPP рассылает один и тот же адрес всем процессорным элементам, поэтому в этой терминологии MPP имеет единственную последовательность в потоке данных, т.е. |D| = 1. Однако затем выборка данных из памяти и последующая обработка осуществляется в каждом процессорном элементе, поэтому w(D_v)=16384, а вся система MPP может быть описана так:

I_1,1D_1,16384

В ILLIAC IV устройство управления, так же, как и в MPP, рассылает  один и тот же адрес всем процессорным элементам, однако каждый из них может  получить свой уникальный адрес, добавляя содержимое локального индексного регистра. Это означает, что |D| = 64 и в системе присутствуют 64 потока адресов данных, определяющих одиночные потоки операндов, т.е. w(D_a) = w(D_v) = 64. Суммируя сказанное, приходим к описанию ILLIAC IV:

I_1,1D_64,64

Для более четкой классификации  Шнайдер вводит три предиката для обозначения значений, которые могут принимать величины w(I_a), w(I_v), w(D_a) и w(D_v):

s - предикат "равен 1";

с - предикат "от 1 до некоторой (небольшой) константы";

m - предикат "от 1 до произвольно большого конечного числа".

На основе указанных предикатов можно выделить следующие классы компьютеров:

• I_ssD_ss - фон-неймановские машины;
• I_ssD_sc - фон-неймановские машины, в которых заложена возможность выбирать данные, расположенные с разным смещением относительно одного и того же адреса, над которыми будет выполнена одна и та же операция. Примером могут служить компьютеры, имеющие команды, типа одновременного выполнения двух операций сложения над данными в формате полуслова, расположенными по указанному адресу.
• I_ssD_sm - SIMD компьютеры без возможности получения уникального адреса для данных в каждом процессорном элементе, включающие MPP, Connection Machine 1 так же, как и систолические массивы.
• I_ssD_cc - многомерные SIMD машины - фон-неймановские машины, способные расщеплять поток данных на независимые потоки операндов;
• I_ssD_mm - это SIMD компьютеры, имеющие возможность независимой модификации адресов операндов в каждом процессорном элементе, например, ILLIAC IV и Connection Machine 2.
• I_scD_cc - вычислительные системы, выбирающие и исполняющие одновременно несколько команд, для доступа к которым используется один адрес. Типичным примером являются компьютеры с длинным командным словом (VLIW).
• I_ccD_cc - многомерные MIMD машины. Фон-неймановские машины, которые могут расщеплять свой цикл выборки/выполнения с целью обработки параллельно нескольких независимых команд.
• I_mmD_mm - к этому классу относятся все компьютеры типа MIMD.

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