Лекция 09. Планирование кода (Лекции (2015))

9. Планирование кода19.1 Постановка задачи9.1.1 Модель целевого процессораКаждое ядро современного процессора обеспечиваетпараллельное выполнение инструкций программы за счетдублирования функциональных устройств (ФУ);использования конвейерных ФУ;возможности одновременной выдачи нескольких командРассмотрим модельный процессор (ядро), который за один тактможет выполнить четыре операции:одну загрузку,одно сохранение,одну арифметическую операциюодну операцию переходаДля организации циклов имеется специальная операцияпереходаBL R, Lкотораяуменьшает на единицу значение регистра R иесли это значение  0, передает управление на метку 2L.9.1 Постановка задачи9.1.1 Модель целевого процессораОперации с памятью могут выполняться в автоинкрементномрежиме: если в команде после ссылки на регистр помещенысимволы ++, то значение регистра автоматически увеличиваетсятаким образом, чтобы на следующей операции с памятьюрегистр указывал на следующий адрес в памяти.Арифметические операции выполняются в конвейерномрежиме.

Они могут быть инициированы на любом такте, но ихрезультаты становятся доступными два такта спустя.Операции с памятью выполняются три такта.Задержка всех прочих операций – один такт.39.1 Постановка задачи9.1.2 ПримерРассмотрим базовый блок, в котором вычисляется выражениеt = a * 2 * b * c * d14581013151821LD R1 &aADD R1 R1 R1LDMULLDMULLDMULSTR2R1R2R1R2R1&t&bR1 R2&cR1 R2&dR1 R2R1Без планирования кодаРезультат на 24 такте49.1 Постановка задачи9.1.2 ПримерРассмотрим базовый блок, в котором вычисляется выражениеt = a * 2 * b * c * d14581013151821LD R1 &aADD R1 R1 R1LDMULLDMULLDMULSTR2R1R2R1R2R1&t&bR1 R2&cR1 R2&dR1 R2R1Без планирования кодаРезультат на 24 такте12LDLDR1 &aR2 &b34567911LDADDMULLDMULMULSTR3R1R1R2R1R1&t&cR1R1&dR1R1R1R1R2R3R2После планирования кодаРезультат на 14 такте59.1 Постановка задачи9.1.3 Цель планирования кодаЦель планирования кода – выбрать такую последовательностькоманд, которая, не меняя семантики программы, обеспечитоптимальное использование особенностей архитектуры целевогопроцессора и, прежде всего, правильное использованиевозможностей параллельного выполнения команд,реализованных в его аппаратуреОтвет на вопрос:насколько быстро может выполняться программа напроцессоре с параллелизмом на уровне команд?зависит от следующих факторов:Доступный параллелизм процессора.Потенциальный параллелизм программы.Возможность выделить параллелизм в исходнойпоследовательной программе.Наша способность спланировать наилучшеепараллельное выполнение при заданных ограничениях6планирования.9.1 Постановка задачи9.1.4 Сохранение семантики программыТребование сохранения семантики программы проще всеговыразить в форме ограничений, которым должна удовлетворятьцелевая программа.

Эти ограничения должны гарантировать, чтооптимизированная программа будет давать такие же результаты,что и исходная.На планирование кода накладывается следующие три типаограничений:Ограничения управления. Все операции, выполняемыев исходной программе, должны выполняться и воптимизированной программе.Ограничения данных.

Операции в оптимизированнойпрограмме должны выдать те же результаты, что исоответствующие операции в исходной программеОграничения ресурсов. Планирование кода не должнотребовать чрезмерного количества ресурсов машины.79.2 Анализ зависимостей по данным9.2.1 Зависимости по даннымОпределение.

Две команды называются зависимыми поданным, если изменение порядка их выполнения может привестик изменению результата вычислений, выполняемых программой.Виды зависимостей по данным:Истинная зависимость: чтение после записи.Если команда C1 записывает значение в некоторую ячейкупамяти (или на регистр), а команда C2 считывает этозначение, то команды C1 и C2 зависимы.Антизависимость: запись после чтения.Если команда C1 считывает значение из некоторой ячейкипамяти, а команда C2 записывает в эту ячейку новоезначение, то команды C1 и C2 зависимы.Зависимость по выходу: запись после записи.Если команды C1 и C2 записывают значения в одну и туже ячейку памяти, то команды C1 и C2 зависимы.89.2 Анализ зависимостей по данным9.2.1 Зависимости по даннымОпределение.

