Классификация Фишера для мелкозернистого паралеллизма

 

Мелкозернистый параллелизм – это параллелизм в обработке смежных ко

манд, операторов, небольших векторов данных.

Чтобы реализовать этот вид параллелизма, компилятор и аппаратура должны выполнить следующие действия: определить зависимости между операциями; определить операции, которые не зависят ни от каких еще не завершенных операций; спланировать время и место выполнения операций.

В соответствиис этим архитектуры с МЗП можно классифицировать сле-

дующим образом:

1. Последовательностные архитектуры: архитектуры, в которых компиляторне помещает в программу в явном виде какую-либо информацию о параллелизме. Компилятор только перестраивает код для упрощения действий аппа-

ратуры по планированию. Представителями этого класса являются супер-

скалярные процессоры.

2. Архитектуры с указанием зависимостей: в программе компилятором явно представлены зависимости, которые существуют между операциями, неза-

висимость между операциями определяет аппаратура. Этот класс представ-

ляют процессоры потока данных.

3. Независимостные архитектуры: архитектуры, в которых компилятор помещает в программу всю информацию о независимости операций друг от друга. Это VLIW-архитектуры.

Классы микропроцессоров по Фишеру

Тип архитектуры	Кто определяет зависимость по данным	Кто определяет независимость по данным	Кто планирует время и место выполнения	Представители
Последователь- ностные	Аппаратура	Аппаратура	Аппаратура	Сперскалярный Pentium
Зависимостные	компилятор	Аппаратура	Аппаратура	Потоковый Pentium Pro
Независимостн- ые	компилятор	компилятор	компилятор	VLIW про- цессоры

Суперскалярные процессоры.

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

В некоторых случаях компилятор может для облегчения работы аппаратуры производить упорядочивание команд. Если команда не зависит от всех других команд, она может быть запущена. Возможны два варианта последовательной архитектуры: суперконвейер и суперскалярная организация. В первом случае параллелизм на уровне команд нужен для того, чтобы исключить остановки конвейера. Здесь аппаратура должна определить зависимости между командами и принять решение, когда запускать очередную команду. Если конвейер способен вырабатывать один результат в каждом такте, такой конвейер называется суперконвейером. За счет уменьшения объема работы в одном такте возникает возможность повысить частоту тактирования процессора. При этом, чем длинее конвейер, тем выше частота. Современные конвейеры имеют длину до 30 этапов.

Дальнейшая цель – построение процессора с несколькими конвейерами,

что позволяет запускать несколько команд каждый такт. Такой процессор называется суперскалярным.

 

 

ЛЕКЦИЯ 8.

Процессоры потока данных.

Существует два типа управления выполнением программы: управление от потока команд (IF − Instruction Flow) и управление от потока данных (DF − Data Flow). Если в ЭВМ первого типа используется традиционное выполнение команд по ходу их расположения в программе, то применение ЭВМ второго типа предполагает активацию операторов по мере их текущей готовности.

В случае DF все узлы информационного графа задачи представляются в виде отдельных операторов:

КОП О1, О2, A3, БС

где О1, О2 — поля для приема первого и второго операндов от других операторов; A3 − адрес (имя) оператора, куда посылается результат; БС − блок событий. В БС записывается число, равное количеству операндов, которое нужно принять, чтобы начать выполнение данного оператора. После приема очередного операнда из БС вычитается единица, когда в БС оказывается нуль, оператор начинает выполняться. Программа полностью повторяет ИГ, но ее операторы могут располагаться в памяти в произвольном порядке. Выполняться они будут независимо от начального расположения строго в соответствии с зависимостью по данным. Это и есть управление потоком данных. Считается, что такая форма представления ИГ обеспечивает наибольший потенциальный параллелизм.

В случае зависимостной архитектуры компилятор или программист выяв-

ляют параллелизм в программе и представляют его аппаратуре путем описания

зависимостей между операциями в машинной программе. Аппаратура все же

еще должна определить на этапе исполнения, когда каждая операция становит-

ся независимой от всех других операций, и тогда выполнить планирование.

Но прежде рассмотрим вопрос о влиянии количества регистров общего на-

