указывает конец цепочки всех обращений к переменной Vi. Каждая
команда содержит в адресной части номер предыдущей команды из той
же цепочки. Если для переменной Vi отведена ячейка в памяти, то
не представляет труда подняться по соответствующей цепочке, заме-
няя адресные части команд на адрес ячейки, отведенной для Vi.
Итак, интервал для каждой переменной определяется парой чисел
(Fi,Li). Теперь можно просмотреть эти пары, чтобы распределить
память для всех переменных. Если Fi=Li, то соответствующая коман-
да ST является избыточной, как отмечалось раньше.
Интервалы просматриваются в порядке возрастания Fi. В нашем
примере переменные уже перенумерованы в этом порядке. Обычно ал-
горитм генерирования команд может быть согласован с алгоритмом
распределения памяти так, чтобы такая нумерация переменных всег-
да имела место. Для этого только требуется, чтобы порядок, в ко-
тором имена переменных впервые появляются в последовательности
команд, совпадал с порядком мест, отведенных в векторах для соот-
ветствующих ячеек Fi и Li. В нашем примере переменная V1 должна
быть определена до переменной V2 и т.д.
При просмотре интервалов в порядке возрастания значений Fi
первая переменная помещается в ячейку T1. Для каждого очередного
интервала (Fj,Lj) исследуются АКТИВНЫЕ интервалы, для которых па-
мять уже распределена, с тем чтобы выяснить, существует ли такой
интервал (Fi,Li), что Li<Fj. Если такой интервал существует, то
переменная Vj помещается в ту же ячейку памяти, что и переменная
Vi, а интервал (Fi,Li) отмечается как НЕАКТИВНЫЙ. Таким образом,
на каждом этапе активные интервалы определяют текущие переменные,
которые размещены в ячейках памяти, а также определяют моменты,
когда эти ячейки освобождаются. Если не существует активного ин-
тервала со значением Li<Fj, то нужно взять из стека новую ячейку
и отвести ее для Vj.
В нашем примере для V1 была бы отведена ячейка T1. Так как
L1>F2, то для V2 нужна новая ячейка, и поэтому для V2 была бы от-
ведена ячейка T2. С другой стороны, L2<F3, так что можно помес-
тить V3 в ту же ячейку памяти, что и V2 (т.е. в ячейку T2).
Интервал для V2 теперь отмечается как неактивный. Так как L1<F4,
то переменная V4 тоже помещается в ячейку T1.
3.3 Алгоритм Биледи
Многие ЭВМ имеют небольшой набор быстрых регистров, которые
сходны с ячейками основной памяти с той разницей, что выборка ин-
формации, запомненной в быстрых регистрах, требует во много раз
меньше времени, чем выборка из основной памяти. На самом деле,
быстрые регистры могут быть индекс-регистрами или добавочными
сумматорами. т.е. их сожержимое может использоваться специальным
образом в арифметических или логических операциях, но здесь мы не
учитываем эти свойства.
Эти быстрые регистры могут быть использованы для хранения
копий переменных, размещенных в основной памяти; что же касается
временной переменной, то она может находиться в быстром регистре
все время своего существования, не требуя места в основной памя-
ти. Если число доступных быстрых регистров превышает число нуж-
ных переменных, то проблемы не возникает и быстрые регистры мо-
гут быть распределены по алгоритму для временных переменных.
Однако если число доступных быстрых регистров не является
достаточным, то возникает ситуация, когда необходимо решать, ка-
кие из переменных должны оставаться в быстрых регистрах. Решение
будет зависеть от частоты использования различных переменных, и
алгоритм должен стремиться максимально использовать быстрые ре-
гистры.
Алгоритм Биледи приводит к оптимальному результату при неко-
торых ограничениях и часто дает хорошие результаты в более общих
случаях. Предполагается, что быстрые регистры должны применяться
для хранения копий переменных из ОП и что использовать эти пере-
менные можно только после занесения их в быстрые регистры.
В дальнейшем будем предполагать, что рассматриваемые пере-
менные не будут изменяться; поэтому, если нужно заменить ка-
кую-то переменную в быстром регистре, то нет необходимости запо-
минать текущее содержимое быстрого регистра, так как копия этого
содержимого уже есть в основной памяти.
Возникающая задача похожа на задачу замещения страниц в сис-
теме с двумя уровнями памяти.
Биледи (1966) сформулировал оптимальный алгоритм для случая,
когда известна полная картина будущих обращений, что использова-
лось в системе с двумя уровнями памяти для получения оценки эф-
фективности многих применяемых эвристических алгоритмов.
Задача распределения быстрых регистров отличается от задачи
с двумя уровнями памяти тем, что для нее нет необходимости выпол-
нять распределение до получения полной последовательности команд.
Поэтому алгоритм Биледи может быть применен непосредственно для
получения оптимальных результатов. Этот алгоритм прменялся в ком-
пиляторах в течение нескольких лет, и только с недавнего времени,
в связи с его использованием в системе с двумя уровнями памяти, с
ним стало связываться имя Биледи.
Интервалы, в которых используются основные переменные Vi,
могут быть изображены диаграммой, как показано на рис. 20.8.
V5 ├────────────────┤
V4 ├───────────────────┤
V3 ├──────────────┼──────────────────┤
V2 ├─────┼─────┼────────┤
V1 ├───────────────────────────┤
1 2 3 4 5 6 7 8 9 10 11 12 13
Рис. 20.8 Диаграмма использования переменных Vi в последова-
тельности команд
Каждая горизонтальная переменная изображает интервал для не-
которой переменной, причем точки указывают номера мест в последо-
вательности команд, где используется эта переменная. Будем пред-
полагать, что в каждой команде используется только одна перемен-
ная, так что на одной вертикали не может появится двух и более
точек. Число горизонтальных линий, пересекающихся с какой-либо
вертикалью, указывает, сколько ячеек памяти содержат в соответ-
ствующий момент нужные значения переменных. Если число пересече-
ний какой-то вертикали с различными горизонтальными линиями пре-
вышает число доступных быстрых регистров, то одна или более чем
одна из переменных не может быть помещена в быстрых регистрах.
Мы будем также полагать, что каждая выборка какой-либо пере-
менной из быстрого регистра требует ничтожной затраты времени.
Если нужной переменной нет в быстром регистре, то необходимо за-
менить содержимое одного из быстрых регистров на значение этой
переменной. Определим функцию S(i,t) следующим образом:
S(i,t)=0, если переменная Vi не находится в быстром регис-
тре в момент t;
S(i,t)=1, если Vi находится в быстром регистре в момент t.
Тогда сумма по всем номерам "t" не должна превышать N, где N
- число доступных быстрых регистров.
Если m(t) - номер переменной, используемой в команде "t", то
функцию U, характеризующую эффективность использования быстрых
регистров, можно определить следующим образом:
U=сумма S(m(t),t)).
t
Максимальное значение функции U (при заданных выше ограниче-
ниях) достигается, когда наибольшее число использований перемен-
ных будет происходить путем непосредственного обращения к быс-
трым регистрам. Единственное доп. ограничение состоит в том, что
S(m(t-1),t)=1
для всех значений t. Это означает, что каждая переменная при
использовании заносится в быстрый регистр.
Алгоритм Биледи состоит в следующем.
Последовательность команд исследуется, начиная с первой ко-
манды, определенной значением t=1. Для каждого значения t рас-
сматривается переменная Vi, где i=m(t), и выполняются действия по
одному из следующих вариантов:
(1) Для переменной Vi отведен быстрый регистр; тогда ис-
пользуется этот регистр.
(2) Для переменной Vi не отведено быстрого регистра, но
имеется неиспользованный быстрый регистр; в таком случае, этот
регистр отводится для Vi.
(3) Для переменной Vi не отведено быстрого регистра, и рас-
пределены все быстрые регистры. Тогда рассматриваются переменные,
для которых в текущий момент имеются копии в быстрых регистрах, и
если значение какой-то одной из них больше не потребуется, то
соответствующий быстрый регистр теперь отводится для Vi. Если со-
держимое всех быстрых регистров все еще необходимо, то для Vi от-
водится быстрый регистр, соответствующий той переменной, следую-
щее использование которой наиболее удалено от данной команды.
Пусть имеются 3 быстрых регистра R1, R2 и R3. Начиная с мо-
мента t=1 первые три команды отведут регистры R1, R2 и R3 для пе-
ременных V1, V2 и V3. В момент t=5 содержимое всех трех быстрых
регистров еще необходимо, а требуется регистр для V4. Переменная
V1 не будет использоваться до момента t=10, тогда как V2 ис-
пользуется при t=6 и V3 - при t=8. Поэтому регистр R1 теперь ис-
пользуется для V4. При t=7 вновь возникает такая же проблема.
Значение V4 не требуется до момента t=11, тогда как V3 ис-
пользуется при t=8 и V2 - при t=9. Поэтому регистр R1 отводится
для V5. При t=10 переменная V1 используется снова. Теперь приме-
няется сформулированное выше условие (2), так как значение V2
больше не потребуется. Поэтому регистр R2 отводится для V1. Ана-
логично при t=11 регистр К2 отводится для V4, так как больше не
потребуется значение V1.
Распределение регистров R1 и R3 для V5 и V3 сохраняется до
конца последовательности команд. Описанное распределение быстрых