Лекция 09. Планирование кода (Лекции (2015)), страница 3
Описание файла
Файл "Лекция 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.