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


 

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

78831. Театр. Theatre 48.5 KB
  Every nation and every country has its own customs and traditions. In Great Britain traditions play a more important part in the life of the people than in other countries. Englishmen are proud of their traditions and carefully keep them up.
78832. Добридень тобі, Україно моя! 141 KB
  Мета: Проаналізувати особливості життєвого та творчого шляху Павла Тичина; дослідити роль П. Тичини як громадського діяча. Розвивати пам’ять, декламаторські здібності, виховувати любов до українського поетичного слова, формувати національну свідомість, творчу особистість.
78833. Вже у фермера в дворі наступає Новий рік 48.5 KB
  Срібні дзвіночки дзвеніли під вікнами і все що бажали у цей святковий день маленькі колядники неодмінно збувалося. Входять до классу колядники Панігосподарко Чи дозволите колядувати Колядувати дім звеселяти А як же Кажуть що в тій хаті і добра не буде яку колядники...
78834. Шевченкове ім’я нам сіяє, як зоря 289 KB
  Активізувати та збагачувати знання дітей про життя та творчість Тараса Григоровича Шевченка; вчити учнів сприймати поезію Кобзаря серцем і душею, викликати інтерес до поезії; виховувати любов до України; спонукати учнів до вияву власних творчих здібностей та їх розвитку...
78835. Урочиста лінійка до дня народження Т.Г.Шевченка 46 KB
  Звучить пісня Реве та стогне Дніпр широкий Учитель Навесні коли тануть сніги А на рясті просяє веселка Повні сили й живої снаги Ми вшановуєм пам΄ять Шевченка. Трагічна та яскрава доля Тараса Шевченка як і доля його...
78836. Хто він, Т.Г. Шевченко? 940 KB
  Бесіда з учнями: учні висловлюють свої думки з приводу поставленого запитання Слово вчителя: Отже ми поки що тільки припускаємо що у Шевченка могли виникати думки про те як просвітити український люд світлом науки. Шевченка. Однак хто ще з такою силою пристрасті як Шевченко звеличив...
78837. Кобзарем його ми звемо… 124.5 KB
  Благословен той день і час Коли прослалась килимами Земля яку сходив Тарас Малими босими ногами Земля яку скропив Тарас Дрібними росами сльозами 9 березня 1814 р. В хаті Григорія Шевченка блиснув у вікні єдиний на все село вогник і народилася нова кріпацька душа для пана а для України...
78838. Написання твору за репродукцією картини Івана Івановича Шишкіна «Зима» 152 KB
  Формувати навички планування, самоконтролю, самоаналізу. Удосконалювати навички каліграфічного грамотного письма. Допомагати учням розкривати їх здібності, формувати пізнавальну активність, розширювати її за рамками картини, поповнювати словниковий запас. Духовно збагачувати внутрішній світ учнів.