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

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

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

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

Файл "Лекция 09. Планирование кода" внутри архива находится в папке "Лекции (2015)". PDF-файл из архива "Лекции (2015)", который расположен в категории "". Всё это находится в предмете "конструирование компиляторов" из 7 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .

Просмотр PDF-файла онлайн

Текст 3 страницы из PDF

Разрез, отделяющий блок Src от выхода,размещается ниже блока Src.379.4 Глобальное планирование кода9.4.6 Резюме по восходящему и нисходящему перемещению кодаПеремещение команд между эквивалентными по управлениюбазовыми блоками – простейшее и наиболее эффективное: нетребуется ни дополнительных команд, ни компенсирующего кода.Если при перемещении кода вверх Src !postdom Dst(либо при перемещении кода вниз Src !dom Dst),может потребоваться выполнение дополнительных команд.Поэтому такое перемещение кода выгодно в том случае, когдадополнительные операции могут быть выполнены бесплатно(с использованием только тех ресурсов, которые иначепростаивали бы), и когда выполняется путь, проходящий через Src.389.4 Глобальное планирование кода9.4.6 Резюме по восходящему и нисходящему перемещению кодаЕсли при перемещении кода вверх Dst !dom Src(либо при перемещении кода вниз Dst !postdom Src),требуется компенсирующий код.Пути с компенсирующим кодом могут оказаться замедленными,поэтому важно, чтобы оптимизированные пути выполнялись чаще,чем неоптимизированные.Если при перемещении кода вверхSrc !postdom Dst & Dst !dom Src(либо при перемещении кода внизSrc !dom Dst & Dst !postdom Src),требуется компенсирующий код и может потребоватьсявыполнение дополнительных команд399.4 Глобальное планирование кода9.4.7 ЗамечанияВ примере на рисунке в блок B1 может быть перенесено иприсваивание х = 2, и присваивание х = 1, так как при такомпреобразовании сохраняются все зависимости исходнойпрограммы.Однако после того, как одно из присваиваний будет перенесено вB1, второе переносить будет нельзя, так как до перемещенияпеременная х не является живой на выходе из блока B1,а после перемещения становится живой.Если в некоторой точке программы переменная жива, тоупреждающее определение этой переменной не может бытьперемещено выше данной точки.B1B2B3B4409.4 Глобальное планирование кода9.4.7 ЗамечанияB1B2B3B4Пример также показывает, что перемещение кода можетизменить отношения зависимостей по данным между командами.Таким образом, после каждого перемещения кода следуетвыполнять обновление зависимостей по данным419.4 Глобальное планирование кода9.4.8 Алгоритм глобального планирования на основе областейРассмотрим планировщик, который поддерживает двепростейшие разновидности перемещения кода:перемещение команд вверх в блоки, эквивалентные сточки зрения управления;упреждающее перемещение команд по одной из ветвейв предшествующий доминирующий блок (тоже вверх).Алгоритм планирования использует области (регионы)область – это подмножество базовых блоков ГПУ,которые могут быть достигнуты через один входнойбазовый блоксуществует три типа областей:область-листобласть-телообласть-цикл (имеется в виду естественный циклс единственной обратной дугой)любая процедура может быть представлена какиерархия областей429.4 Глобальное планирование кода9.4.8 Алгоритм глобального планирования на основе областейПорядок обхода графа потока:Все обратные ребра удаляются – граф потокастановится ациклическимВсе зависимости, идущие к заголовку области,удаляются из графа зависимостей – граф зависимостейстановится ациклическимПланирование кода ведется от внутренних областей квнешним: сначала планируется код в областях-листьях(базовых блоках), потом в областях-телах первогоуровня, потом в областях-телах второго уровня и т.д.При планировании области каждая вложеннаяподобласть рассматривается как черный ящик:команды не могут перемещаться в подобласть или изнее; однако команды могут перемещаться вокругподобласти при условии удовлетворения ограниченийзависимостей по данным и по управлению439.4 Глобальное планирование кода9.4.8 Алгоритм глобального планирования на основе областейПорядок обхода графа потока (окончание):Базовые блоки в каждой области посещаются втопологическом порядке.

