А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 176

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 176)

10.9. Обратите внимание, что план начинает с загрузки цЗ, поскольку эта команда имеет наибольшую высоту. Сложение ВЗ и В4 используют ресурсы, которые позволяют спланировать эту команду на второй такт, однако задержка 2 у команды загрузки заставляет нас спланировать эту команду на третий такт — иначе нельзя гарантировать, что регистр ВЗ будет иметь необходимое значение при выполнении сложения. и 863 10.3.

Планирование базовых блоков Таблица резервирования ресурсов Алу моп План Рис. 10.9. Результат применения планирования списка к примеру на рис. 10.7 10.3.4 Упражнения к разделу 10.3 Упражнение 10.3.1. Для каждого из фрагментов кода на рис. 10.10 постройте граф зависимости данных. В2 В2 Рис. 10.10. Машинный код к упражнению 10.3.1 Упражнение 10.3.2.

Предположим, что у машины имеется только один ресурс АЛУ (для операпий АРР и ЯПВ) и один ресурс МОП (для операций РР и БТ). Предположим, что все операции выполняются за один такт, кроме операции РР, требующей для выполнения два такта. Однако, как в примере 10.6, операция ЯТ при работе с той же ячейкой памяти, что и предшествующая ей операция РР, может начинаться через один такт после начала операции РР. Найдите кратчайшие планы для каждого из фрагментов кода на рис. 10.10. Упражнение 10.3.3. Повторите упражнение 10.3.2 в предположении, что 1. у машины один ресурс АЛУ и два ресурса МОП; 2.

у машины два ресурса АЛУ и один ресурс МОП; 1) Е0 к1,а 2) 00 Рс2, Ь 3) Я1)В КЗ, К1, Е2 4) А00 К2, К1, К2 5) БТ а, РсЗ 6) ЯТ Ь, Рс2 а) 1,Р В1, а 1Р В2, Ь БРВ В1, В1, АРР К2, В1, ЯТ а, В1 ЯТ Ь, К2 б) 1Р В1, а 1Р П2, Ь ЯРВ ВЗ, К1, Р2 АРР В4, В1, В2 ЯТ а, РЗ БТ Ь, В4 в) 864 Глава 10. Параллелизм на уровне команд 3.

у машины два ресурса АДУ и два ресурса МОП. Упражнение 10.3.4. Предположим, что мы работаем с моделью машины из при- мера 10.6 (как в упражнении 10.3.2). а) Изобразите граф зависимости данных для кода на рис. 10.1!. б) Укажите критические пути для построенного вами графа. ! в) Укажите все возможные планы для этих семи команд в предположении неограниченности ресурса МОП.

1) Ь!З К1, а 2) ЯТ Ъ, К1 3) х!э к2, с 4) ЯТ с, К1 5) Ь0 К1, с1 б) БТ с1, К2 7) ЯТ а, К1 Рис. 10.1!. Машинный код к упражнению 10.3.4 10.4 Глобальное планирование кода Для машины со средним параллелизмом на уровне команд планы, создаваемые путем работы с индивидуальными базовыми блоками, как правило, приводят к простаиванию большого количества ресурсов. Для более эффективного использования машинных ресурсов необходимо рассмотреть стратегии генерации кода, которые перемешают команды между базовыми блоками. Такие стратегии, которые рассматривают одновременно больше одного базового блока, называются алгоритмами гвобальново пванировалия.

Для корректного глобального планирования следует рассматривать не только зависимости данных, но и зависимости управления. Мы должны гарантировать, что 1. оптимизированная программа выполняет все команды исходной программы; 2. хотя оптимизированная программа и может выполнять некоторые команды с упреждением, они не имеют никаких нежелательных побочных действий. 1ОУК Глобальное планирование кода 865 10.4.1 Примитивное перемещение кода Рассмотрим вопросы, возникающие при перемещении кода, на простом примере. Пример 10.9.

Предположим, что наша машина в состоянии выполнить любые две операции за один такт. Каждая операция выполняется с задержкой в один такт, за исключением операции загрузки, задержка которой составляет два такта. Для простоты мы считаем, что все обращения к памяти в примере корректны и удовлетворяются кэшем. На рис. 10.12, а показан простой граф потока с тремя базовыми блоками. Преобразованный в машинные команды код показан на рнс. 10.12, б. Все команды в каждом базовом блоке из-за зависимости данных должны выполняться последовательно, так что в каждый базовый блок вставлены команды "нет операции".

Предположим, что адреса переменных а, 6, с, й и е различны и что эти адреса хранятся в регистрах с й2 по К5 соответственно. Таким образом, вычисления в разных базовых блоках не зависимы по данным. Заметим, что все операции в базовом блоке Вз выполняются независимо от того, по какому из путей ветвления пойдет программа, а значит, они могут выполняться параллельно с операциями из базового блока Вь Перемещать операции из базового блока В~ в базовый блок Вз мы не можем, поскольку они необходимы для определения выбираемого пути ветвления. Операции в базовом блоке Вз зависят по управлению от проверки в блоке Вь Можно выполнить упреждающую загрузку из блока Вз в блоке Вы сэкономив тем самым 2 такта времени выполнения.

