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


 

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

70029. Правовая природа монополий. Виды монополий по российскому праву 14.5 KB
  Что касается сугубо юридической стороны дела то в действующем законодательстве отсутствует легальное определение понятия монополия. Монополия может возникнуть на рынке в силу различных обстоятельств исходя из которых обычно выделяются три основных типа монополий...
70030. Основные методологические принципы эмпирической науки 18.58 KB
  Часто призывают строить естественные классификации полагая что такая классификация определяется природой изучаемых явлений. Более-менее заменяет представление о естественности требование чтобы классификации были или теоретически или прагматически осмыслены.
70031. Построение и уравнивание маршрутной и блочной фототриангуляции по методу связок 117.5 KB
  При построении сети фототриангуляции методом связок для каждого изображения точки (определяемой и опорной), измеренного на снимке составляются уравнения коллинеарности...
70032. Система конкурентного права. Правовая природа отношений, складывающихся в сфере конкуренции 21.5 KB
  Конкурентное право как отрасль законодательства характеризуется конкретным предметом правового регулирования который по экономическому содержанию распадается на две группы отношений: отношения связанные с конкуренцией; 2 отношения в сфере монополий.
70034. Оптимальное распределение потоков мощности в замкнутых контурах электрической сети 62.65 KB
  Параметры режима Z делятся на независимые Y и зависимые X. Число уравнений установившегося режима 2n равно числу зависимых параметров режима Х комплексных напряжений в узлах. Общее число параметров режима Z m входящих в уравнение больше 2n – числа этих уравнений.