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


 

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

12405. Компоненты отображения иерархических данных 165 KB
  Лабораторная работа № 10 Компоненты отображения иерархических данных Цель лабораторной работы состоит в изучении методики работы с компонентами отображения произвольных иерархических данных. Общие сведения о компонентах В библиотеке VCL для отображения иерар...
12406. Принятие решений в условиях неопределенности. Критерий Лапласа 305 KB
  Принятие решений в условиях неопределенности Теория статистических решений может быть истолкована как теория поиска оптимального недетерминированного поведения в условиях неопределенности. Согласно А.Вальду поведение считается оптимальным если оно минимизирует...
12407. Измерение длины световой волны с помощью прозрачной дифракционной решетки 98 KB
  Отчёт по лабораторной работе По дисциплине: Физика. Тема: Измерение длины световой волны с помощью прозрачной дифракционной решетки Общие теоретические сведения: Интерференция явление перераспределения волны в результате наложения когерентных волн...
12408. Контролер станочных и слесарных работ 156.5 KB
  Для приобретения квалификации контролера станочных и слесарных работ необходимо: технологию сборочных работ; технические условия на приемку деталей и проведения испытаний операций, механической и слесарной обработки...
12409. Исследование свободных электрических затухающих колебаний 234.5 KB
  Отчет. К лабораторной работе 5.2. Исследование свободных электрических затухающих колебаний. Цель работы: Исследование закономерностей свободных электрических незатухающих колебаний в последовательном колебательном контуре определение их физических характерис
12410. Исследование вынужденных колебаний в последовательном контуре 80.5 KB
  Отчёт по лабораторной работе 53. Исследование вынужденных колебаний в последовательном контуре. Цель работы: исследовать зависимость резонансной частоты и вида резонансной кривой от параметров контура. Расчёт погрешностей
12411. Технологический процесс приготовления блюд: Рассольник Ленинградский; Котлета натуральная из филе птицы, со сложным гарниром; Торт Прага 3.25 MB
  Для приправы практически всех блюд используется соевый соус, который является одним из основных ингредиентов китайской кухниэто экстракт из соевых бобов, который практически ничем не заменяется. В европейских условиях этот соус готовят из местной сои. Кроме этого широко используется вей-су - глютаминат натрия...
12412. Исследование волны в натянутом шнуре 42 KB
  Отчёт по лабораторной работе 6. Исследование волны в натянутом шнуре. Цель работы: Исследование стоячих волн в горизонтальном натянутом шнуре. Измерение частоты источника методом стоячих волн. Рабочие формулы Пример расчета полной абсолютной погр
12413. Исследование резонанса в металлической струне 98.5 KB
  Отчет к работе № 55 Исследование резонанса в металлической струне II. РАБОЧАЯ ФОРМУЛА III.КОНСТАНТЫ КОСВЕННЫХ ИЗМЕРЕНИЙ Uвых. ген.=5В IV. ТАБЛИЦЫ ИЗМЕРЕНИЙ N № измерения 1...