А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 180
Текст из файла (страница 180)
Такие циклы известны как перекрестные (г(о-асгоаз 1оорз). Пример 10.16. Код бог (1 = 0; 1 < пг 1++) ( вцв = аив + А(1); В(1) = А(з.) * )зг содержит зависимости данных между соседними итерациями, поскольку при выполнении итерации для получения нового значения ваяв к старому значению впв прибавляется значение А (г]. Если машина обладает достаточной степенью параллелизма, то такое суммирование можно выполнить за время О (1ояп), но мы просто предположим, что все последовательные зависимости должны быть удовлетворены и что суммирование должно быть выполнено в исходном порядке. Поскольку в нашей модели машины выполнение команды АРР требует двух тактов, цикл не может выполняться быстрее, чем одна итерация за два такта.
Ускорить выполнение не поможет никакое количество добавочных сумматоров или !. 10 2. 10 3. 1Р 4. ЬР 5. 10 6. ЬР 7. 1. "10 Я. ЬР 9. ЬР 1О. 10 11. 12. 13. 14. 15. 16. К5,0(К1++) К6,0(К2++) К5,0(К1++) К6,0(К2++) К5,0(К1++) К6,0(К2++) К5,0(К1++) К6,0(К2++) К5,0(К1++) К6,0(К2++) 884 Глава !О. Параллелизм на уровне команд умножителей. Производительность перекрестного цикла ограничена цепочкой зависимостей между итерациями. На рис.
10.23, а показан локально оптимизированный план для каждой итерации, а на рис. 10.23, б — программно конвейеризованный код. Такой программно конвейеризованный цикл каждые два такта начинает выполнение новой итерации и, таким образом, работает с оптимальной скоростью.
с // В1 = йА; В2 = йВ // ВЗ = вшп // В4 = Ь // К10 = и-1 1.' ВЭ К5, 0(В1++) М01 Вб, В5, К4 АОО ВЗ, КЗ, В4 ЯТ Вб, 0(В2++) В1 К10, В а) Локально оптимизированный план 6) Программно Рис. ! 0.23. Программная конвейеризация перекрестного цикла 10.5.5 Цели и ограничения программной конвейеризации Основная цель программной конвейеризации — максимизация производительности долго выполняющихся циклов.
Вторичная цель заключается в генерации кода относительно малого размера. Другими словами, программно конвейеризованный цикл должен иметь малое устойчивое состояние конвейера. Достичь // В1 = йА; К2 // ВЗ = випг // В4 = Ь // В10 = п-2 ВО В5, 0(В1++) М01 Кб, К5, В4 В: А1Ю ВЗ, ВЗ, В4 ЯТ Кб, 0(Р2++) ВО В5, 0(В1++) МУВ Вб, В5, К4 ВВ В10, В АОО КЗ, ВЗ, К4 ЯТ Вб, 0(В2++) конвейеризованная версия 885 !0.5.
Программная конвейеризация этого малого устойчивого состояния можно, если потребовать, чтобы относительные планы каждой итерации были одинаковы и чтобы итерации начинались через один и тот же постоянный интервал времени. Поскольку производительность цикла определяется как величина, обратная интервалу между запусками итераций, цель программной конвейеризации заключается в минимизации этого интервала.
План программной конвейеризации для графа зависимости данных С = (Ю, Е) может быть определен 1. интервалом между запусками итераций Т; 2. относительным планом Я, который для каждой операции указывает время ее выполнения относительно начала итерации, которой принадлежит эта команда. Таким образом, операция и в 1-й итерации, считая от нуля, выполняется в момент 1 х Т + 3 (и), Подобно всем прочим задачам планирования, программная конвейеризация имеет два вида ограничений, связанных с ресурсами и зависимостями данных.
Ниже мы рассмотрим каждый из этих типов ограничений. Модульное резервирование ресурсов Представим машинныс ресурсы в виде Л' = ( !. гз...,], где г, — количество единиц 1-го вида ресурса. Если итерация цикла требует п,; единиц ресурса г, то средний интервал между запусками итераций конвейеризованного цикла составляет как минимум шах, (и,,/г,) тактов. Программная конвейеризация требует, чтобы интервалы запуска между любыми соседними итерациями представляли собой одно и то же значение. Таким образом, интервал запуска должен состоять из как минимум шах, ! ки/г,~! тактов.
Если шах, (кч/г;) меньше 1, то имеет смысл развернуть небольшое количество итераций. Пример 10.17. Вернемся к нашему программно конвейеризованному циклу, показанному на рис. 10.20. Вспомним, что целевая машина может выполнить за один такт одну загрузку, одну арифметическую операцию, одно сохранение и одну операцию цикла. Поскольку цикл содержит две загрузки, две арифметические операции и одну операцию сохранения, минимальный интервал между запусками итераций, вычисленный на основании ограничений, связанных с ресурсами, равен двум тактам.
На рис. 10.24 показаны требования четырех последовательных итераций к ресурсам в разные моменты времени. Чем больше итераций запущено, тем выше требования к ресурсам; максимальные требования достигаются в устойчивом состоянии. Пусть ЛТ вЂ” таблица резервирования ресурсов, представляющая запросы одной итерации, а НТз представляет запросы в устойчивом состоянии. ЯТя объединяет запросы четырех последовательных итераций, начавшихся в пределах 886 Глава 10. Параллелизм иа уровне команд Итераиия ! Ьс АЛУ БТ Итерация 2 ЬО АЛУ БТ Итераиия 3 Ьо АЛУ Бт Устойчивое Итераиия 4 состояние Ьц АЛУБТ ьр Адузт Рис. 10.24.
Требования четырех последовательных итераций кода из примера 10.13 к ресурсам Т тактов. Запросы в строке О таблицы ВТБ соответствуют сумме ресурсов, запрошенных в ВТ [0], ВТ[2], ВТ[4] и ВТ [6]. Аналогично запросы в строке ! соответствуют сумме ресурсов, запрошенных в ВТ [1], ВТ [3], ВТ [5] и ЛТ [7], т.е. ресурсы, запрошенные в т-й строке в устойчивом состоянии, равны ВТБ [т] = ~~> ВТ [1].
(ар втос$21=х ! Будем говорить о таблице резервирования ресурсов, представляющей устойчивое состояние, как о таблице модульного резервирования ресурсов (пнк1ц!аг гезоцгсегеаегуаг!оп гаЫе) конвейеризованного цикла. Чтобы проверить наличие в плане программной конвейеризации конфликтов, связанных с ресурсами, можно просто проверить запросы в таблице модульного резервирования ресурсов. Само собой разумеется, если запросы в устойчивом состоянии могут быть удовлетворены, то тем более они могут быть удовлетворены в прологе и эпилоге — частях кода до и после устойчивого состояния цикла.
и В общем случае для данного интервала между запусками Т и таблицы резервирования ресурсов итерацией ЯТ конвейеризованный план на машине с вектором ресурсов В не имеет конфликтов, связанных с ресурсами, тогда и только тогда, когда ВТБ [т] < В для всех т = О, 1,..., Т вЂ” 1. 887 10.5. Программная конвейеризация Ограничения, связанные с зависимостями через данные Зависимости через данные при программной конвейеризации отличаются от зависимостей, с которыми мы сталкивались до настоящего времени, потому что они могут образовывать циклы. Операция может зависеть от результата той же операции нз предыдущей итерации.
Теперь помечать ребра зависимостей только лишь значениями задержек недостаточно; требуется также различать различные экземпляры одной и той же операции в разных итерациях. Мы будем помечать ребро зависимости п~ — пз меткой (6, д), если операция пз в итерации ( должна быть задержана как минимум на д тактов после выполнения операции п~ в итерации ( — б. Пусть Я вЂ” план, полученный путем программной конвейеризации-- представляет собой функцию, областью определения которой является множество узлов графа зависимости данных, а областью значений — целые числа, и пусть Т вЂ” интервал между запусками итераций. Тогда (с х Т) + Я (пз) — Я (п1) 3~ д. Разность итераций б должна быть неотрицательна.
Более того, для данного цикла из ребер зависимости данных как минимум одно ребро имеет положительную разность итераций. Пример 10Л8. Рассмотрим следующий цикл в предположении, что значения р и д нам неизвестны: аког(1 = 0; 1 < и; 1++) *(р++) = *(с1++) + с' Мы должны считать, что любая пара * (р++ ) и * (<1++ ) может обращаться к одной и той же ячейке памяти. Таким образом, все чтения и записи должны выполняться в том же порядке, что и в исходной программе. Считая, что целевая машина имеет те же характеристики, что и описанная в примере 10.12, мы получим для этого кода ребра зависимостей данных, показанные на рис. 10.25. Заметим, однако, что мы игнорируем команды управления циклом, которые состоят в вычислении и тестировании значения ( либо в проверке, основанной на значениях В1 или К2.о Разность итераций между связанными операциями может быть больше единицы, что видно нз следующего примера: аког(1 = 2; 1 < и; 1++) А(1) = В(1) + А(з.-2); Здесь значение, записываемое на итерации г, используется двумя итерациями позже.
Ребро зависимости между сохранением А [г) и загрузкой А (( — 2), таким образом, имеет разность в две итерации. 888 Глава 10. Параллелизм на уровне команд ~! вт, в2 = ч ггвз = с <т,г> Рис. 10.25. Граф зависимости данных к примеру!0.18 Наличие циклов зависимостей данных накладывает еще одно ограничение на скорость выполнения. Например, цикл зависимости данных на рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
