Программная конвейеризация: символическое разворачивание циклов

Мы уже видели, что один из методов компиляции - разворачивание циклов - полезен для увеличения степени параллелизма на уровне команд посредством создания более длинных последовательностей линейного кода. Имеются два других важных метода, которые разработаны для этих целей: программная конвейеризация и планирование трасс.

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

Рис. 50 – Программная конвейеризация

 

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

Loop: LD F0,0(R1)

ADDD F4,F0,F2

SD 0(R1),F4

SUBI R1,R1,#8

BNEZ R1, Loop

Игнорируя пролог и эпилог мы можем переписать цикл следующим образом:

Loop: SD 0(R1),F4; записывает в M[i]

ADDD F4,F0,F2; складывает с M[i-1]

LD F0,-16(R1); загружает M[i-2]

BNEZ R1, Loop

SUBI R1,R1,#8; вычитает в слоте задержки

Если не принимать во внимание пролог и эпилог, этот цикл может работать со скоростью 5 тактов на один проход. Поскольку команда загрузки осуществляет выборку на расстоянии двух элементов от счетчика цикла, цикл должен выполнять на две итерации меньше. При этом перед началом цикла из содержимого регистра R1 необходимо вычесть 16. Заметим, что повторное использование регистров (например, F4, F0 и R1) требует использования специальных аппаратных средств, чтобы обойти конфликты типа WAR и приостановки конвейера. В данном случае это не должно привести к каким-либо проблемам, поскольку никаких приостановок по причине зависимостей по данным произойти не должно.

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

Программную конвейеризацию можно рассматривать как символическое разворачивание цикла. Действительно, некоторые алгоритмы программной конвейеризации используют разворачивание цикла в качестве исходного материала для расчета (вычисления) выполнения программной конвейеризации. Главное преимущество программной конвейеризации по отношению к прямому разворачиванию циклов заключается в том, что первая генерирует в результате меньший по размеру программный код. Программная конвейеризация и разворачивание циклов в дополнение к тому, что они дают лучше спланированный внутренний цикл, сами по себе сокращают разные типы накладных расходов. Разворачивание циклов сокращает накладные расходы на организацию цикла, связанные с командами перехода и изменения значения счетчика циклов. Программная конвейеризация сокращает время, когда цикл не работает с полной скоростью, что происходит только однажды в начале и в конце цикла. Если мы разворачиваем цикл, который выполняет 100 итераций постоянное количество раз, скажем 4 раза, мы будем иметь накладные расходы 100/4=25 раз - каждый раз, когда будет инициироваться внутренний развернутый цикл. На рис. 6.16 это поведение показано графически. Поскольку эти методы направлены на два различных типа накладных расходов, наилучший результат может быть получен при использовании обоих методов.

Трассировочное планирование

Другим методом, используемым для выделения дополнительного параллелизма, является трассировочное планирование. Трассировочное планирование расширяет метод разворачивания циклов методикой для нахождения параллелизма в программах с условными переходами, не связанными с организацией циклов. Трассировочное планирование полезно для машин с очень большим количеством команд, выдаваемых для выполнения в одном такте, где одного разворачивания циклов может оказаться недостаточно для выявления необходимой степени параллелизма уровня команд для поддержания машины в занятом состоянии. Трассировочное планирование является комбинацией двух отдельных процессов. Первый процесс, который называется выбором трассы (trace selection), старается найти возможную последовательность базовых блоков, операции которых будут собираться вместе в меньшее количество команд; эта последовательность называется трассой. Разворачивание циклов используется для генерации длинных трасс, поскольку переходы циклов выполняются с высокой вероятностью. Дополнительно при использовании статического прогнозирования направления переходов другие условные переходы (не связанные с организацией цикла) также выбираются как выполняемые или как невыполняемые, так что результирующая трасса представляет собой линейную последовательность, полученную в результате конкатенации (объединения) многих базовых блоков. Когда трасса выбрана, другой процесс, называемый уплотнением трассы (trace compaction), старается сжать трассу в небольшое количество широких команд. Процесс уплотнения трасс пытается перенести операции как можно ближе к началу последовательности (трассы), упаковывая операции насколько это возможно в минимальное количество широких команд (или пакетов для выдачи).

Уплотнение трассы представляет собой процесс глобального планирования кода. Имеются два разных ограничения, которые возникают и должны обрабатываться любой схемой глобальной оптимизации кода: зависимости по данным, которые задают определенный порядок операций, и точки условного перехода, которые создают места, через которые команды не могут просто перемещаться. По существу код должен быть уплотненным в наиболее короткую последовательность, которая сохраняет зависимости по данным и по управлению. Зависимости по данным преодолеваются посредством разворачивания циклов и использования анализа зависимостей для определения того, относятся ли два обращения к одному и тому же адресу. Зависимости по управлению также сокращаются при разворачивании циклов. Главным преимуществом методики трассировочного планирования по сравнению с более простым методом планирования загрузки конвейера заключается в том, что она обеспечивает схему для снижения эффекта зависимостей по управлению посредством переноса команд через условные переходы, не связанные с циклами, используя прогнозируемое поведение переходов. На рис.51 показан фрагмент кода, который может рассматриваться как итерация развернутого цикла, и выбранная трасса.