Упреждающие сохранения выполнять нельзя, поскольку они переписывают старые значения в ячейках памяти. Однако операции сохранения можно отложить. Мы не можем просто перенести операцию сохранения из базового блока Вв в блок Вз, поскольку она должна выполняться только в том случае, когда поток управления проходит через базовый блок Вз. Однако можно поместить операцию сохранения в копию блока Вз. На рнс.

10.12, в показан такой оптимизированный план. Оптимизированный код выполняется за четыре такта (это то же время, которое требовалось для выполнения одного лишь блока Вз до оптимизации). о В примере 10.9 показана допустимость перемещения операций вверх и вниз по пути выполнения. Каждая пара базовых блоков в данном примере имеет различное "отношение доминирования", а потому различно и определение, когда и как можно выполнить перемещение команд в пределах пары. Как говорилось в разделе 9.6.1, базовый блок В доминирует над блоком В', если любой путь от входа в граф потока управления к базовому блоку В' проходит через блок В.

Аналогично базовый блок В постдоминирует (розЫош)па1е) над блоком В', если любой путь от базового блока В' к выходу из графа потока проходит через базовый блок В. Если базовый блок В доминирует над базовым блоком В', а ба- збб Глава 1О. Параллелизм на уровне команд а) Исходная программа б) Локально спланированный машинный кол а) Глобально спланированный машинный кол Рис. 10.12. Графы потоков до и после глобального планировании в примере 10.9 зовый блок В' постдомииирует над базовым блоком В, мы говорим, что базовые блоки В и В' эквивалентны с точки зрения управления, что означает, что один из 867 10.4.

Глобальное планирование кода этих базовых блоков выполняется тогда и только тогда, когда выполняется второй. В примере на рис. !0.12, считая базовый блок В1 входом, а базовый блок Вз— выходом, мы получим следующие взаимоотношения базовых блоков. 1. Базовые блоки В| и Вз эквивалентны с точки зрения управления: В1 доминирует над Вз, а Вз постдоминирует над Вп 2. Базовый блок В1 доминирует над базовым блоком Вз, но блок Вз не пост- доминирует над базовым блоком Вп 3. Базовый блок Вз не доминирует над базовым блоком Вз, но базовый блок Вз постдоминирует над блоком Вз.

Пара блоков вдоль пути выполнения может также не быть связана ни отношением доминирования, ни отношением постдоминирования. 10.4.2 Восходящее перемещение кода Давайте теперь внимательно рассмотрим, что собой представляет перемещение кода вверх по пути выполнения. Предположим, что мы хотим переместить операцию из блока згс вверх по пути управления в базовый блок оп Предположим, что такое перемещение не нарушает никакие зависимости данных и что оно делает пути, проходящие через юг и хгс, более быстро выполняющимися. Если сЬг доминирует над ягс, то перемещенная операция выполняется раз и только раз, когда она должна быть выполнена.

Если ягс не постдоминирует нвд хЫ В таком случае существует путь, который проходит через ~ЬБ но не достигает яс, и в результате могут быть выполнены лишние операции. Код не должен приводить к нежелательным побочным эффектам, иначе такое перемещение кода некорректно. Если выполнение перемещенной операции оказывается "бесплатным", т.е. оно использует только те ресурсы, которые иначе простаивали бы, то такое перемещение также оказывается бесплатным и повышает эффективность выполнения программы только в том случае, когда поток управления достига- ет хгс.

Если сЫ не доминирует над ягс В этом случае существует путь, который достигает я.с, не проходя при этом через ьоь Мы должны вставить копии перемещаемой операции вдоль каждого такого пути. Как это делается, мы знаем из рассмотрения устранения частичной избыточности в разделе 9.5. Мы помещаем копии операции в базовых блоках, которые образуют разрез, отделяющий входной блок от я.с. В каждом месте, в которое вставляется операция, должны удовлетворяться следующие ограничения. 868 Глава 1О.

Параллелизм на уровне команд 1. В операндах операции должны храниться те же значения, что и в исходной операции. 2. Результат выполнения операции не должен перезаписывать значение, которое потребуется в дальнейшем. 3. Этот результат также никем не перезаписывается до достижения кгс. Такие копии делают исходную команду в згс полностью избыточной, и она может быть удалена. Будем говорить о дополнительных копиях операции как о компенсирующем коде (сошрепзайоп соде). Как говорилось в разделе 9.5, для хранения таких копий могут использоваться базовые блоки, вставленные на критических путях. Компенсирующий код потенциально в состоянии сделать некоторые из путей более медленными, так что перемещение кода повышает производительность программы, только если оптимизированные пути выполняются более часто, чем неоптимизированные.

10.4.3 Нисходящее перемещение кода Предположим, что мы хотим перенести операцию из базового блока кгс вдоль пути потока управления вниз, в базовый блок азг. К такому переносу применимы те же рассуждения, что и при восходящем переносе. Если згс не доминирует над ~Ь~ В таком случае существует путь, который достигает пЫ, не посетив перед этим кгс. В этом случае, как и ранее, будут выполняться дополнительные операции.

Характеристики

Список файлов книги