Алгоритм Биледи

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 сохраняется до

конца последовательности команд. Описанное распределение быстрых

регистров показано диаграммой на рис. 20.9.

V5 ├─────────────────┤

V4 ├────── ─ ─ ─ ─ ─ ──┤

V3 ├───────────────┼──────────────────┤

V2 ├─────┼─────┼────────┤

V1 ├──────────── ─ ─ ─ ─ ─ ─ ──┤

1 2 3 4 5 6 7 8 9 10 11 12 13

Рис. 20.9 Диаграмма использования переменных Vi в последова-

тельности команд, поясняющая работу алгоритма Биледи

4. ТАБЛИЦА СИМВОЛОВ

4.1 Описатели

Для каждого вхождения идентификатора в исх. программе осу-

ществляется поиск соотв. элемента в таблице символов (ТС), инфор-

мация, полученная при данном вхождении, сопоставляется с ранее

полученной информацией, выполняется необходимый контроль и регис-

трация новой информации. Таким образом, ТС является очень важной

частью компилятора и, в некотором смысле, узловой точкой всей

трансляции. Ее структура должна допускать эффективный поиск и

внесение информации. В то же время, каждый элемент должен зани-

мать как можно меньше места, для того, чтобы хватало места на

большие программы с большим числом идентификаторов. Вообще гово-

ря, желательно, чтобы возможно меньшее число программ транслято-

ра непосредственно работало с ТС. Это позволит достаточно легко

вносить необходимые изменения. Особенно важно тщательно согласо-

вать формат описателя до того, как начнется программирование

транслятора.

ОПИСАТЕЛЕМ называется часть элемента ТС, в которой описы-

вается идентификатор. Существует другой термин для обозначения

этого же понятия, введенный Фельдманом - "семантическое слово" (У

Ахо и Ульмана это назывется "дескриптором").

Количество информации, которое нужно хранить в описателе,

зависит от того, чем является фактически идентификатор - простой

переменной, массивом, функцией и т.д. Поэтому в некоторых реали-

зацих описатели имеют переменную длину. Это допустимо не при лю-

бой организации ТС. Иногда в целях экономии памяти выбирают эле-

мент ТС малого размера, а для идентификаторов, требующих больше

места, отводят по несколько соседних элементов.

Другая возможность открывается, емли в нужных случаях отво-

дить часть описателя под указатель, ссылающийся на дополни-

тельную таблицу. Это несколько осложняет программирование, пос-

кольку тип описателя может менять свой смысл в зависимости от ти-

па элемента.

Похожие работы

Программное обеспечение удалённого доступа к технической документации

Скачать

84334

30

0

... работы. В ходе работы над дипломным проектом разработан транслятор. Проблема создания такого транслятора является очень актуальной, т.к. многим пользователям САПР необходимо доступ к технической документацию, которую удобнее хранить на удаленных серверах в формате HTML. Поэтому степень положительного эффекта от выполнения дипломного проекта научно-исследовательского характера 1=6.5. В ...

Андрей Петрович Ершов (1931-1988)

Скачать

50249

0

1

... направления, активно развиваемого сейчас в разных коллективах и странах. Отталкиваясь от трансформационной модели смешанных вычислений и от своих работ в области трансляции и оптимизации программ, Ершов определяет концепцию трансформационной машины. Трансформационная машина есть абстрактное вычислительное устройство, выполняющее программы в некотором "сверхязыке", действиями которого являются ...

Программа–конструктор для построения МП–транслятора по его параметрам с последующей проверкой задаваемых пользователем цепочек

Скачать

36295

1

7

... 166, 16 Mb RAM, Windows 95 Вывод   В ходе разработки курсового проекта я ближе ознакомился с теорией МП- трансляторов, научился писать программы - конструкторы для построения МП – транслятора по его параметрам с последующей проверкой задаваемых цепочек, закрепил знания по системному программированию. Разрабатывая программу, я научился применять знания дискретной математике, что облегчает ...

Технологии проектирования в инженерных средах

Скачать

141647

0

0

... позволяет связывать твёрдотельные модели, сборки или чертежи, созданные с помощью SolidWorks 97, с файлами других приложений, что значительно расширяет возможности автоматизации процесса проектирования. С помощью технологии OLE можно использовать информацию, полученную в других приложениях Windows, для управления моделями и чертежами SolidWorks. Например, размеры модели могут быть рассчитаны в ...