Лекция 7.

Планирование ЯПФ базовых блоков.

Спланировать – означает указать, на каком процессоре и в каком такте будет запущен на исполнение некоторый блок вычислений.

Алгоритмы планирования связаны с природой графа управления: состоит

ли он из одного или нескольких базовых блоков, является ли граф управления

циклическим или ациклическим графом в случае нескольких базовых блоков.

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

на каждой обратной дуге графа управления.

Метод списочных расписаний.

Планирование для единичного ББ заключается в построении как можно более короткого плана. Поскольку эта проблема имеет переборный характер, внимание было сосредоточено на эвристических алгоритмах планирования. Среди таких алгоритмов наиболее подходящими оказались списочные расписания. Алгоритмы планирования по списку при линейном росте времени планирования при увеличении числа планируемых объектов, дают результаты, отличающиеся от оптимальных всего на 10-15%.

В таких расписаниях оператором присваиваются приоритеты по тем или

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

убыванию или возрастанию приоритета в виде линейного списка. В процессе

планирования затем осуществляется назначение операторов процессорам в по-

рядке их извлечения из списка.

На рисунке (а) представлена исходная ЯПФ. Номера вершин даны внутри

кружков, а время исполнения — около вершин. На рисунке (б) приведены уровни вершин. Под уровнем вершины понимается длина наибольшего пути из этой вершины в конечную. Построим для примера два расписания из множества возможных. Для каждого из них найдем характеристики всех вершин по соот

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

личин приоритетов этих вершин.

В первом расписании величина приоритета вершины есть ее уровень. Это

расписание УР. Во втором расписании величина приоритета вершины есть ее

уровень без учета времени исполнения, то есть здесь веса всех вершин полага-

ются одинаковыми (единичными).

УР		УР без учета веса
П	В	П	В
14	1	5	1
13	3	4	4
9	4	4	2
6	7	4	3
5	2	3	5
4	6	3	7
4	5	3	6
4	11	2	10
3	9	2	9
3	8	2	8
2	10	2	11
1	12	1	12

б) Приоритеты и списки вершин

(П— приоритеты, В — номера вершин)

в) Уровни вершин

1	2	3	4	5	6	7	8	9	10	11	12	номера вершины
14	5	13	9	4	4	6	3	3	2	4	1	уровни

г) Реализация расписаний (Р1, Р2 — процессоры, X — простой процессора)

УР (по уровню вершин)

Р1	1	3	3	3	3	3	3	3	7	7	7	9	9	12
Р2	Х	4	4	4	2	11	11	11	6	5	8	8	10	Х

УР без учета веса вершин

Р1	1	4	4	4	11	11	11	Х	Х	5	6	8	8	9	9	12
Р2	Х	2	3	3	3	3	3	3	3	7	7	7	10	Х	Х	Х

Об оптимальности расписания можно судить по количеству простоев про-

цессоров. Первое расписание дает 2, второе — 5.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Вопросы для самоконтроля

1. Что такое суперскалярные процессоры?