Главная » Все файлы » Просмотр файлов из архивов » PDF-файлы » Лекция 09. Планирование кода

Лекция 09. Планирование кода (Лекции (2015)), страница 2

PDF-файл Лекция 09. Планирование кода (Лекции (2015)), страница 2 Конструирование компиляторов (52922): Лекции - 7 семестрЛекция 09. Планирование кода (Лекции (2015)) - PDF, страница 2 (52922) - СтудИзба2019-09-18СтудИзба

Описание файла

Файл "Лекция 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 до выхода).Замечание.

Свежие статьи
Популярно сейчас
Как Вы думаете, сколько людей до Вас делали точно такое же задание? 99% студентов выполняют точно такие же задания, как и их предшественники год назад. Найдите нужный учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Нашёл ошибку?
Или хочешь предложить что-то улучшить на этой странице? Напиши об этом и получи бонус!
Бонус рассчитывается индивидуально в каждом случае и может быть в виде баллов или бесплатной услуги от студизбы.
Предложить исправление
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
5076
Авторов
на СтудИзбе
455
Средний доход
с одного платного файла
Обучение Подробнее