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

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

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

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

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

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

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

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

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

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

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

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

t( PEPE ) = t( CDC 7600 ) × (1×3, 288, 32) = = (15, 1, 12) × (1, 1×9, 60) × (1×3, 288, 32)

Поток данных последовательно проходит через  три подсистемы, что мы и отразили, соединив их знаком '×'.

Заметим, что все подсистемы последнего примера  достаточно сложны и, вообще говоря, исходя только из данного описания могут представляться по-разному. Чтобы внести большую ясность, аналогично операции конвейерного исполнения, Хендлер вводит операцию параллельного исполнения (+), фиксирующую возможность независимого использования процессоров разными задачами:

t(n,d,w) = [{(1,d,w) + ... + (1,d,w)] {n раз}

В случае CDC 7600 уточненная запись вида:

(15, 1, 12) × (1, 1×9, 60) = [(1, 1, 12) + ... +(1, 1, 12)]} {15 раз} × (1, 1×9, 60)

говорит о том, что каждая задача может  захватить свой периферийный процессор, а затем одна за одной они будут поступать в центральный процессор. И наконец третья операция - операция альтернативы (V), показывает возможные альтернативные режимы функционирования вычислительной системы. Чем больше для системы таких режимов, тем более гибкой архитектурой, по мнению Хендлера, она обладает. Например, компьютер C.mmp может быть запрограммирован для использования в трех принципиально разных режимах:

t( C.mmp ) = (16, 1, 16) V (1×16, 1,1 6) V (1, 16, 16).

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

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

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

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

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

Далее, среди 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, имеющим на внешнем уровне топологию гиперкуба, каждый узел которого является кластером процессоров с полной связью.

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

В 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.

Из  определений S_a, S_v и w сразу следует утверждение: если S - это поток ссылок со значениями из n чисел, то

w(S_a) = |S| и

w(S_v) = n|S|,

где |S| обозначает мощность множества S.

Каждую  пару (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)

Рассмотрим  классическую последовательную машину. Согласно классификации Флинна, она попадает в класс SISD, следовательно |I| = |D| = 1. Используя утверждение 1, получаем, что w(I_a) = w(D_a) = 1. Из-за того, что в подобного рода компьютерах команды декодируются последовательно, следует равенство w(I_v) = 1, а последовательное исполнение команд дает w(D_v) = 1. Поэтому описание однопроцессорной машины с фон-неймановской архитектурой будет выглядеть так:

I_1,1D_1,1

Теперь  возьмем две машины из класса 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. Несмотря на то, что и 'c' и 'm' в принципе не имеют определенной верхней границы, они отражают разные свойства архитектуры компьютера. Описатель 'c' предполагает жесткие ограничения сверху со стороны аппаратуры, и соответствующий параметр не может быть значительно увеличен относительно простыми средствами. Примером может служить число инструкций, упакованных в командном слове VLIW компьютера. С другой стороны, описатель 'm' используется тогда, когда обозначаемая величина может быть легко изменена, т.е. другими словами, компьютер по данному параметру масштабируем. Например, относительная проста в увеличении числа процессорных элементов в системе MPP является основанием для того, чтобы отнести ее к классу I_ssD_sm. Конечно же, различие между 'c' и 'm' в достаточной мере условное и, как правило, порождает массу вопросов. В частности, как описать машину, в которой процессоры связаны через общую шину? С одной стороны, нет никаких принципиальных ограничений на число подключаемых процессоров. Однако каждый дополнительный процессор увеличивает загруженность шины, и при достижении некоторого порога подключение новых процессоров бессмысленно. Как описать такую систему, 'c' или 'm'? Автор оставляет данный вопрос открытым.

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

• 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.