Лекция 09. Планирование кода (Лекции (2015)), страница 2
Описание файла
Файл "Лекция 09. Планирование кода" внутри архива находится в папке "Лекции (2015)". PDF-файл из архива "Лекции (2015)", который расположен в категории "". Всё это находится в предмете "конструирование компиляторов" из 7 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 2 страницы из PDF
Это нужно длятого, чтобы найти и те расписания, которые были быисключены из-за антизависимостей.2.Построение графа зависимостей D.Базовый блок обходится снизу вверх. Для каждойоперации строится вершина графа, представляющаязначение, вычисленное этой операцией. Построеннаявершина соединяется дугами с вершинами,использующими это значение.219.3 Локальное планирование9.3.4 Алгоритм планирования с помощью списковАлгоритм включает следующие четыре шага3.Присваивание приоритета каждой операции.Планировщик использует эти приоритеты при выбореопераций.
Каждая вершина снабжается несколькимиоценками, используемыми планировщиком дляопределения очередной операции, которая должна бытьзапланирована, и для выбора операций, когда основнаяоценка у них одинакова. Известно несколько различныхсхем назначения приоритетов. Классическая схемаиспользует в качестве основного приоритетапродолжительность вычисления узла с учетом задержек.4.Итеративный процесс выбора вершин ипланирования их.Алгоритм устанавливает счетчик тактов в 1 и пытаетсязапланировать как можно больше операций.
Потомувеличивает счетчик тактов и переходит к планированиюследующего такта. И так далее пока все операции небудут запланированы.229.3 Локальное планирование9.3.4 Алгоритм планирования с помощью списковПервые два шага (переименование и построение графа D)не нуждаются в комментариях.Типичное вычисление приоритетов (шаг 3) состоит в обходеграфа зависимостей D и вычислении некоторых метрик.Основная часть алгоритма – это алгоритм планирования (АП),псевдокод которого (в предположении, что у целевогопроцессора всего одно ФУ) представлен на следующем слайде.АП выполняет абстрактное моделирование (симуляцию)процесса выполнения блока, уделяя основное вниманиеограничениям по времени, налагаемыми дугами графа D.239.3 Локальное планирование9.3.4 Алгоритм планирования с помощью списковCycle 1Ready leaves of DActive while (Ready Active ){for each op Activeif (S(op) + delay(op) < Cycle)thenremove op from Activefor each successor s of op in Dif s is readythen add s to Readyif Ready thenremove an op from ReadyS(op) Cycleadd op to ActiveCycle Cycle + 1249.3 Локальное планирование9.3.4 Алгоритм планирования с помощью списковЗначением переменной Cycle (такт) является номер текущеготакта.Список Ready содержит все операции, которые можновыполнить на текущем такте.
Сначала Ready содержит вселистья графа D, так как они не зависят от других операций блока.Список Active содержит все операции, которые началивыполняться на предыдущих тактах, но пока не завершились.Когда номер текущего такта меняется, из исключаются всеоперации, завершающиеся на новом тактеКачество полученного расписания зависит прежде всего отмеханизма, используемого для выборки операции из очередиReady.В простейшем случае, когда Ready содержит не более одногоэлемента на каждой итерации, алгоритм сгенерируетоптимальное расписание. В самом деле, на каждом такте либоесть единственная готовая операция, либо нет ни однойготовой операции, и у алгоритма не возникает вопросов, чтозапланировать.259.3 Локальное планирование9.3.4 Алгоритм планирования с помощью списковКогда алгоритм должен выбирать из нескольких готовыхопераций, все зависит от качества алгоритма выбора.
Алгоритмвыбирает операцию с наивысшим приоритетом. Если приоритетыравны требуется рассмотреть дополнительные критерии.Операции обмена с памятью часто имеют неопределенные инепостоянные задержки: этому способствуют промахи кэшей ипрочие особенности работы с памятью. Фактическая задержкапри этом может меняться от 0 до нескольких тысяч тактов.
Еслипланировщик исходит из наихудшей возможности, он рискуетполучить достаточно длительные простои процессора, если изнаилучшей, он спровоцирует дополнительные промахи кэша.Наиболее привлекательным представляется алгоритмсбалансированного планирования, когда задержка оцениваетсяв процессе планирования в зависимости от контекста (а также,возможно, характеристик целевого процессора).269.4 Глобальное планирование9.4.1 Вводные замечанияДля современных процессоров планы, создаваемые путем работытолько с базовыми блоками, как правило, несовершенны иприводят к простаиванию большого количества ресурсов.Для более эффективного использования машинных ресурсовможно рассмотреть стратегии планирования, использующиеперемещение команд между базовыми блоками.Стратегии планирования кода, которые затрагивают больше одногобазового блока, называются стратегиями глобальногопланирования.Стратегии глобального планирования должны гарантировать, что:оптимизированная программа выполняет все командыисходной программы;при выполнении некоторых команд исходной программыс упреждением не возникает никаких побочных действий.279.4 Глобальное планирование кода9.4.2 Зависимости по управлениюКоманда s1 зависит по управлению от команды s2, есливыполнение команды s2 определяет, будет ли выполнятьсякоманда s1.Простые примерыв конструкции if(с) s1; else s2;s1 и s2 зависят по управлению от св конструкции while (с) s;s зависит по управлению от c289.4 Глобальное планирование кода9.4.2 Зависимости по управлениюПример.
Во фрагменте кодаif (a > t)b = a * а;d = а + с;команды, соответствующие инструкциямb = а*а и d = a+с ,не зависят по данным от других частей фрагмента.команда, соответствующая инструкции b = а*а,зависит по управлению от сравнения а > tкоманда, соответствующая инструкции d = а + с,не зависит от сравнения а > t ни по данным, ни поуправлению299.4 Глобальное планирование кода9.4.2 Зависимости по управлениюПример. Во фрагменте кодаif (a > t)b = a * а;d = а + с;команды, соответствующие инструкциямb = а*а и d = a+с ,не зависят по данным от других частей фрагмента.команда, соответствующая инструкции b = а*а,зависит по управлению от сравнения а > tкоманда, соответствующая инструкции d = а + с,не зависит от сравнения а > t ни по данным, ни поуправлению309.4 Глобальное планирование кода9.4.3 Эквивалентность по управлениюОпределение.
Если базовый блок В является доминаторомбазового блока В', а блок В' - постдоминатором блока В, то блокиВ и В' называются эквивалентными по управлению,что означает, что блок В выполняется тогда и только тогда, когдавыполняется блок В'.Возможны следующие отношения междублоками: Блоки В1 и В4 эквивалентны по управлению:В1 = Dom(В4) & В4 = Postdom(В1) Блок В1 доминирует над блоком В2, а блокВ2 не постдоминирует над блоком В1. Блок В2 не доминирует над блоком В4, аблок В4 постдоминирует над блоком В2. Блоки В2 и В3 не связаны ни отношениемдоминирования, ни отношениемпостдоминирования.B1B2B3B4319.4 Глобальное планирование кода9.4.4 Перемещение кода вверх по пути управленияПусть команда из блока Src перемещается вверх по путиуправления в блок Dst, не нарушая никаких зависимостей поданным.если Dst доминирует над Src,перемещенная команда выполняется только один разесли Dst не доминирует над Src,существует один или несколько путей, которые достигаютSrc, но не проходят через Dst; в этом случае в базовыеблоки, которые образуют разрез, отделяющий входнойблок от Src необходимо вставить компенсирующийкод: копии перемещаемой команды (чтобы онавыполнялась на всех путях, достигающих Src).329.4 Глобальное планирование кода9.4.4 Перемещение кода вверх по пути управленияПусть команда из блока Src перемещается вверх по путиуправления в блок Dst, не нарушая никаких зависимостей поданным.если Src не постдоминирует над Dst,существует один или несколько путей, которые проходитчерез Dst, но не достигают Src, и в результате на этихпутях могут быть выполнены лишние команды; этилишние команды не должны приводить к нежелательнымпобочным эффектам, иначе перемещение коданекорректно339.4 Глобальное планирование кода9.4.4 Перемещение кода вверх по пути управленияПеремещение кода повышает эффективность программытолько тогда, когда оно использует только те ресурсы, которыеиначе простаивали бы; такое перемещение называетсябесплатнымВ каждом месте разреза, в которое вставляется компенсирующаякоманда, должны удовлетворяться следующие ограничения:операнды вставленной команды должны иметь те жезначения, что и в исходной команде.результат выполнения команды не должен убиватьзначения, которое потребуется в дальнейшем.результат команды нельзя убивать до достижения Src.Компенсирующий код потенциально в состоянии сделатьнекоторые из путей более медленными, так что перемещениекода повышает производительность программы, только еслиоптимизированные пути выполняются более часто, чемнеоптимизированные349.4 Глобальное планирование кода9.4.5 Перемещение кода вниз по пути управленияПусть команда из блока Src перемещается вниз по пути управленияв блок Dst, не нарушая никаких зависимостей по данным.если Dst постдоминирует над Src,то перемещенная команда выполняется только один разесли Src не доминирует над Dst,то существует один или несколько путей, которыедостигают Dst, минуя Src; в этом случае будутвыполняться дополнительные операции.359.4 Глобальное планирование кода9.4.5 Перемещение кода вниз по пути управленияЕсли перемещение кода вниз применяется к операциям записи,может возникнуть побочный эффект – убивается старое значение.Обойти это можно:либо создав дубликаты базовых блоков на пути от Src кDst и разместив команды записи в новых копиях блоков;либо, при возможности, используя предикатныекоманды таким образом, чтобы они были защищенытем же предикатом, что и блок Src;для этого предикатная команда должна размещаться вблоке, над которым доминирует вычисление предиката,так как иначе предикат будет недоступен.369.4 Глобальное планирование кода9.4.5 Перемещение кода вниз по пути управленияПусть команда из блока Src перемещается вниз по пути управленияв блок Dst, не нарушая никаких зависимостей по данным.Если Dst не постдоминирует над Src,существует один или несколько путей, которые проходятчерез Src, но не достигают Dst; в этом случае в базовыеблоки, которые образуют разрез, отделяющий Src отвыходного блока необходимо вставить компенсирующийкод: копии перемещаемой команды (чтобы онавыполнялась на всех путях от Src до выхода).Замечание.