А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 179
Текст из файла (страница 179)
а // В1, В2, КЗ = ьА, йВ, вР // В4 = о // К10 = и-1 ЬР В5, 0(В1++) РР Вб, 0(82++) в!Ш 87, В5, Вб пор АРР В8, В7, В4 пор ЯТ 0(КЗ++), В8 В1 810, Ь Рнс. 10. ! 7. Локально спланированный код примера 10. 12 В общем случае добиться повышения степени использования аппаратного обеспечения можно путем развертки нескольких итераций цикла. Однако это приводит к увеличению размера кода, что, в свою очередь, может привести к отрицательному влиянию на общую производительность, Таким образом, следует искать компромисс — количество итераций, развертка которых даст наибольшее повышение эффективности без слишком сильного увеличения кода.
Следующий пример иллюстрирует такой компромисс. Пример 10.13. В то время как обнаружить параллелизм в пределах одной итерации очень сложно, между итерациями его сколько угодно. Развертка цикла помещает несколько итераций цикла в один большой базовый блок, после чего для планирования параллельного выполнения операций можно использовать простой алгоритм планирования списка.
Если в нашем примере мы четырежды развернем цикл и применим алгоритм 10.7, то получим план, показанный на рис. 10.18 (для простоты мы пока что игнорируем детали распределения регистров). Цикл выполняется за 13 тактов, т.е. продолжительность выполнения одной итерации падает до 3,25 такта. Цикл, развернутый й раз, требует как минимум 28 + 5 тактов, достигая, таким образом, выполнения одной итерации за 2+ 5/й тактов. Следовательно, чем больше итераций будет развернуто, тем быстрее будет выполнен цикл. При й — оо 879 10.5. Программная конвейеризация Ы) ЬЯ ЬЭ МЯЬ Ь1) МЯЬ А)ПЭ АР!) Ь1) Ь1) Ь1) М!)Ь Ь0 МБ1 А!)1) А!)1) ЯТ ЯТ ЯТ ЯТ ВЬ !1) Рнс. 10.18. Развернутый код из примера 10.12 полностью развернутый цикл может выполнять в среднем одну итерацию за два такта.
Однако чем больше итераций будет развернуто, тем большего размера код будет получен; так что развернуть все итерации цикла, определенно, не получится. Развертка 4 итераций дает код, состоящий из 13 команд, или 163% от оптимального значения; развертка 8 итераций дает 21 команду, или 131% от оптимального значения. Можно пойти и в обратном направлении; например, чтобы получить 110% от оптимального значения, следует развернуть 25 итераций, получая код с 55 командами. и 10.5.2 Программная конвейеризация циклов Программная конвейеризация предоставляет удобный способ достичь оптимального использования ресурсов одновременно с компактным кодом. Проиллюстрируем лежащую в ее основе идею на нашем стандартном примере. Пример 10.14.
На рис. 10.19 показан пятикратно развернутый код из примера 10.12. (Как и ранее, вопрос распределения регистров остается за пределами нашего внимания.) В строке 1 показаны все операции, выполняемые на такте г; в столбце 7' показаны все команды итерации 7'. Заметим, что каждая итерация имеет один и тот же план выполнения относительно ее начала и что каждая итерация начинается через два такта после начала предыдущей. Легко видеть, что этот план удовлетворяет всем ограничениям, накладываемым ресурсами и зависимостями данных.
Мы видим, что на тактах 7 и 8 выполняются те же операции, что и на тактах 9 и 10. Во время тактов 7 и 8 выполняются операции из первых четырех итераций исходной программы; во время тактов 9 и 10 также выполняются операции из 880 Глава 1О. Параллелизм на уровне команд з=4 1=5 Такт 2=1 1 1Р 2 1Р 3 МШ 4 5 6 АРР 7 8 ЯТ 9 10 11 12 13 14 15 16 ЬР ЬР МРЬ РР ЫЭ МШ ГР МРЬ ЬР ЬР МРЬ АРР АРР ЯТ АРР ЯТ АРР Рис. 10.19. Пятикратно развернутый код из примера !0.12 четырех итераций, но на этот раз — итераций со второй по пятую. План можно рассматривать как выполнение многооперационных команд — при этом работа цикла представляет собой завершение самой старой итерации и начало новой до тех пор, пока не будут выполнены все итерации.
Такое динамическое поведение можно сжато закодировать при помощи кода, показанного на рис. 10.20, если считать, что цикл содержит как минимум четыре итерации. Каждая строка на рисунке соответствует одной машинной команде. Строки 7 и 8 образуют двухтактный цикл, который выполняется п — 3 раза, где п — количество итераций в исходном цикле. и Описанный выше метод называется программной конвейеризацией 1яойи'аге р1ре11п|п8), поскольку он представляет собой программный аналог метода, используемого для планирования аппаратных конвейеров.
План, выполняющий каждую итерацию в данном примере, можно рассматривать как восьмиэтапный конвейер. Новая итерация может начинаться в конвейере кахслые два такта. В начале в конвейере находится только одна итерация. Когда первая итерация переходит на третий этап выполнения, с первого этапа начинается выполнение второй итерации. На седьмом такте конвейер полностью заполнен первыми четырьмя итерациями. На этой стадии параллельно выполняются четыре соседние итерации.
Когда наиболее старая итерация выполнена и покидает конвейер, начинается выпол- 881 10.5. Программная конвейеризация ! 2 4 5 6 7 8 9 10 11 12 13 !4 ЬВ ЬВ М1!1 ЬВ ыз МШ АВВ 1: ЯТ АИ! ЬВ Ы) М17Ь 1 В Ь!э ВЬ (Ь) МШ АВ1З БТ ЯТ А1эВ Рис. 10.20. Программная конвейеризация кода из примера 10.12 нение новой итерации. Когда новых итераций нет, конвейер опустошается, и все находящиеся в нем итерации выполняются до конца. Последовательность команд, использующихся для заполнения конвейера (в нашем примере — команды с ! по 6), называется лралогаи, строки 7 и 8 представляют устойчивое состояние (з1еаг)у з1а1е), а последовательность команд, приводящих к опустошению конвейера (в нашем примере — команды с 9 по 14), называется элилогам.
В нашем примере мы знаем, что цикл не может работать быстрее, чем итерация за два такта, поскольку машина не в состоянии выполнять более одного чтения за такт, а в каждой итерации их два. Рассмотренный программно конвейеризованный цикл выполняется за 2п + б тактов, где и — количество итераций в исходном цикле. При п — ссскорость работы цикла стремится к одной итерации за два такта.
Таким образом, в отличие от развертки циклов, программная конвейеризация потенциально способна получить оптимальный план при весьма компактной последовательности кода. Заметим, что по отношению к отдельно взятой итерации этот план не является оптимальным.
Сравнивая его с локально оптимизированным планом, показанным на рис. 10.17, мы видим излишнюю задержку перед операцией АВР. Эта стратегическая задержка необходима для того, чтобы выполнение каждой новой итерации могло начинаться спустя два такта после начала предыдущей без каких-либо конфликтов ресурсов.
Если бы мы использовали локальный план, то во избежание конфликтов каждая новая итерация должна была бы начинаться через четыре такта после начала предыдущей и скорость работы программы упала бы вдвое. Этот пример иллюстрирует важный принцип конвейерного планирования: для оптимизации производительности следует очень аккуратно выбирать план. Локально 882 Глава 10. Параллелизм на уровне команд оптимизированный план, минимизирующий время выполнения одной итерации, может привести к неоптимальной производительности при конвейеризации. 10.5.3 Распределение регистров и генерация кода Рассмотрим теперь вопросы распределения регистров для программно конвейеризованного цикла из примера 10.!4. Н (1з >= !я 2 е1ве !з2 аког (1 = 1) [ з.
) аког (з. = 0[1) 5) 3 + 2 * й1оог((1я-3)/2)! 0; О! 1 < !Ч2! 1++) = А[з.]* В[1.1 + с; 1я2; 1 < 1х! 1++) = А[з.)* В[э.) + с; Рис. 10.2!. Развертка цикла из примера 10.12 на уровне исходного текста Пример 10.15. В примере 10.14 результат операции умножения в первой итерации получается на третьем такте, а используется — на шестом. Между этими тактами, на пятом такте, генерируется новый результат операции умножения во второй итерации; это значение используется на восьмом такте. Результаты работы этих двух итераций должны храниться в разных регистрах для того, чтобы предотвратить их влияние друг на друга.
Поскольку такое перекрытие временных интервалов существования результата осуществляется только для соседних итераций, достаточно использовать для хранения указанных значений два разных регистра: один — для четных итераций, другой — для нечетных. Поскольку код нечетных итераций отличается от кода четных, размер устойчивого состояния цикла удваивается. Такой код может использоваться для выполнения любого цикла с нечетным количеством итераций, не меньшим 5.
Для работы с циклами, состоящими менее чем из пяти итераций, и циклами с четным количеством итераций мы генерируем код, на уровне исходного текста эквивалентный показанному на рис. 10.2!. Первый цикл конвейернзован, как видно из представленного на рис. 10.22 эквивалента программы на уровне машинных команд.
Второй цикл на рис. 10.21 не требует оптимизации, так как в нем выполняется не более четырех итераций. и ЯЯЗ 10.5. Программная конвейеризация МРЬ К7, К5, Кб М01 К9, К5, Кб АРР К8,К7,К4 МРЬ К7,К5,К6 АРР К8, К9, К4 МРЬ К9, К5, Кб АРР КЯ,К7,К4 МРЬ К7, К5, Кб АРР КВ,К9,К4 ЯТ 0(КЗ++),К8 ЯТ 0(КЗ++),К8 ВЬ К10,Ь ЯТ 0(КЗ++),К8 АВР К8,К7,К4 ЯТ 0(КЗ++),К8 ЯТ 0(КЗ++),К8 Рис. 10.22. Код из примера 10.12 после программной конвейеризации и распределения регистров 10.5.4 Циклы с зависимыми итерациями Программная конвейеризация применима и к циклам, у итераций которых имеются зависимости данных друг от друга.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
