А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 181
Текст из файла (страница 181)
10.25 приводит к задержке в четыре такта между операциями загрузки из последовательных итераций, т.е. исходный цикл не может выполняться быстрее, чем одна итерация за четыре такта. Интервал между запусками итераций конвейеризованного цикла не может быть меньше л еес'1е шах с — цикл во 2, др тактов. В результате интервал между запусками итераций каждого программно конвейеризованного цикла ограничен использованием ресурсов на каждой итерации. А именно, этот интервал должен быть не меньше, чем отношение количества необходимых единиц каждого ресурса и количества доступных единиц ресурса в целевой машине. Кроме того, если имеются циклы зависимостей данных, то интервал между запусками оказывается еще более ограниченным суммой задержек в цикле, деленной на сумму разностей итераций.
Наибольшая из этих величин определяет нижнюю границу между запусками итераций. 10.5.6 Алгоритм программной конвейеризации Цель программной конвейеризации состоит в том, чтобы найти план с наименьшим возможным интервалом между запусками итераций. Это ХР-полная задача, которая может быть переформулирована как задача целочисленного линейного программирования. Мы должны показать, что если мы знаем, чему равен минимальный интервал, то алгоритм планирования может избежать конфликта ресурсов с использованием таблиц модульного резервирования ресурсов при раз- 889 10.5.
Программная конвейеризация мещении каждой операции. Но мы не знаем, чему равен минимальный интервал, пока не разработаем план. Как же разорвать этот круг? Мы знаем, что интервал между запусками должен быть больше, чем граница, вычисленная из требований цикла к ресурсам и циклов зависимостей данных, как рассматривалось выше. Если мы можем найти план, отвечающий этой границе, то это — оптимальный план.
Если же такой план не найден, можно повторить попытку поиска с ббльшим значением интервала между запусками, и так до тех пор, пока план не будет найден. Заметим, что если используется не исчерпывающий поиск, а лишь эвристика, то оптимальный план может так и не быть найден. Можем ли мы найти план, близкий к нижней границе, зависит от свойств графа зависимости данных и архитектуры целевой машины.
Можно легко найти оптимальный план в случае ацикличного графа зависимости данных, а каждая машинная команда требует для выполнения только одной единицы одного ресурса. Легко также найти близкий к нижней границе план, когда в наличии больше аппаратных ресурсов, чем может быть использовано графом зависимости данных с циклами. В таких случаях можно рекомендовать начать с нижней границы в качестве начального значения интервала между запусками итераций, а затем увеличивать его на один такт для каждой попытки построения плана. Другая возможность заключается в поиске интервала между запусками путем бинарного поиска. В качестве верхней границы можно использовать длину плана для одной итерации, полученную путем планирования списка. 10.5.7 Планирование ациклических графов зависимости данных Для простоты мы пока что считаем, что программно конвейеризуемый цикл содержит только один базовый блок.
Это условие будет ослаблено в разделе 10.5.11. Алгоритм 10.19. Программная конвейеризация ациклического графа зависимости данных Вход: вектор ресурсов целевой машины Л = [г,,гз,...), где г, — количество доступных единиц ресурса г-го вида и граф зависимости данных С = (Ю, Е).
Каждая операция п е Ю помечается ее таблицей резервирования ресурсов ВТ„; каждое ребро е = п~ — пз из Е имеет метку (б„д,), указывающую, что операция пз должна выполняться не ранее чем через й, тактов после операции и~ из б,-й предшествующей итерации. Выход: программно конвейеризованный план Я и интервал между запусками итераций Т. Метод: выполнить программу, приведенную на рис. 10.26. и Алгоритм 10.19 программно конвейеризует ациклические графы зависимостей данных. Сначала алгоритм находит границу интервала между запусками итера- 890 Глава !О. Параллелизм иа уровне команд еа(л () ( Р~„, нт (~Д)~ То = шах [ 1 !ог (Т = То, То + 1,..., пока не будут спланированы все узлы из Х) ( ВТ = пустая таблица резервирования ресурсов с Т строками; !ог (каждый узел и б Х в приоритетном топологическом порядке) ( ао = шахе=р и из е Ф (р) + ~(е) !ог (а = ао,во+ 1, ..,,во +Т вЂ” 1) И' (МойеБслейи1ей (ЯТ, Т, п, а) ) Ьгеаи; !!' (и не может быть спланировано в ГтТ) Ьгеви; Ног1еБсйейи(ег( (ГтТ, Т, п, а) ( ВТ' = ВТ; !ог (каждая строка ! из ЙТ„) ГтТ'[(а+ !) шос( Т) = ГтТ'[(а+ !) шоб Т~ + ГтТ [г]; !!' (для всех г, !1Т' (!) < В) ( ГтТ = ГтТ', Я(п) = а; геепгп ггце; е(ае гегцгп (а(яе; Рис.
10.26. Алгоритм программной конвейеризации ациклического графа ций То на основе требований к ресурсам операций в графе. Затем он пытается найти программно конвейеризованный план, начиная с То в качестве целевого интервала между запусками итераций. Алгоритм повторяется с ббльшим значением интервала, если для текущего значсния построить план не удается. При каждой попытке алгоритм применяет подход из алгоритма планирования списка. Этот подход использует модульное резервирование ресурсов для отслеживания запросов ресурсов в устойчивом состоянии.
Операции планируются в топологическом порядке, так что зависимости данных всегда можно удовлетворить соответствующими задержками операций. Для планирования операции мы сначала находим нижнюю границу ао, соответствующую ограничениям зависимостей данных. Затем вызывается функция МоИе5слеои1еа~, проверяющая возможные конфликты ресурсов в устойчивом состоянии. Если конфликт существует, алгоритм пытается спланировать операцию на следующий такт. Если выясняется, что опе- 891 10.5.
Программная конвейеризация рация вызывает конфликт для Т последовательных тактов, то в силу модульной природы обнаружения конфликтов, связанных с ресурсами, последующие попытки будут гарантированно неуспешными, так что следует переходить к другому значению интервала между запусками итераций. Эвристика, состоящая в планировании операций на как можно более ранние моменты времени, стремится минимизировать длину плана итерации. Однако планирование операции на как можно более ранний срок может привести к росту времени жизни некоторых переменных. Например, загрузка данных при этом может оказаться выполненной задолго до того, как потребуются загружаемые данные. Одна из простейших эвристик состоит в планировании графа зависимости данных в обратном направлении, поскольку обычно загрузок существенно больше, чем сохранений.
10.5.8 Планирование графов с циклическими зависимостями Наличие циклов зависимостей существенно усложняет программную конвейеризацию. При планировании операций в ациклическом графе в топологическом порядке зависимости данных планируемых операций могут указать только нижнюю границу размещения каждой операции. В результате всегда можно удовлетворить ограничения, связанные с зависимостями данных, путем задержки операций. Но концепция "топологического порядка" не применима к циклическим графам.
В действительности для данной пары операций в цикле размещение одной из них указывает как нижнюю, так и верхнюю границы для размещения второй. Пусть п| и пз — две операции из цикла зависимостей, Я вЂ” план, получаемый путем программной конвейеризации, а Т вЂ” интервал между запусками итераций для данного плана. Ребро зависимости п1 — пз с меткой (бы И1) накладывает на 5(п1) и о (пз) следующие ограничения: (б1 х Т) + 5 (пв) — Я (п1) ) Н1 Аналогично ребро зависимости па — п1 с меткой (бз, дз) накладывает ограничение (бз х Т) + Я (п1) — Я (пз) ~ ~оя Таким образом, 5(п1) + А — (б| х Т) < о (пг) < о (п1) — дг+ (бз х Т) Сильно связанным компонентом (зГгоп8)у соппес1ед сошропепГ) графа называется множество узлов, в котором каждый узел компонента может быть достигнут 892 Глава !О.
Параллелизм на уровне команд из любого другого узла компонента. Планирование одного узла в сильно связанном компоненте ограничивает время каждого другого узла компонента как снизу, так и сверху. Транзитивно, если существует путь р, ведущий из п1 в пз, то Я(пз) — Я(пз) 3 ~~~ (г1, — (Ь, х Т)) (10.1) еер Заметим следующее. ° Сумма б вдоль цикла должна быть положительной.
Если бы она была равна 0 или отрицательна, то это означало бы, что либо операция в цикле должна предшествовать самой себе, либо все операции цикла должны выполняться одновременно, в один и тот же такт. ° План для операций внутри итерации одинаков для всех итераций; это требование, по сути, и означает "программную конвейеризацию". В результате сумма задержек (вторых компонентов меток ребер в графе зависимости данных) в цикле представляет собой нижнюю границу интервала между запусками итераций Т. Комбинируя эти два наблюдения, можно увидеть, что для любого допустимого интервала между запусками итераций Т значение правой части уравнения (10.1) должно быть отрицательно или равно О, если р представляет собой цикл.
В результате наиболее строгие ограничения на размещение узлов получаются из просягых путей, т.е. из путей, не содержащих циклы. Таким образом, для каждого допустимого Т вычисление транзитивного влияния зависимостей данных на каждую пару узлов эквивалентно поиску длины наибольшего простого пути от первого узла ко кгорому. Более того, поскольку циклы не могут увеличивать длину пути, для поиска наидлнннейших путей без требования "простоты пути*' можно воспользоваться простым алгоритмом динамического программирования и быть уверенным, что полученные в результате длины будут также длинами наидлиннейших простых путей (см.
упражнение 10.5.7). Пример 10.20. На рнс. 10.27 показан граф зависимости данных с четырьмя узлами: а, Ь, с и д. Возле каждого узла изображена его таблица резервирования ресурсов, а возле каждого ребра — разность итераций и задержка. Будем считать, что в этом примере целевая машина имеет по одной единице каждого ресурса. Поскольку имеется три использования первого ресурса и два — второго, интервал между запусками итераций не может быть меньше трех тактов. В данном графе имеется два сильно связанных компонента: первый из них тривиальный, состоящий из единственного узла а, а второй — из узлов Ь, с и г1. Самый длинный цикл, Ь вЂ” с — д — 6, имеет общую задержку, равную трем тактам в пределах одной итерации. Таким образом, нижняя граница интервала между запусками итераций, основанная на ограничениях цикла зависимости данных, также равна трем тактам.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
