List Scheduling

Если никак не влиять на последовательность выполнения инструкций, то за такт у нас будет выполняться не более одной инструкции. Но для Itanium’а это было бы слишком расточительным, т.к. он способен выполнить за такт до 6 инструкций, при этом рационально использовать широкие команды (very long instruction word).
Оптимальное планирование параллельного потока инструкций является одной из важнейших задач оптимизирующей компиляции, т.к. от этого напрямую зависит итоговая производительность системы.

Рассмотрим простейшее планирование инструкций, именно – планирование по списку. Нам понадобятся 2 списка: ready_list (готовые узлы) и wait_list( ждущие узлы).

Пусть есть линейный участок (Basic Block), который имеет следующий граф зависимостей:

graph1.JPG

Для простоты будем считать, что за один такт могут выполняются 2 инструкции. Для алгоритма нужен построенный граф зависимостей и машинная модель (оттуда, например, можно взять задержку).

Берем саксессоры от begin’а (1.mov, 2.mov, 3.mov) и записываем их в ready_list (задержка 0):
t  = 0 (нулевой такт)
ready_list = { 1.mov, 2.mov, 3.mov }

Планируем первую и вторую инструкции в широкую команду:
sched 1.mov
sched 2.mov

В wait_list записываем саксессоры планируемых инструкций(1-я и 2-я), в скобках пишем задержку:
wait_list = {4.cmp(1), 5.add(1), 7.add(1)}  

Удаляем из ready_list спланированные инструкции:
ready_list = { 3.mov }

t = 1
Обновляем задержки:
wait_list = {4.cmp(0), 5.add(0), 7.add(0)}  
Заносим одну из инструкций wait_list’а в ready_list:
ready_list = { 3.mov, 4.cmp }
wait_list = {5.add(0), 7.add(0)}  
Идем по списку ready_list и планируем инструкции:
sched 3.mov
sched 4.cmp

Обновляем списки (инструкции 5.add и 7.add продолжают ждать), заносим в wait_list саксессоры 4.cmp:
ready_list = { }
wait_list = {5.add(1), 7.add(1), 6.mul(1), 8.mul(1)}  

t = 2
Обновляем задержки:
wait_list = {5.add(0), 7.add(0), 6.mul(0), 8.mul(0)}
Пишем в ready_list пару инструкций с нулевой задержкой:
ready_list = {5.add, 7.add}
Идем по списку ready_list и планируем инструкции:
sched 5.add
sched 7.add

ready_list = {}
wait_list = {6.mul(1), 8.mul(1)}

Аналогично поступаем дальше:
t = 3
wait_list = {6.mul(0), 8.mul(0)}
ready_list = {6.mul, 8.mul}

sched 6.mul
sched 8.mul

ready_list = { }
wait_list = {9.add(1)}

t = 4
wait_list = {9.add(0)}
ready_list = {9.add}

sched 9.add

wait_list = {}
ready_list = {}

Т.е. программа работает за 5 тактов, вместо 9 тактов при линейном исполнении.

Это был классический алгоритм “List Scheduling”, который имеет ряд недостатков, в результате чего вычислительные ресурсы архитектуры распределяются не оптимально.
Уже на простых примерах с инструкциями, задержка которых больше единицы, приходится ждать несколько тактов, ничего не планируя.

Как альтернатива предлагается модификация алгоритма “List Scheduling”, где вводится понятие приоритета планирования инструкции, который определяет более значимую инструкцию для планирования из любой пары инструкций (приоритет отдаем инструкции с минимальным временем позднего).
На графе зависимостей для каждой инструкции вычисляется время раннего и позднего запуска.
Время раннего – минимальное время, когда инструкция может быть запущена. Время позднего – максимальное время, когда операция может быть запущена без увеличения возможного времени запуска предшественников.

Путь в графе, на котором находятся инструкции, у которых время раннего запуска равно времени позднего запуска образуют критический путь графа программы (critical path).

Рассмотрим такой пример:

graph2.JPG
Инструкции\время раннего позднего
1 0 2
2 0 2
3 0 0
4 0 3
5 1 1
6 1 4
7 3 3
8 6 6

Инструкции 3, 5, 7, 8 образуют критический путь.

t = 0
Располагаем готовые инструкции по возрастанию времени позднего
ready_list = {3.mov, 1.mov, 2.mov, 4.mov}

sched 3.mov
sched 1.mov

ready_list = {2.mov, 4.mov}
wait_list = {5.add(1), 6.add(1), 7.fma(1)}

t = 1
wait_list = {5.add(0), 6.add(0), 7.fma(0)}
ready_list = {5.add, 2.mov, 4.mov}

sched 5.add
sched 2.add

ready_list = {4.mov}
wait_list = {6.add(1), 7.fma(2)}

t = 2
wait_list = {6.add(0), 7.fma(1)}
ready_list = {4.mov}

sched 4.mov

ready_list = {}
wait_list = {6.add(1), 7.fma(1), 8.fma(1)}

t = 3
wait_list = {6.add(0), 7.fma(0), 8.fma(0)}
ready_list = {7.fma, 6.add}

sched 7.fma
sched 6.add

ready_list = {}
wait_list = {8.fma(3)}
Теперь приходится ждать 2 такта:
//Только я видимо прослушал идеологию: этот факт говорит о нерациональности и 
//нового алгоритма? Вроде мы модифицировали его, чтоб он работал быстрее
t = 4
wait_list = {8.fma(2)}
t = 5
wait_list = {8.fma(1)}
t = 6
wait_list = {8.fma(0)}
ready_list = {8.fma}
sched 8.fma

wait_list = {}
ready_list = {}

Это была упрощенная модель, мы же имеем дело с Itanium’ом, поэтому инструкции нужно распараллеливать по 6 штук. На самом деле это не значит, что за такт мы можем исполнить любые 6 инструкций. Имеется ряд шаблонов широких команд (можно найти в документации), которых нам нужно придерживаться.

Стоит также разработать быстрый алгоритм подгона имеющихся инструкций под такие шаблоны, хотя можно и в лоб:
- ставим первую инструкцию на 1-е место, если шаблон с таким началом существует, берем следующую инструкцию и пытаемся поставить ее на 2-е место…;
- если не существует, перебираем остальные инструкции или в конце концов ставим nop (отсутствие инструкции).

Все вышесказанное относится к планированию в пределах линейного участка (Basic Block). Также существует глобальное планирование, учитывающее, что происходило с данными в предыдущих Basic Block’ах. Например может возникнуть ситуация, когда выполнение некоторой инструкции с большой задержкой началось в конце предыдущего Basic Block’а, тогда в начале данного Basic Block’а придется ждать несколько тактов. Но мы будем рассматривать только локальное планирование.

\\Bazhenov Alexej

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-Share Alike 2.5 License.