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


 

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

12532. Помехоустойчивость сигналов дискретной модуляции 36.41 KB
  Домашняя работа для лабораторной работы № 23 по курсу ТЭС: Помехоустойчивость сигналов дискретной модуляции Цель работы: экспериментальное исследование помехоустойчивости приема сигналов дискретной амплитудной частотной и относительной фазовой модуляции. ...
12534. Анализ и эмпирический синтез цифровых фильтров 394.5 KB
  Лабораторная работа №26 Анализ и эмпирический синтез цифровых фильтров Лабораторная работа 261 Цель работы: На персональном компьютере провести анализ нерекурсивных цифровых фильтров 1го и 2го порядка; исследовать частотные и временные характеристики фил
12535. ОБНАРУЖЕНИЕ ИМПУЛЬСНЫХ СИГНАЛОВ В ШУМЕ 70.61 KB
  Лабораторная работа №16 ОБНАРУЖЕНИЕ ИМПУЛЬСНЫХ СИГНАЛОВ В ШУМЕ Цель работы Изучение принципа порогового обнаружения двоичных сигналов механизма возникновения ошибок обнаружения метода анализа и оптимизации процесса обнаружения. Экспериментальное
12536. Процессы протекающие в оптимальном фильтре детерминированных сигналов. Оптимальная линейная фильтрация детерминированных сигналов 1023 KB
  Оптимальная линейная фильтрация детерминированных сигналов Цель работы: эксперементальное исследование процессов протекающих в оптимальном фильтре детерминированных сигналов; закрепление теоретически
12537. Создание логотипа в CorelDRAW 3.19 MB
  Лабораторная работа №1 по CorelDRAW Создание логотипа Цель лабораторной работы В процессе выполнения этой лабораторной работы вы получите практические навыки по созданию и редактированию векторных изображений. При этом вы научитесь: Рисовать...
12538. СОЗДАНИЕ РИСОВАННОЙ ИЛЛЮСТРАЦИИ РУСАЛОЧКА 1.57 MB
  ЛАБОРАТОРНАЯ РАБОТА № СОЗДАНИЕ РИСОВАННОЙ ИЛЛЮСТРАЦИИ РУСАЛОЧКА Перейдя непосредственно к созданию картинки прежде всего прорисуем лицо русалки. Для этого используем панель инструментов Corel Draw позволяющую рисовать стандартные фигуры круг прямоугольник много
12539. Кодирование данных в телекоммуникационных сетях 24.26 KB
  Домашнее задание №1 Кодирование данных в телекоммуникационных сетях 1. ВВЕДЕНИЕ1 2. ЭТАПЫ РАБОТЫ1 2.1. Формирование сообщения1 2.2. Физическое кодирование исходного сообщения2 2.3. Логическое избыточное кодирование исходного сообщения2 2.4. Скремблирование и...
12540. Методы цифрового кодирования в телекоммуникационных сетях 149.78 KB
  Сети ЭВМ и средства телекоммуникаций Методы цифрового кодирования в телекоммуникационных сетях 1. Аналоговая модуляция1 2. Спектр модулированного сигнала1 3. Цифровое кодирование2 3.1. Требования к методам цифрового кодирования2 3.2. Потенциальный код без в