значения РОН на величину параллелизма. Существует несколько видов памяти

с разным временем доступа и объемом хранимой информации:

 

Тип памяти	Время доступа, такты	Обьем
РОН		Обычно до 16 байт
Кэш	1-2	Сотни килобайт
Оперативная память	20-50	гигабайты

Регистры – самая быстрая память. Обычно их немного. Рассмотрим сле-

дующую ситуацию. Пусть требуется сложить четыре числа - .

Рассмотрим эту операцию для двух случаев: в микропроцессоре имеется 2 или 4 РОН. В программе для двух РОН из-за недостатка регистров приходится промежуточные результаты записывать в память, поэтому программы удлиняется и в нейт нет параллелизма. Если предположить, что одно обращение к памяти занимает 3 такта, а сложение – 1 такт, то приведенная программа выполняется за 30 тактов.

Программа

mov r1, [a1]

mov r2, [a2]

r1=r1+r2

 

mov [b1], r1

mov r1, [a3]

mov r2, [a4]

r1=r1+r2

 

mov [b2], r1

mov r1, [b1]

mov r2, [b2]

r1=r1+r2

mov [c], r1

 

Увеличение числа регистров до 4 –ех устраняет использование промежу-

точных переменных и позволяет параллельное выполнение операций:

mov r1, [a1]

mov r2, [a2]

mov r3, [a3]

mov r4, [a4]

r1=r1+r2, r3=r3+r4

r1=r1+r2

mov [c], r1

Итого, 17 тактов, что значительно меньше, чем в предыдущем случае. При увеличении объема данных и числа РОН выигрыш будет намного больше.

Микропроцессор Pentium Pro компании Intel (рис) построен по принципу

управления от потока данных (DF), отсюда и получил название потокового.

Главное в потоковом процессоре − выполнить команду сразу, как только станут доступны входные операнды и освободятся необходимые функциональные устройства

Блок ВД (выборка и декодирование команд) по существу является микро-

программной частью компилятора. Он обеспечивает:

• Чтение команд из КЭШ и их преобразование из формата i86 в формат DF (управление от потока данных)

• Запись команд в буфер команд в буфер команд БК. В БК команды пред-

ставлены в трехадресном формате. Поскольку в системе команд i 86 мало

РОН (всего 8), то для устранения ложных зависимостей по данным в МП

Pentium Pro введено 40 дополнительных регистров, которые недоступны

программисту. Они используются аппаратурой для временного хранения

результатов. Обозначим эти регистры временного хранения через V. Тогда

 

на рисунке V1, V2 и VР обозначают соответственно номера регистров для

хранения первого, второго операндов и результата.

Блок ПВ (планирование и выполнение) является центральным блоком МП Pentium Pro. Именно он выполняет команды в порядке их готовности. ПВ содержит несколько АЛУ и устройств обращения к памяти. За один такт ПВ выполняет следующие действия:

• Выделяет в БК команды, готовые к исполнению.

• Планирует и назначает на исполнение до пяти команд, поскольку в ПВ

имеется пять исполнительных устройств.

• Выполняет эти команды.

• Передает результаты в блок БК, вычитает единицу из БС и в случае воз

можности устанавливает в командах признак готовности.

Чтобы блок ПВ мог выполнять за один такт до 3...5 команд, необходимо,

чтобы в БК находилось до 20...30 команд. По статистике среди такого объема

команд в среднем имеется имеется 4...5 команд условных переходов. Следова-

тельно, в БК находится некоторая трасса выполнения команд. Выбор таких

наиболее вероятных трасс является новой функцией МП с непоследовательным

выполнением команд. Эта функция выполняется в блоке ВД на основе расши-

ренного до 512 входов буфера истории переходов.

Поскольку реально вычисленный в ПВ адрес перехода не всегда совпадает с предсказанным в блоке ВД, то вычисление в ПВ выполняется условно, т. е. результат записывается в регистр временного хранения. Только после того, как

установлено, что переход выполнен правильно, блок удаления команд УК вы-

водит из БК все выполненные команды, расположенные за командой условного

перехода, преобразует их в формат системы i 86 и производит запись результа-

тов по адресам, указанным в исходной программе.