Две команды называются зависимыми поданным, если изменение порядка их выполнения может привестик изменению результата вычислений, выполняемых программой.Виды зависимостей по данным:Истинная зависимость: чтение после записи.Если команда C1 записывает значение в некоторую ячейкупамяти (илина регистр),а командаC2 считываетэтоНеустранимойявляетсятолькоистиннаязависимость.значение, то команды C1 и C2 зависимы.Два других вида зависимостей (ихназывают зависимостями,Антизависимость: записьчтения.связаннымис хранением) могутбытьпослеустранены:нужноЕсли вкомандаC1 Cсчитываетзначениеиз памяти.некоторой ячейкииспользоватькомандахиCразныеячейки12памяти, а команда C2 записывает в эту ячейку новоезначение, то команды C1 и C2 зависимы.Зависимость по выходу: запись после записи.Если команды C1 и C2 записывают значения в одну и туже ячейку памяти, то команды C1 и C2 зависимы.99.2 Анализ зависимостей по данным9.2.2 Требование консервативности анализаКонсервативность.

Компилятор обязан считать, что двекоманды могут обращаться к одним и тем же ячейкам, еслион не может доказать обратное.Пример: Рассмотрим код1. a  12. *p  23. b  aСразу можно обнаружить истинную зависимость междукомандами 1 и 3.Больше зависимостей как будто нет, но это только в том случае,если компилятор может доказать, что указатель p не можетуказывать на a.В противном случае, компилятор обязан считать, что указатель pможет указывать на a, и тогда возникают еще две зависимости:истинная зависимость между командами 2 и 310зависимость по записи между командами 1 и 2.9.2 Анализ зависимостей по данным9.2.3 Граф зависимостей (по данным)В базовом блоке B граф зависимостей D – ориентированныйграф, вершинами которого являются команды блока , а дугисоединяют вершины n1 и n2, если n2 использует результат n1.На рисунке изображен граф зависимостей для примера 9.1.2I1LDR1 &aI2I3I4I5I6I7I8I9ADDLDMULLDMULLDMULSTR1R2R1R2R1R2R1&tR1&bR1&cR1&dR1R1I1R1I2R2R2R2I3I4I5I6I7I8I9119.2 Анализ зависимостей по данным9.2.3 Граф зависимостей (по данным)Учитываются только истинныезависимости.Вершина графа D, у которой нетпоследователей, называется корнемграфа D.В рассматриваемом примере граф D– дерево.

В общем случае граф D– лес, и у него несколько корней.Расписание S сопоставляет каждойоперации o номер такта i = S(o),в который она может начатьвыполняться.i-я команда содержит все операции{o | S(o) = i}I1I2I3I4I5I6I7I8I9129.3 Локальное планирование9.3.1 Расписание (порядок выдачи) командРасписание S(o) должно удовлетворять следующимограничениям:1.Для любой операции o S(o)  1, т.е. операции не могутбыть выданы до начала выполнения программы. Крометого, расписание должно содержать по крайней мере однуоперацию o, у которой S(o) = 1.2.3.Если o1 и o2 – концы дуги графа зависимостей, то дляобеспечения корректности необходимо, чтобыS(o1) + delay(o1)  S(o2), т.е.

операция не может бытьвыдана до того, как будут определены ее операнды.Каждая команда может содержать не больше однотипныхопераций, чем это допускается системой команд целевоймашины (гарантия выполнимости).139.3 Локальное планирование9.3.3 Расписание (порядок выдачи) командПо определению продолжительность расписания S(o)фрагмента программы P – это номер такта, на которомзавершится последняя операция. Продолжительность L(S)расписания S можно вычислить по формулеLS   maxS o   delay o oPОптимальным по времени расписанием для фрагментапрограммы P называется расписание Sopt(P), котороеудовлетворяет условию: для любого расписания S (P)  Sopt(P)L(S (P))  L(Sopt(P))149.3 Локальное планирование9.3.2 Простой алгоритм планированияВершина графа D, у которой нетI1(13)последователей, называется корнемI2(10) I3(12)графа D.В рассматриваемом примере граф DI4(9) I5(10)– дерево.

