А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 175
Текст из файла (страница 175)
Мы рассмотрим простой, но высокоэффективный алгоритм для решения этой задачи, называющийся планирование списка (1ци зсЬедц1(п8). 10.3.1 Графы зависимости данных Представим каждый базовый блок машинных команд при помощи графа зависимости данных (ба1а-береженое 8гарЬ) С = (Х, Е), содержащего множество узлов Х, представляюгдих операции в машинных командах базового блока, и множества ориентированных ребер Е, представляющих ограничения зависимостей данных между операциями. Узлы и ребра графа С строятся следующим образом.
1. Каждая операция п Е )ч' имеет таблицу резервирования ресурсов ЛТ„, которая представляет собой таблицу резервирования ресурсов для типа операции п. 2. Каждое ребро е е Е помечено задержкой с(„указывающей, что целевой узел должен быть выполнен не ранее, чем через И, тактов после выполнения исходного узла. Предположим, что за операцией п~ следует операция пз, причем обе обращаются к одной и той же ячейке памяти с запаздываниями 1~ и 1з соответственно.
Иначе говоря, значение в ячейке создается через 1~ тактов после начала первой команды и требуется второй команде через 1з тактов после ее начала (типичными являются значения 1~ = 1 и 1з = О). В таком случае в множестве Е имеется ребро п~ — из, помеченное задержкой 1~ — 1з. !) 10 г1, 2) 10 г2, 3) А1з1З т1, 4) Ь1З г2, 5) 11З гз, 6) А1зр г2, 7) АР0 г1, 8) 11З г2, 9) Ь1Э гЗ, 10) АИ1 г2, 11) АОй г1, х т2, гз т1, г2 у г г2, гз г1, г2 // // // // // // // // // // // 859 10.3. Планирование базовых блоков Пример 10.6. Рассмотрим простую машину, которая может выполнять в каждый момен~ времени две операции.
Первая должна быть либо операцией ветвления, либо операцией АЛУ вида ОР с(ат., вгс1, агс2 Вторая операция должна быть операцией загрузки или сохранения вида 10 с(ас, айдг ЯТ ас(с(г, вгс Операция загрузки (1О) полностью конвейеризуема и занимает два такта. Однако немедленно за загрузкой может следовать сохранение (ЯТ), которое записывает считанные данные в память. Все прочие операции выполняются за один такт. На рис. 10.7 приведен граф зависимости данных для примера базового блока и его требования к ресурсам. Можно представить, что 81 — указатель на стек, используемый для обращения к данным в стеке со смещениями 0 и 12.
Первая команда загружает значение в регистр В2, и это значение становится доступным только спустя два такта после начала команды. В связи с этим ребра от первой команды ко второй и пятой, в каждой из которых требуется значение 82, помечены меткой 2. Аналогично задержка 2 указана и у ребра от третьей команды к четвертой; значение, загруженное в регистр ВЗ, требуется четвертой команде и становится доступно через два такта после начала третьей команды. Поскольку мы не знаем, как связаны между собой значения 81 и В7, мы должны рассматривать возможность того, что адрес наподобие 8 ( В1 ) тот же, что и адрес 0 (В7 ) . Иначе говоря, последняя команда может сохранять значение по тому же самому адресу, из которого выполняет чтение третья.
Используемая нами модель машины позволяет выполнять сохранение в ячейке памяти через один такт после того, как мы выполнили чтение из нее, даже если за этот срок значение еще не появилось в регистре. Это замечание объясняет метку 1 у ребра от третьей команды к последней. Такая же аргументация поясняет наличие ребра от первой команды к последней и его метку 1. Оставшиеся ребра с метками ! объясняются либо явными зависимостями, либо возможными зависимостями, связанными со значением Р.7, и 10.3.2 Планирование списков базовых блоков Простейший подход к планированию базовых блоков включает посещение каждого узла графа зависимости данных в "приоритетном топологическом порядке".
Поскольку в графе зависимости данных циклы отсутствуют, всегда имеется 860 Глава 10. Параллелизм на уровне команд Таблицы резервирования ресурсов АЛУ МОП Зависимости данных ПЕ Рис. 10.7. Граф зависимости данных к примеру 10.6 как минимум одно топологическое упорядочение его узлов. Однако среди возможиых топологических упорядочений одни предпочтительнее других. В разделе 10.3.3 будут рассмотрены некоторые стратегии выбора топологического упорядочеиия, ио пока что мы просто будем считать, что существует некоторый алгоритм выбора предпочтительного упорядочения. Описанный далее алгоритм планирования списка посещает узлы в выбранном приоритетном топологичсском порядке. Узлы могут быть спланированы к выполнению как в порядке посещеиия, так и в некотором ином порядке.
Но при этом команды планируются к выполнению как можно ранее, так что порядок плаиироваиия команд приближается к порядку посещения узлов. Говоря более детально, алгоритм вычисляет наиболее раннее время, когда может быть вычислен каждый из узлов, в соответствии с ограничениями зависимости данных ранее спланированных узлов. Затем выполняется проверка наличия требующихся для узла ресурсов в таблице резервирования ресурсов, в которой собраны все выделенные к настоящему времени ресурсы. Узел планируется к выполнению в самый ранний момент, в который имеется достаточно ресурсов. 861 10.3.
Планирование базовых блоков Графическое изображение таблиц резервирования ресурсов Зачастую удобно визуализировать таблицу резервирования ресурсов для операции в виде сетки с закрашенными и пустыми ячейками. Каждый столбец соответствует одному из ресурсов машины, а каждая строка — одному из тактов выполнения операции. В предположении, что никакая операция не требует более одной единицы одного ресурса, можно представить единицы закрашенными квадратами, а нули — пустыми. Кроме того, если операция полностью конвейеризуема, то все, что нам надо, — указать используемые ресурсы в первой строке, и таблица резервирования ресурсов при этом превратится в единственную строку. Такое представление использовано, например, в примере 10.6. На рис.
10.7 таблицы резервирования ресурсов показаны в виде строк. Две операции сложения требуют ресурс АЛУ, а операции загрузки и сохранения— ресурс МОП. Алгоритм 10.7. Планирование списка базового блока ВхОд: вектор ресурсов машины К = ]гы гз,...], где г, — количество доступных единиц ресурса 1-го вида, и граф зависимости данных С = 1%, Е). Каждой операции п е Ж сопоставлена таблица резервирования ресурсов КТ„; каждое ребро е = и, — пз из Е имеет метку И„указывающую, что пз должна выполняться не ранее чем через д, тактов после пп Выход: план Я, который отображает операции из Х на временные интервалы, когда удовлетворяются все ограничения по ресурсам для данных операций и когда может начинаться выполнение последних. Метод: выполнить программу, приведенную на рис. 10.8. Вопрос о том, что такое "приоритетный топологический порядок", рассматривается в разделе 10.3.3.
и 10.3.3 Приоритетные топологические порядки Планирование списка работает без откатов: каждый узел планируется раз и только раз. Это планирование использует эвристическую функцию приоритета для выбора очередного узла среди узлов, готовых к планированию. Вот некоторые наблюдения о возможных приоритетных упорядочениях узлов. ° При отсутствии ограничений, связанных с ресурсами, кратчайший план получается при помощи критического пути 1сп11са! ра1П) — самого длинного пути в графе зависимости данных.
Метрика, используемая в качестве 862 Глава 10. Параллелизм на уровне команд ВТ = пустая таблица резервирования ресурсов; 1ог 1каждый п Е Ю в приоритетном топологическом порядке) 1 гпахб=р п)ее Ф (Р) + <~е) /* Поиск самого раннего времени возможного начала команды на основе заданного времени начала ее предшественницы. ~! тки~!е 1сушествует 1 такое, что КТ (в + 1] + ЛТ„(г( ) 72) а=а+1; !* Задержка в выполнении команды до тех пор, пока не будут доступны все необходимые ресурсы. *! Я(п) = а; 1ог 1всех 1) ггТ[а+1( = ттТ(а+1(+ КТ„[1( Рис.
10.8. Алгоритм планирования списка функции приоритета, — высота узла, представляюшая собой длину самого длинного пути от данного узла в графе. ° С другой стороны, если все операции независимы, то длина плана ограничена доступными ресурсами. Критический ресурс — это ресурс с наибольшим отношением количества использований к количеству доступных единиц ресурса. Более высокий приоритет могут иметь операции, используюшие более критические ресурсы. ° Наконец, для разрешения неопределенностей можно использовать исходный порядок операций — операция, находяшаяся в исходной программе раньше других, должна быть спланирована первой.
Пример 10.8. В случае графа зависимости данных, приведенного на рис. 10.7, критический путь имеет длину 6 тактов, включая время выполнения последней команды. Это путь, включаюший пять последних узлов, — от загрузки цЗ до сохранения Р,7. Суммарные задержки вдоль ребер этого пути равны 5, и к ним мы добавляем еше одну единицу — такт, необходимый для выполнения последней команды. При использовании высоты в качестве функции приоритета алгоритм 10.7 дает оптимальный план, показанный на рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
