Параллелизм как способ параллельной обработки данных (стр. 4 из 5)

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.

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

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

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

Рассмотрим упомянутый выше компьютер Connection Machine 2. В терминах данных характеристик его можно описать:

(1, 1, 1–1, n, n, n-n, 1-n, nxn),

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

Для сильно связанных мультипроцессоров (BBN Butterfly, C.mmp) ситуация иная. Такие системы состоят из множества процессоров, соединенных с модулями памяти с помощью динамического переключателя. Задержка при доступе любого процессора к любому модулю памяти примерно одинакова. Связь и синхронизация между процессорами осуществляется через общие (разделяемые) переменные. Описание таких машин в рамках данной классификации выглядит так: (n, n, n-n, n, n, nxn, n-n, нет), а саму архитектуру можно изобразить так, как на следующем рисунке:

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

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