А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 182
Текст из файла (страница 182)
894 Глава 1О. Параллелизм на уровне команд жений из таблицы на рис. 10.28, а для каждого из ребер вдоль рассматриваемого пути. Далее, на рис. 10.28, в и г мы видим выражения из рис. 10.28, б с двумя подходящими значениями Т, равными 3 и 4. Разность между планами для двух узлов Я(пз) — Я(п~) должна быть не меньше, чем значение в ячейке (пмпз) в таблицах в и г (в зависимости от выбранного значения Т). Например, рассмотрим запись 2 — Т на рис. 10.28 для наидлиннейшего (простого) пути от с к 6.
Наидлиннейший простой путь от с к 6 — с — й — 6. Общая задержка вдоль этого пути — два такта, а сумма значений д — 1, которая представляет тот факт, что номер итерации должен увеличиться на 1. Поскольку Т— продолжительность промежутка между двумя итерациями, узел 6 должен быть запланирован на такт, находящийся как минимум через 2 — Т такта после такта, на который запланирован узел с. Но, поскольку Т не меньше 3, это означает, что на самом деле 6 может быть спланирован за Т вЂ” 2 такта до с или позже этого такта, но никак не ранее. Заметим, что рассмотрение непростых путей от с к 6 не дает более строгих ограничений. Можно добавить к пути с — Н вЂ” 6 любое количество итераций цикла из узлов 6 и д.
Если мы добавим )г таких циклов, то получим длину пути 2 — Т+ к 13 — Т), поскольку общая задержка вдоль пути равна 3, а сумма значений б равна 1. Поскольку Т > 3, эта длина никогда не превышает 2 — Т; таким образом, наиболее сильная нижняя граница такта 6 по отношению к такту с равна 2 — Т вЂ” тому же значению, которое было получено при рассмотрении наидлиннейшего простого пути. Например, из записей (6, с) и (с,Ь) мы видим, что Я(с) — э(6) > 1 Я(Ь) — Я(с) > 2 — Т Иначе говоря, 516) + 1 < Я1с) < 316) — 2+ Т Если Т = 3, то Я (6) + 1 < Я (с) < Я (Ь) + 1 Это означает, что узел с должен быть запланирован на следующий после 6 такт.
Если же Т = 4, то Я(Ь) + 1 < Я(с) < Я(6) + 2, так что узел с должен быть запланирован на один или два такта после 6. Информация о самом длинном пути позволяет нам легко вычислить корректное место для узла, исходя из зависимостей данных. Мы видим, что у нас нет выбора при Т = 3, но при росте Т количество возможных вариантов возрастает.о ! 0.5. Программная конвейеризация 895 Алгоритм 10.21. Программная конвейеризация Вход; вектор ресурсов целевой машины Н = [гыгз,...~, где г, — количество доступных единиц ресурса 1-го вида и граф зависимости данных С = (М, Е). Каждая операция п Е Х помечается ее таблицей резервирования ресурсов ВТ„; каждое ребро е = и! — из из Е имеет метку (Б„Н,), указывающую, что операция пз должна выполняться не ранее чем через г1, тактов после операции и! из б,-й предшествующей итерации. Выход: программно конвейеризованный план э' и интервал между запусками итераций Т.
Метод: выполнить программу, приведенную на рис. 10.29. о Алгоритм 10.21 имеет высокоуровневую структуру, аналогичную структуре алгоритма 10.19, который способен работать только с ациклическими графами. Минимальный интервал между запусками итераций в данном случае ограничен не только требованиями к ресурсам, но и циклами зависимостей данных в графе. Планирование графа выполняется путем поочередного планирования его сильно связанных компонентов. Если рассматривать каждый сильно связанный компонент как отдельный модуль, то ребра между ними обязательно образуют ациклический граф.
Если алгоритм 10.19 планирует узлы графа в топологическом порядке, то алгоритм 10.21 планирует в топологическом порядке сильно связанные компоненты. Как и ранее, если алгоритм не в состоянии спланировать все компоненты, то интервал между запусками итераций увеличивается и попытка планирования повторяется.
Заметим, что в случае ациклического графа алгоритм 10.21 ведет себя точно так же, как и алгоритм 10.19. Алгоритм 10.21 вычисляет два дополнительных множества ребер: Е' — множество всех ребер, разность итераций которых равна О, и Е' — ребра наидлиннейшего пути через все точки. Иначе говоря, для каждой пары узлов (п, р) существует ребро е е Е*, с которым связано значение Н„равное длине наидлиннейшего простого пути от р к и, что обеспечивает существование как минимум одного пути от р к и. Е' вычисляется для каждого значения интервала между запусками итераций Т. Можно также выполнить это вычисление однократно с использованием символического значения Т, а затем для каждой итерации подставлять вместо Т конкретные значения, как это было сделано в примере 10.20.
Алгоритм 10.21 использует возвраты. Если он не в состоянии спланировать сильно связанный компонент, то он пытается спланировать весь компонент на такт позже. Этн попытки продолжаются до достижения Т тактов. Возврат важен в связи с тем, что, как показано в примере 10,20, размещение первого узла сильно связанного компонента может полностью определять план для других узлов.
Если такой план не согласуется с планом, уже разработанным к этому моменту, попытка составления плана оказывается неудачной. й9б Глава 10. Параллелизм иа уровне команд тат () ( Е'=(е(еЕЕ, 6,=0) аког (Т = То, То + 1,... или пока все сильно связанные компоненты в С не будут спланированы) ( ВТ = пустая таблица резервирования с Т строками; Е* = АИРа(гзЕопдезуРай (С, Т); 1ог (каждый сильно связанный компонент С из С в приоритетном топологическом порядке) ( 1ог (все и, из С) ЗО = вуале=р п из Е",узел р спланирован Ф (Р) + сзе) ~ Ризу = некоторое и, такое, что зо (и) является минимумом; зо = зо (йгзг); 1Ьг (з = ва, з < во + Т; з = в+ 1) 11' (5ссЯсйес(и(еЫ(ЯТ, Т, С, 1 згзт, в)) Ьгеай; Ы (С не может быть спланирован в ТтТ) Ьгеак; БссБс1зег1и1ес1 (ЯТ, Т, С, ) 1тз|, з) ( КТ' = ЯТ; 11' (по1 Аеог1еБсйее1и!его (ВТ', Т, г'згИ, з)) гетцгп 1а1зе; 1ог (каждый остающийся п из с в приоритетном топологическом порядке ребер из Е') ( гч = птахе=п' и из н*,п'ес,узел п' спланирован (о (и ) + 4: .(сс х Т))1 I зо = щще=п' и из к',п'еелузея п' снланироааи (о (и ) гзе + (ае и Т)) 1ог (з = зб з < шгп (з„, з~ + Т вЂ” 1); в = з + 1) 11' (А1ойеБсйег1и!ее1 ()тТ', Т, п, в)) Ьгеаи; 11' (и не может быть спланирован в ВТ') гетнгп Га!зе; ВТ = ЛТ'; гетцгп 1гце; Рис.
10.29. Алгоритм программной конвейеризации графа зависимости данных с циклами Для планирования сильно связанного компонента алгоритм определяет самый ранний момент, когда каждый узел компонента может быть спланирован с удовлетворением всех транзитивных зависимостей данных из Е*. Затем в качестве пер- 897 10.5.
Программная конвейеризация вого планируемого узла йгзг выбирается узел с наиболее ранним временем начала. Далее алгоритм использует функцию Яссосггег!и1ег1, которая пытается спланировать компонент с использованием наиболее раннего времени начала выполнения. Алгоритм делает не более Т попыток с последовательно возрастающим временем начала. Если попытка оказывается неудачной, алгоритм пытается использовать другой интервал между запусками итераций. Алгоритм оссосггег!и(ег! напоминает алгоритм ! 0.19, но имеет три существенных отличия. 1.
Цель оссосггеди1ег! состоит в планировании сильно связанного компонента в данный интервал времени в. Если узел гггзг из сильно связанного компонента не может быть спланирован в интервале в, функция ЯссосЬег!и)ед возвращает значение !а!яе, В таком случае функция лгагп может, если это потребуется, вновь вызвать оссос)геЫи1еЫ с более поздним интервалом времени.
2. Узлы сильно связанного компонента планируются в топологическом порядке, основанном на ребрах из Е'. Поскольку разность итераций для всех ребер из Е' равна О, эти ребра не пересекают никакие границы итераций и не могут образовывать циклы. (Ребра, пересекающие границы итераций, известны как цикяонесущгге (!оор сагпег!).) Верхнюю границу размещения операций указывают только циклонесущие ребра. Итак, данный порядок планирования вкупе со стратегией по возможности наиболее раннего планирования каждой операции максимизируют диапазоны, в пределах которых могут планироваться последовательные операции.
3. Для сильно связанных компонентов зависимости указывают как нижнюю, так и верхнюю границы диапазона, в котором может планироваться узел. Функция оссосЬег!и!еИ вычисляет эти диапазоны и использует их для дальнейшего ограничения попыток планирования. Пример 10.22. Применим алгоритм 10.21 к циклическому графу зависимости данных из примера 10.20.
Сначала алгоритм вычисляет, что в данном примере граница интервала между запусками итераций равна трем тактам. Заметим, что достичь этой нижней границы невозможно. Когда интервал между запусками итераций Т равен трем, транзитивные зависимости на рис. 10.28 требуют выполнения условия Я(0) — о (6) = 2. Планирование узлов !г и г! на расстоянии двух тактов друг от друга приводит к конфликту в таблице модульного резервирования ресурсов длиной 3.
На рис. 10.30 показано поведение алгоритма 10.21 с графом из упомянутого примера. Сначала он пытается найти план для интервала между запусками итераций, равного 3. Попытка начинается с планирования узлов а. и 6 в наиболее 898 Глава 10. Параллелизм на уровне команд Рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