Рис. 51 – Фрагмент кода с выбранной трассой

 

Когда трасса, как показано на рис.51, выбрана, она должна быть уплотнена так, чтобы заполнить машинный ресурс. Уплотнение трассы приводит к перемещению операторов присваиваний переменным B и C вверх по блоку, чтобы разместить их перед точкой решения о направлении перехода. Любая схема глобального планирования, включая трассировочное планирование, выполняет такое перемещение команд при наличии набора ограничений. В трассировочном планировании условные переходы рассматриваются как безусловные переходы во внутрь или во вне выбранной трассы, которая предполагалась как наиболее вероятный путь. Когда команды перемещаются через такие точки входа и выхода трассы, во входной и выходной точке могут потребоваться дополнительные команды. Главное предположение состоит в том, что выбранная трасса является наиболее вероятным событием, в противном случае стоимость дополнительной работы (дополнительных команд) может оказаться чрезмерной.

Что включает в себя процесс перемещения присваиваний B и C? Вычисление и присваивание B является зависимым по управлению от условного перехода, а вычисление C нет. Перемещение этих операторов может быть выполнено только, если ни один из них не меняет зависимость по управлению или по данным, или эффект от изменения зависимости не виден и тем самым не приводит к изменению выполнения программы. Рассмотрим типичную последовательность генерации кода для приведенного выше случая (рис. 52).

Рис. 52 – Генерация кода для различных методик

 

Ниже представлена такая последовательность в предположении, что адреса для A, B и C находятся в регистрах R1, R2 и R3 соответственно:

LW R4,0(R1);загрузка A[i]

ADDI R4,R4,...;добавление к A[i]

SW 0(R1),R4;запись в A[i]

...

BNEZ R4,elsepart;проверка A[i]

...;часть then

SW 0(R2),...;запись в B[i]

J join;прыжок через else

elsepart:...;часть else

X;код для X

...

join:...;после if

SW 0(R3),...;запись в C[i]

Сначала рассмотрим проблему перемещения операции присваивания B на место перед командой BNEZ. Поскольку B зависит по управлению от того перехода, перед которым мы ее хотим расположить, и не будет зависеть от него после перемещения, необходимо гарантировать, что выполнение оператора не может вызвать появление исключительной ситуации, поскольку такая исключительная ситуация не могла возникнуть в первоначальной программе, если бы была выбрана часть else условного оператора. Перемещение B не должно также воздействовать на поток данных. Чтобы более ясно определить требования, нам нужна концепция живучести переменной. Переменная Z живет в операторе, если имеется путь выполнения от этого оператора до использования переменной Z, на котором нового присваивания переменной Z не делается. На интуитивном уровне, переменная живет в операторе, если добавление операции присваивания этой переменной в операторе может изменить семантику программы.

Возвращаясь к нашему примеру, можно видеть, что имеются два возможных случая, когда перемещение B может изменить поток данных в этой программе:

1) Обращение к B происходит в коде X (часть else) прежде, чем В будет присвоено новое значение.

2) B "живет" в конце оператора if и ей не делается присваивания в X.

В обоих случаях перемещение операции присваивания переменной B приведет к тому, что некоторая команда i (либо в X, либо далее в программе) станет зависимой по данным от этой перемещенной команды, а не от более ранней операции присваивания B, которая выполняется перед циклом и от которой i первоначально зависела. Поскольку это приведет к изменению результата программы, операция присваивания B не может быть перемещена в случае, если справедливо любое из приведенных выше условий. Можно представить себе более изощренные схемы: например, в первом случае перед оператором if можно сделать теневую копию B и использовать только эту теневую копию в X. Такие схемы в общем случае не используются, поскольку, во-первых, их сложно реализовать, и, во-вторых, поскольку они будут замедлять программу, если выбранная трасса не оптимальна и завершение операций требует выполнения дополнительных команд.

Для перемещения операции присваивания C на место сразу за первым условным переходом требуется, чтобы она переместилась выше точки объединения трассы (входа трассы) с направлением else. Это делает команды для C зависимыми по управлению от условного перехода и означает, что они не будут выполняться, если выбран путь else, который не находится на трассе. Поэтому будут затронуты команды, которые были зависимыми по данным от присваивания C и которые выполняются после этого кодового фрагмента. Для обеспечения вычисления корректного значения для этих команд делается копия команд, которые вычисляют и присваивают значение C на переходе на трасе, а именно в конце X на пути else. Мы можем переместить C из ветви then перехода через условие перехода, если это не воздействует ни на какой поток данных в условии перехода. Если C перемещается на место перед проверкой условия if, копия C в части else перехода может быть ликвидирована.

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