В общем случае граф D– лес, и у него несколько корней.I (8)I6(7) 7Расписание S сопоставляет каждойI8(5)операции o номер такта i = S(o),в который она может начатьI9(3)выполняться.i-я команда содержит все операцииЧисла в скобках равны{o | S(o) = i}продолжительностиПуть I1I2I4I6I8I9 – самый длинный вычислений от(критический); он определяетполное время выполнениярассматриваемого фрагментасоответствующей вершиныдо окончания вычисленийони помогают составить15расписание9.3 Локальное планирование9.3.2 Простой алгоритм планированияРасписание для фрагмента.

Напервое место в нем претендуютвершины I1, I3, I5, I7, так как у нихнет предшественников и их операндыготовы; но I1 находится на критическомпути, так что именно эту операциюнужно запланировать первой.Продолжая рассуждать подобнымобразом, получим расписаниеI1I3I5I2I4I7I6I8I9.У полученного расписаниясущественный недостаток – при егосоставлении не учитывалисьзависимости по данным: I3 и I5определяют R2, а I4 используетзначение R2, установленное I3.

Так чтоI5 нельзя помещать между I3 и I4.I1(13)I2(10) I3(12)I4(9)I5(10)I6(7)I7(8)I8(5)I9(3)I1 LDR1&aI3 LDR2&bI5 LDR2&cI2 ADDR1R1R1I4 MULR1R1R2I7 LDR2&dI6 MULR1R1R2I8 MULR1R1R2I9 ST&tR1169.3 Локальное планирование9.3.2 Простой алгоритм планированияНо между I3 и I5 – антизависимость, ивсе можно решить, «переименовав»регистр R2 в I5, т.е. заменитьLD R2 &c на LD R3 &c.Если ввести обозначениеантизависимости между I3 и I5 какI5I3, то в рассматриваемом примереесть еще три антизависимости: I5I4,I7I5, и I7I6.

Их тоже можноразрешить, использовав дополнительныерегистры, но тут возникают сложности всвязи с нехваткой регистров.I1(13)I2(10) I3(12)I4(9)I5(10)I6(7)I7(8)I8(5)I9(3)I1 LDR1&aI3 LDR2&bI5 LDR2&cI2 ADDR1R1R1I4 MULR1R1R2I7 LDR2&dI6 MULR1R1R2I8 MULR1R1R2I9 ST&tR1179.3 Локальное планирование9.3.3 Зависимости по данным и распределение регистровПример. Рассмотрим код, вычисляющий выражение(а + b)+с +(d + е)(скобки в выражении расставлены в соответствии с деревом,показанном на рисунке)189.3 Локальное планирование9.3.3 Зависимости по данным и распределение регистров1.2.3.4.5.6.7.8.9.LDLDADDLDADDLDLDADDADDRl,&aR2,&bRl,Rl,R2R2,&сRl,Rl,R2R2,&dR3,&eR2,R2,R3Rl,Rl,R2//Rl//R2//Rl//R2//Rl//R2//R3//R2//Rl=========abRl+R2сRl+R2deR2+R3Rl+R2Экономное распределение регистров приведет кпоследовательному коду, представленному вверху справа.Этот код использует всего три регистра, но параллельно в немможно выполнить только загрузки регистров в строках 1 и 2 изагрузки регистров в строках 6 и 7.Таким образом, для вычисления выражения с максимальнымиспользованием параллельности потребуется 7 шагов.199.3 Локальное планирование9.3.3 Зависимости по данным и распределение регистров1.2.3.4.5.6.7.8.9.LDLDADDLDADDLDLDADDADDRl,&aR2,&bRl,Rl,R2R2,&сRl,Rl,R2R2,&dR3,&eR2,R2,R3Rl,Rl,R2//Rl//R2//Rl//R2//Rl//R2//R3//R2//Rl1.2.3.4.5.6.7.8.9.LDLDLDLDLDADDADDADDADD=========abRl+R2сRl+R2deR2+R3Rl+R2Rl,&a |R2,&b |R3,&c |R4,&d |R5,&e |R6,R1,R2R7,R4,R5R8,R6,R3R8,R8,R7Если использоватьразличные регистры длякаждой промежуточнойсуммы, то выражениеможно вычислить за 4 шага,что равно высоте деревавыражения.Но при этом потребуетсяне 3, а 8 регистров.шаг 1|||||||||||шаг 2шаг 3шаг 4209.3 Локальное планирование9.3.4 Алгоритм планирования с помощью списковАлгоритм включает следующие четыре шага1.Переименование значений, чтобы избежатьантизависимостей.Значения переименовываются таким образом, чтобыкаждое значение имело уникальное имя.