А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 183
Текст из файла (страница 183)
10.30. Поведение алгоритма ! 0.21 с графом из примера 10.20 ранние допустимые моменты времени. Однако после размещения узла 6 в такте 2 узел с может быть помещен только в такт 3, а это приводит к конфликту с использованием ресурсов узлом а. И а, и с требуют себе первый ресурс в те такты, которые при делении на 3 дают остаток О. Алгоритм выполняет возврат и пытается выполнить планирование сильно связанного компонента ~6, с, д~ на такт позже. В этот раз узел б размещается в такте 3, а узел с успешно размещается в такте 4.
Однако узел д не может быть размещен в такте 5. И б, и д требуют себе второй ресурс в те такты, которые при делении 899 10.5. Программная конвейеризация на 3 дают остаток О. Заметим, что это просто совпадение, что и этот конфликт, и ранее рассматривавшийся проявляются в тактах, которые при делении на 3 дают остаток О.
С тем же успехом в других примерах конфликт мог бы проявиться и в тактах, дающих остаток ! или 2. Алгоритм продолжает работу, откладывая начало планирования сильно связанного компонента !6, с, Н1 еще на один такт. Но, как уже говорилось, данный сильно связанный компонент не может быть спланирован с интервалом между запусками итераций, равным 3. Так что алгоритм прекращает попытки планирования с интервалом 3 и приступает к попыткам планирования с интервалом 4, и в конечном итоге находит оптимальный план во время шестой попытки. 10.5.9 Усовершенствования алгоритма конвейеризации Алгоритм 10.21 достаточно простой, хотя и неплохо работает на реальных целевых машинах. Важными элементами этого алгоритма являются следующие.
1. Использование таблицы модульного резервирования ресурсов для обнаружения конфликтов в устойчивом состоянии. 2. Необходимость вычисления транзитивных отношений зависимости для по- иска диапазона планирования узла при наличии циклов зависимостей. 3.
Возможность возврата, а также совместного перепланирования узлов критических циклов (циклов, которые определяют наибольшую нижнюю границу интервала между запусками итераций Т), поскольку между ними нет временных зазоров. Имеется ряд способов усовершенствования алгоритма ! 0.21. Например, в простом примере 10.22 алгоритм тратит некоторое время на то, чтобы убедиться, что интервал между запусками итераций, равный трем тактам, неприемлем. Можно сначала независимо спланировать сильно связанные компоненты для того, чтобы выяснить пригодность интервала между запусками итераций для каждого компонента. Можно также изменить порядок планирования узлов. Порядок, использованный в алгоритме 10.21, имеет несколько недостатков.
Во-первых, поскольку нетривиальные сильно связанные компоненты планируются сложнее тривиальных, их желательно планировать первыми. Во-вторых, некоторые регистры могут иметь неоправданно длительное время жизни. Желательно размещать определения поближе к соответствующим использованиям.
Одна из возможностей заключается в том, чтобы начинать работу с сильно связанных компонентов с критическими циклами, а затем с двух сторон расширять план. 900 Глава 1О. Параллелизм на уровне команд Есть ли альтернативы эвристикам Задачу одновременного поиска оптимального плана и распределения регистров можно сформулировать в виде задачи целочисленного линейного программирования. При том что многие задачи целочисленного линейного программирования могут быть решены достаточно быстро, некоторые из них требуют для решения непомерного количества времени.
Чтобы реально использовать целочисленное линейное программирование, необходимо иметь возможность прервать вычисления, если они не укладываются в некоторые предопределенные пределы. Такой подход был эмпирически испытан на целевой машине (8О! 18000), и было обнаружено, что для большой части программ удавалось за приемлемое время найти оптимальное решение поставленной задачи. Оказалось также, что планы, полученные с применением эвристического подхода, достаточно близки к оптимальным. Таким образом, выяснилось, что использовать подход целочисленного линейного программирования не имеет особого смысла.
Тем более что в связи с тем, что решение задачи линейного программирования может не быть получено за предопределенное время, в компиляторе все равно требуется иметь эвристический планировщик. Однако решения, полученные с его помощью, отличаются от оптимальных в столь незначительной степени, что при наличии эвристического планировщика просто нет смысла в реализации еще и планировщика на основе целочисленного линейною программирования. 10.5.10 Модульное расширение переменных Скалярная переменная называется приватизируемой (рпчабгаЫе) в цикле, если время ее жизни не выступает за пределы итерации. Другими словами, приватизируемая переменная не должна быть активна до входа в любую итерацию или после выхода из нее.
Название таких переменных связано с тем, что различные процессоры, выполняя различные итерации цикла, могут иметь собственные частные копии переменной, таким образом, никак не влияя друг на друга. Расширение переменной (чайаЫе ехрапгйоп) означает преобразование по превращению приватизируемой скалярной переменной в массив, такой, что зхя итерация цикла читает и записывает зхй элемент этого массива. Такое преобразование устраняет ограничения антизависимости между чтениями в одной итерации и записями в последующих, как и выходные зависимости между записями в разных итерациях. Если все циклонесущие зависимости оказываются устраненными, то все итерации цикла могут выполняться параллельно. 901 10.5.
Программная конвейеризация Устранение циклонесущих зависимостей и, таким образом, устранение циклов в графе зависимости данных может существенно повысить эффективность программной конвейеризации. Как показано в примере 10.15, нам не требуется расширение приватизируемой переменной на количество итераций цикла. Одновременно может выполняться только небольшое количество итераций, а приватизируемые переменные могут быть одновременно активны даже в меньшем количестве итераций. Одна и та же память может использоваться для хранения переменных с неперекрывающимися временами жизни.
Говоря конкретнее, если время жизни регистра равно 1 тактам, а интервал между запусками итераций равен Т, то в любой одной точке могут быть активны только д = [ЦТ~ значений. Мы можем выделить для переменной т! регистров, используя в т-й итерации (т тпот) т1)-й регистр. Такое преобразование называется лтодульньтм расширением переменной (тпот(п! аг чаг(аЫе ехрапз)оп). Алгоритм 10.23. Программная конвейеризация с модульным расширением пере- менной Вход: граф зависимости данных и описание ресурсов машины. Выход: два цикла; один — программно конвейеризованный, а второй — неконвейеризованный. Метод: выполнить следующие действия.
1. Устранить циклонесущие антизависимости и выходные зависимости, связанные с приватизируемыми переменными из графа зависимости данных. 2. Программно конвейеризовать получающийся в результате граф зависимостей с использованием алгоритма 10.21. Пусть Т вЂ” интервал между запусками итераций, для которого найден план, а Л вЂ” длина плана одной итерации. 3. Вычислить для получившегося плана 9„минимальное количество регистров, необходимых для каждой приватизируемой переменной в. Пусть Я = тпах„д„.
4. Сгенерировать два цикла: программно конвейеризованный и неконвейеризованный. Программно конвейеризованный цикл содержит (1 (Т) + т т — 1 копий итераций, размещенных на расстоянии Т тактов друг от друга. Его пролог состоит из ((ЦТ~ — 1) Т команд, устойчивое состояние — из ЯТ команд, а эпилог — из Л вЂ” Т команд. Вставить команду цикла, которая выполняет ветвление из конца устойчивого состояния в его начало. Количество регистров, назначенных приватизируемой переменной и, равно т1„если Я шот) д„= О, Чз 1~ в противном случае.
902 Глава 1О. Параллелизм на уровне команд Переменная и в 1-й итерации использует (г тос1 д,')-й из назначенных ей регистров. Пусть п — переменная, представляющая количество итераций исходного цикла. Программно конвейеризованный цикл выполняется, если и > |1,(Т1 + Я вЂ” 1. Количество выполнений вставленной команды цикла равно и — |ЦТ1 + 1 п1 = Таким образом, количество исходных итераций, выполняемых программно конвейеризованным циклом, равно [й/Т1 — 1+ Яиц если и > |т /Т1 + Я вЂ” 1, пг = 0 в противном случае. Количество итераций, выполняемых неконвейеризованным циклом, равно пз = и — пз. о Пример 10.24.
В случае программно конвейеризованного цикла на рис. 10.22 Ь = 8, Т = 2 и Я = 2. Программно конвейеризованный цикл содержит 7 копий итераций с прологом, устойчивым состоянием и эпилогом, состоящими соответственно из 6, 4 и б команд. Пусть п — количество итераций в исходном цикле. Программно конвейеризованный цикл выполняется, если и > 5; в этом случае команда цикла выполняется раз, а программно конвейеризованный цикл отвечает за 8+2х итераций исходного цикла. Модульное расширение увеличивает размер устойчивого состояния в Я раз.
Несмотря на это увеличение код, сгенерированный алгоритмом 10.23, остаемся достаточно компактным. В наихудшем случае программно конвейеризованный цикл будет содержать в три раза больше команд, чем спланировано для одной итерации. Грубо говоря, вместе с дополнительным циклом для обработки остающихся операций общий размер кода вырастает примерно в 4 раза по сравнению с первоначальным. Поскольку данный метод обычно применяется для небольших внутренних циклов, такое увеличение оказывается вполне приемлемым. Алгоритм 10.23 минимизирует увеличение кода ценой использования большего количества регистров.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
