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

Общая классификация архитектур ЭВМ по признакам наличия параллелизма в потоках команд и данных была предложена Майклом Флинном в 1966 году[1] и расширена в 1972 году[2]. Все разнообразие архитектур ЭВМ в этой таксономии сводится к четырём классам:

• ОКОД — Вычислительная система с одиночным потоком команд и одиночным потоком данных
  (SISD, Single Instruction stream over a Single Data stream).
• ОКМД — Вычислительная система с одиночным потоком команд и множественным потоком данных
  (SIMD, Single Instruction, Multiple Data).
• МКОД — Вычислительная система со множественным потоком команд и одиночным потоком данных
  (MISD, Multiple Instruction Single Data).
• МКМД — Вычислительная система со множественным потоком команд и множественным потоком данных
  (MIMD, Multiple Instruction Multiple Data).

Типичными представителями SIMD являются векторные архитектуры. К классу MISD ряд исследователей относит конвейерные ЭВМ, однако это не нашло окончательного признания, поэтому можно считать, что реальных систем — представителей данного класса не существует. Класс MIMD включает в себя многопроцессорные системы, где процессоры обрабатывают множественные потоки данных.

Отношение конкретных машин к конкретному классу сильно зависит от точки зрения исследователя. Так, конвейерные машины могут быть отнесены и к классу SISD (конвейер — единый процессор), и к классу SIMD (векторный поток данных с конвейерным процессором) и к классу MISD (множество процессоров конвейера обрабатывают один поток данных последовательно), и к классу MIMD — как выполнение последовательности различных команд (операций ступеней конвейера) на множественным скалярным потоком данных (вектором).

Существуют два типа машин (процессоров), выполняющих несколько команд за один машинный такт:

• суперскалярные машины,
• VLIW-машины.

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

Дополнительно, чтобы снять ограничения последовательного выполнения команд, эти машины используют механизмы внеочередной выдачи и внеочередного завершения команд (англ. OoO, Out of Order execution), прогнозирование переходов (англ. Branch prediction), кэши целевых адресов переходов и условное (по предположению) выполнение команд.

В отличие от суперскалярных машин, VLIW-машина выполняет за один машинный такт фиксированное количество команд, которые сформатированы либо как одна большая команда, либо как пакет команд фиксированного формата. Планирование работы VLIW-машины всегда осуществляется компилятором. В типичной суперскалярной машине аппаратура может выдавать на выполнение от одной до восьми команд в один такт. Обычно эти команды должны быть независимыми и удовлетворять некоторым ограничениям, например таким, что в каждый такт не может выдаваться более одной команды обращения к памяти. Если какая-либо команда в выполняемом потоке команд является логически зависимой или не удовлетворяет критериям выдачи, на выполнение будут выданы только команды, предшествующие данной. Поэтому скорость выдачи команд в суперскалярных машинах переменна. Это отличает их от VLIW-машин, в которых полную ответственность за формирование пакета команд, которые могут выдаваться одновременно, несёт компилятор (и следовательно программист-разработчик компилятора), а аппаратура в динамике не принимает никаких решений относительно выдачи нескольких команд.

Использование VLIW приводит в большинстве случаев к быстрому заполнению небольшого объёма внутрикристальной памяти командами NOP (no operation), которые предназначены для тех устройств, которые не будут задействованы в текущем цикле. В существующих VLIW-архитектурах был найден большой недостаток, который был устранён делением длинных слов на более мелкие, параллельно поступающие к каждому устройству. Обработка множества команд независимыми устройствами одновременно является главной особенностью суперскалярной процессорной архитектуры.

Классификация машин MIMD-архитектуры:

• Переключаемые — с общей памятью и с распределённой памятью.
• Конвейерные.
• Сети — регулярные решётки, гиперкубы, иерархические структуры, изменяющие конфигурацию.

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

В 1972 году Фенг (T. Feng) предложил классифицировать вычислительные системы на основе двух простых характеристик. Первая — число n бит в машинном слове, обрабатываемых параллельно при выполнении машинных инструкций. Практически во всех современных компьютерах это число совпадает с длиной машинного слова. Вторая характеристика равна числу слов m, обрабатываемых одновременно данной ВС. Немного изменив терминологию, функционирование ВС можно представить как параллельную обработку n битовых слоёв, на каждом из которых независимо преобразуются m бит. Каждую вычислительную систему можно описать парой чисел (n, m). Произведение P = n x m определяет интегральную характеристику потенциала параллельности архитектуры, которую Фенг назвал максимальной степенью параллелизма ВС.

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

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

Подобная схема выделения уровней предполагает, что вычислительная система включает какое-то число процессоров каждый со своим устройством управления. Если на какое-то время не рассматривать возможность конвейеризации, то число устройств управления k, число арифметико-логических устройств d в каждом устройстве управления и число элементарных логических схем w в каждом АЛУ составят тройку для описания данной вычислительной системы C: t(C) = (k, d, w).

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

Классификация Скилликорна (1989) была очередным расширением классификации Флинна. Архитектура любого компьютера в классификации Скилликорна рассматривается в виде комбинации четырёх абстрактных компонентов: процессоров команд (Instruction Processor — интерпретатор команд, может отсутствовать в системе), процессоров данных (Data Processor — преобразователь данных), иерархии памяти (Instruction Memory, Data Memory — память программ и данных), переключателей (связывающих процессоры и память). Переключатели бывают четырёх типов — «1-1» (связывают пару устройств), «n-n» (связывает каждое устройство из одного множества устройств с соответствующим ему устройством из другого множества, то есть фиксирует попарную связь), «1-n» (переключатель соединяет одно выделенное устройство со всеми функциональными устройствами из некоторого набора), «n x n» (связь любого устройства одного множества с любым устройством другого множества). Классификация Скилликорна основывается на следующих восьми характеристиках:

• Количество процессоров команд IP
• Число ЗУ команд IM
• Тип переключателя между IP и IM
• Количество процессоров данных DP
• Число ЗУ данных DM
• Тип переключателя между DP и DM
• Тип переключателя между IP и DP
• Тип переключателя между DP и DP

• Симметричная мультипроцессорность (SMP)
• Массово-параллельная архитектура (MPP)

• Классификации архитектур вычислительных систем на основе пособия Вл. В. Воеводин, А. П. Капитонова. «Методы описания и классификации вычислительных систем». Издательство МГУ,1994.
• Бакалаврская работа с краткой классификацией ВС (самораспаковывающийся архив)
• http://hosting.ulstu.ru/umk/umk/ap/lections/transputers/microprocessor%20architectures/classif.htm (недоступная+ссылка)