20612

Использование динамического программирования при генерации кода

Лекция

Коммуникация, связь, радиоэлектроника и цифровые приборы

Пример: Пусть дана инструкция вида: add R1 R0 она может быть представлена в виде: R1:= R1 R0 Алгоритм динамического программирования разделяет задачу генерации оптимального кода для некоторого выражения на подзадачи генерации оптимального кода для подвыражений из которых состоит выражение Ei. Если E:=E1 E2 то генерация кода E разбивается на генерацию кода E1 и генерацию кода E2. Композиция получаемых элементов кода осуществляется в зависимости от типа вхождения подвыражений в основное выражение.

Русский

2013-07-31

137.5 KB

0 чел.

Лекция № 13

Использование динамического программирования при генерации кода

Может использоваться для регистровых машин при следующих условиях:

R0, Rn-1 являются взаимозаменяемыми

Инструкции должны быть представлены в виде: R1:=E1, Eiпроизвольное выражение содержащее регистры, ячейки памяти, причем если Ei включает в себя регистры, регистр Ri  должен быть один из них.

Пример:

Пусть дана инструкция вида:

add R1, R0

она может быть представлена в виде:

R1:= R1 + R0

Алгоритм динамического программирования  разделяет задачу генерации оптимального кода для некоторого выражения на подзадачи, генерации оптимального кода для подвыражений, из которых состоит выражение Ei.

Если E:=E1 + E2, то генерация кода E разбивается на генерацию кода E1 и генерацию кода E2. Композиция получаемых элементов кода осуществляется в зависимости от типа вхождения подвыражений в основное выражение. Количество подвыражений может быть больше чем 2.

Пример:

Для любой программы Р, вычисляющей дерево выражений Т можно найти эквивалентную программу Р/ такую что:

  1.  Стоимость Р/ будет не выше стоимости Р
  2.  Р/ будет использовать не большее количество регистров чем Р.
  3.  Р/ будет вычислять дерево последовательно

Критерии оптимизации

В результате выполнения преобразований на этапе оптимизации, следует придерживаться следующих правил:

  1.  смысл программы не должен изменяться
  2.  преобразования должны ускорить работу программы в целом
  3.  преобразования по оптимизации должны стоить затрачиваемых усилий.

Повышение производительности программы

Оптимизация кода:

  1.  Анализ потока управления
  2.  Анализ потока данных
  3.  Сами преобразования

Оптимизация кода

Устранение общих подвыражений.

Выражение E называют общим подвыражением, если оно было ранее вычислено и значение переменных в нем с того времени не изменилось. При этом можно избежать повторного вычисления i, если использовать ранее вычисленное значение.

Пример:

Живые переменные

Переопределяемые переменные

Б1

m, n, a

i, j, t1, v

Б2

i, a

i, t1, t2

Б3

j, a

j, t2, t5

Б4

i, a, j

t6, x, t7, t8, t9, t10, a

Б5

i, a, n

t11, x, t12, t13, t14, t15, a

Б6

i, j


 

А также другие работы, которые могут Вас заинтересовать

71340. СССР В ПЕРИОД ВЕЛИКОЙ ОТЕЧЕСТВЕННОЙ ВОЙНЫ 143 KB
  Основное население страны планировалось превратить в рабов, а саму Россию – в аграрно-сырьевой придаток Запада. Такие планы не оставили народу другой альтернативы, кроме борьбы. В этой войне речь шла не столько о борьбе нацизма и большевиков, сколько о судьбе российской государственности.
71341. Начало царствования Ивана IV. Реформы Избранной рады 76.5 KB
  На долю сына Ивана III Василия III (1505-1533) досталась нелегкая задача завершить начатое отцом объединения страны. И он блестяще осуществил эту задачу. Именно при нем были присоединены к Москве Псков, Смоленск и Рязанское княжество (завершение объединения русских земель).
71342. Понятие МЧП 204 KB
  МЧП - система правовых норм регулирующая отношения вытекающие из гражданского оборота носящие интернациональный характер в которой одной из сторон является лицо попадающее под действие частного права. МЧП - комплексная правовая система объединяющая нормы национального...
71343. Восточные славяне в древности 1 MB
  В СССР речь шла о возобновлении индустриализации начавшейся еще в царской России. Каковы были цели индустриализации 1 Преодоление технико-экономической отсталости СССР; 2 Ликвидация отсталости аграрного сектора экономики; 3 Превращение страны из аграрной в индустриальную...
71344. Восток — Запад — Россия. Зарождение и развитие мировой экономики 211 KB
  Отличительной чертой такого подхода стала углубленная характеристика не только экономических, но и социальных отношений в обществе в разные исторические периоды. Историко-хронологический и технологический подходы дают возможность обобщить социально-экономический опыт человеческой цивилизации...
71346. Периферийные устройства ЭВМ 1.1 MB
  Учебное пособие «Администрирование локальных вычислительных сетей» по дисциплине ЭВМ и телекоммуникации» предназначено для студентов Псковского государственного политехнического института специальности 220100 «Вычислительные машины, комплексы, системы и сети очно-заочной форм обучения.
71348. Глобализация - отличительная черта современного мирового сообщества 600 KB
  К глобальным проблемам человечества следует отнести, прежде всего, такие, как предотвращение третьей мировой войны, охрана окружающей среды и борьба с техногенными катастрофами, энергетическая, сырьевая, продовольственная, а также освоение космоса и Мирового океана...