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


 

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

43243. Проектирование одноосного гироскопического стабилизатора на безе чувствительного элемента заданного типа 1.98 MB
  Качка основания Частота вибраций Гц Угловое движение Расположение оси стабилизации Частота Гц Амплитуда град. 2 частотами и амплитудами происходит вокруг осей отмеченных символом x; ось стабилизации расположена параллельно оси указанной в табл. ВВЕДЕНИЕ Системы гироскопической стабилизации различных видов применяются в навигационных устройствах и системах управления кораблей и ЛА а также в системах ориентации антенн телескопов и других приборов установленных на движущихся объектах.
43244. Процесс синхронизации телевизора LG и компьютера 2.36 MB
  Данное напряжение получается в схеме платы сопряжения из питающего напряжения 5Вольт логических элементов микросхем. Сторона элементов В таблице 4 отразим перечень элементов используемых в разработанной плате сопряжения ПК с телевизором. Таблица 4 Перечень элементов схемы электрической принципиальной сопряжения ПК с телевизором Поз. РАСЧЕТ НАДЕЖНОСТИ Расчет надежности чаще всего сводится к определению числовых значений наработки на отказ Т0 и вероятности безотказной работы Рt по известным интенсивностям отказов элементов.
43245. Расчёт ПОТС и ЦРБ 605.5 KB
  Техническая служба ГПС включает систему управленческих, производственно-технических и оперативных подразделений, организуемых в целях технического и материального обеспечения оперативно-служебной и хозяйственной деятельности пожарной охраны.
43246. Проектирование технологического процесса изготовления детали типа «корпус редуктора» в условиях крупносерийного производства 1.25 MB
  Курсовой проект является большой самостоятельной работой будущего технолога, направленной на решение конкретных задач в области совершенствования технологии, организации производства и улучшение технико-экономических показателей работы участка. Наряду с этим курсовое проектирование закрепляет умение студента пользоваться справочной литературой, ГОСТами, таблицами, номограммами, нормами и расценками умело, сочетая справочные данные с теоретическими знаниями, полученными в процессе изучения курса. Проект закрепляет, углубляет и обобщает знания, полученные студентами во время лекционных и практических знаний.
43247. Моделирование процесса функционирования ВЦ при условии, что обработать необходимо 100 заданий 2.02 MB
  После обработки на процессоре как коротких так и длинных заданий производится вывод результатов на печать в течение 2 1 мин. Смоделировать процесс функционирования ВЦ при условии что обработать необходимо 100 заданий. Определить число коротких и длинных заданий ожидающих обработки а также число обработанных коротких заданий и коэффициент загрузки процессора.
43248. Проектирование стальной промежуточной опоры с исходными данными для проектирования 902.5 KB
  Характеристика провода. Нахождение исходного режима работы провода. Общая характеристика воздушной линии электропередач Воздушная линия электропередачи ВЛ служит для передачи и распределения электрической энергии по проводам расположенным на открытом воздухе и прикрепленным к опорам или кронштейнам и стойкам на инженерных сооружениях при помощи изоляторов и арматуры. Основными элементами воздушных линий являются провода изоляторы линейная арматура опоры и фундаменты.
43249. РОЗРАХУНОК ХАРАКТЕРИСТИК РАДІОТЕХНІЧНИХ СИГНАЛІВ 226.5 KB
  Розрахунок параметрів первинного аналогового сигналу.Розрахунок параметрів сигналу аналогової модуляції. Розрахунок параметрів первинного цифрового сигналу. Розрахунок параметрів сигналу дискретної модуляції.
43250. Доходи Державного бюджету України 185 KB
  Характеристика доходів державного бюджету. Соціальноекономічна суть призначення і роль доходів Державного бюджету України. Джерела надходжень державного бюджету.Аналіз та склад доходів бюджету за перше півріччя 20092010рр. Одержавлення національного доходу здійснюється державою різними методами. Основним методами, які використовуються органами державної влади для перерозподілу національного доходу та утворення бюджетних доходів, являються податки, державний кредит та емісія грошей.
43251. Полевые транзисторы в интегральных схемах 323.5 KB
  Чем больше обратное напряжение тем глубже обедненный слой и тем соответственно меньше толщина канала w. Таким образом меняя обратное напряжение на затворе можно менять поперечное сечение а значит и сопротивление канала. При наличии напряжения на стоке будет меняться ток канала т. Определим зависимость толщины и сопротивления канала от управляющего напряжения на затворе при нулевом напряжении на стоке.