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

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

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

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

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

Просмотр 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.

Свежие статьи
Популярно сейчас