Такое упорядочениегарантирует, что базовый блок не будет планироватьсядо тех пор, пока не будут спланированы все команды, откоторых он зависит.Команды, которые должны быть спланированы вбазовом блоке В, выводятся изо всех блоков,эквивалентных по управлению блоку В (включая самбазовый блок В), а также из непосредственныхпреемников блока В, над которыми он доминирует449.4 Глобальное планирование кода9.4.8 Алгоритм глобального планирования на основе областейПланирование внутри каждого базового блока ведется спомощью алгоритма планирования списком, который поддерживаетCandInsts – приоритетный список команд-кандидатов, содержащийкоманды блоков-кандидатов, все предшественники которых ужеспланированыВ списке CandInsts используется функция приоритета,подобная функции приоритета для планированиясписком, но с одним важным изменением (онообеспечивает выполнение команд из блоков-преемниковблока только с упреждением):командам блоков, эквивалентных по управлению блоку В,назначается более высокий приоритет, чем командамблоков-преемников.План создается такт за тактом.459.4 Глобальное планирование кода9.4.8 Алгоритм глобального планирования на основе областейПланирование внутри каждого базового блока ведется спомощью алгоритма планирования списком, который поддерживаетCandInsts – приоритетный список команд-кандидатов, содержащийкоманды блоков-кандидатов, все предшественники которых ужеспланированыДля каждого такта в порядке приоритета проверяетсякаждая команда n из списка CandInsts и включается вплан, если позволяют ресурсы (функция S(n)).Затем обновляется список CandInstsПроцесс повторяется до тех пор, пока не будутспланированы все команды из базового блока В.469.4 Глобальное планирование кода9.4.8 Алгоритм глобального планирования на основе областейСписок CandInsts формируется следующим образом:Функция ControlEquiv(В) строит множество блоков,эквивалентных блоку В по управлениюФункция DominatedSucc, примененная к множествубазовых блоков, строит множество базовых блоков,являющихся преемниками как минимум одного блокамножества, для которых все блоки множества являютсядоминирующимиСтроится множество CandBlocks: оно состоит измножества блоков, эквивалентных рассматриваемомублоку В по управлению, к которому добавленыдоминируемые последователиВ список включаются все уже спланированные командыиз множества CandBlocksФормирование плана с помощью функции S(n, B, t) – включениекоманды n из B блока в план на такт t.479.4 Глобальное планирование кода9.4.9 Развертка цикловПланирование на основе областей ведется в рамках однойитерации цикла, так что граница итерации цикла являетсябарьером для перемещения кода.Простой, но эффективный метод упрощения этой проблемысостоит в частичной развертке цикла перед планированием кода.Цикл for вида:for ( i = 0; i < N; i++ ) {S (i) ;}можно переписать следующим образом:489.4 Глобальное планирование кода9.4.9 Развертка цикловЦикл for вида:for ( i = 0; i < N; i++ ) {S(i) ;}можно переписать следующим образом:for}for(i = 0;S(i) ;S(i+1);S(i+2);S(i+3) ;i+4(;S(i) ;< N;)i< N;i+=4){{}499.4 Глобальное планирование кода9.4.9 Развертка цикловЦикл RepeatRepeatS;until С;можно переписать следующим образом:Repeat {S;if (C) break;S;if (C) break;S;if (C) break;S;} until C;Развертывание создает в теле цикла большое количествокоманд, позволяя алгоритму глобального планирования достичь50большей степени параллелизма.9.4 Глобальное планирование кода9.4.10 Взаимодействие с динамическим планировщикомДинамический планировщик – это, как правило, аппаратныйпланировщик OoO-процессораДинамический планировщик обладает тем преимуществом, чтоон может создавать новые планы в зависимости от условийвремени выполнения, и не рассматривать заблаговременно всевозможные планы.Если целевой процессор оснащен динамическим планировщиком(принадлежит классу OoO), основная функция статическогопланировщика состоит в обеспечении ранней выборки командс большими задержками, чтобы динамический планировщик могзапланировать как можно более раннее выполнение этих команд.Это особенно эффективно в том случае, когда в целевомпроцессоре имеются команды предвыборки данных.В частности, предвыборка данных помогает предотвратитьпромахи кэша, представляющие собой класс непредсказуемыхсобытий, которые могут привести к большим разбросампроизводительности программы.51.

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