Классификация параллельных вычислительных систем (Tlgvvnsntgenx hgjgllyl,ud] fdcnvlnmyl,ud] vnvmyb)

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

Общая классификация архитектур ЭВМ по признакам наличия параллелизма в потоках команд и данных была предложена Майклом Флинном в 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 машины

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

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

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

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

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

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

Классификация Хокни (Roger W. Hockney)

Классификация машин 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

См. также

Примечания

↑ Flynn MJ (1966) Very high speed computers. Proc IEEE 54:1901–1901
↑ M.J. Flynn. Some computer organizations and their effectiveness. IEEE Transactions on Computers, 21(9): 948–960, 1972

Ссылки

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

[1] Flynn MJ (1966) Very high speed computers. Proc IEEE 54:1901–1901

[2] M.J. Flynn. Some computer organizations and their effectiveness. IEEE Transactions on Computers, 21(9): 948–960, 1972

[1]

[2]

	Одиночный поток команд (single instruction)	Множество потоков команд (multiple instruction)
Одиночный поток данных (single data)	SISD (ОКОД)	MISD (МКОД)
Множество потоков данных (multiple data)	SIMD (ОКМД)	MIMD (МКМД)