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


 

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

53807. Оцінювання навчальних досягнень учнів. Прийоми усного опитування та письмового контролю 150 KB
  Про це свідчить хоча б той факт що контроль накладає свій відбиток на всі когнітивні процеси дитини і те що саме на одну з функцій контролю – оцінювання – орієнтовано 54 дітей сучасної школи. Без оцінювання процес засвоєння неможливий. За умови вдалої дидактикометодичної організації уроку добре продумане оцінювання може суттєво сприяти справі підвищення успішності. Серед типових помилок учителів що часто стають джерелами помилок під час оцінювання є наступні: гало ефект тенденція судити про всі аспекти поведінки людини на...
53808. Форми контролю знань на уроках інформатики 199 KB
  Для тестування широко використовую комп’ютер що дозволяє якісно змінити контроль за діяльністю учнів. Комп’ютер дозволяє перевірити всі відповіді учні більш охоче відповідають комп’ютеру і якщо отримують невисоку оцінку то мають велике бажання скоріше її виправити. Практична робота активізує пізнавальну діяльність учнів оскільки від роботи з ручкою та зошитом діти переходять до роботи з комп’ютерами. Учні оформляють свої доклади реферати за допомогою комп'ютера виконують самі малюнки схеми допомагають створювати тести посібники з...
53810. Обобщение и систематизация знаний. Контрольная работа по теме «Обыкновенные дроби» 40 KB
  Проверка домашнего задания Собрать мини-задачи 1. Постановка цели и задач мини-модуля Дети сегодня мы с вами подведем итоги изучения темы Обыкновенные дроби. Что вам больше всего понравилось на уроке метод микрофон ІІ Системно-обобщающий м м № п п Этапы мини-модуля Формы работы Вопросы упражнения задачи 1.
53811. Информационное обеспечение деятельности финансового менеджера, состав и содержание бухгалтерской отчетности для целей финансового менеджмента 31 KB
  Первый блок включает в себя законы, постановления и другие нормативные акты, положения и документы, определяющие правовую основу финансовых институтов, рынка ценных бумаг
53813. Перерізи конуса площинами. Зрізаний конус 131.5 KB
  Мета уроку: розглянути основні види перерізів конуса переріз перпендикулярний до осі; переріз що проходить через дві твірні; формування поняття зрізаного конуса. Сприйняття й усвідомлення нового матеріалу Перерізи конуса площинами слайд №1 2 Проведемо в конусі переріз площиною яка проходить через дві твірні S і SB площина перетне основу конуса по хорді B отже переріз конуса площиною яка проходить через вершину трикутник. Розв’язування задач Твірна конуса L.
53814. Музичні шедеври Родіона Щедріна 161 KB
  Мета: Познайомити студентів з творчістю Р. Щедріна показати особливості його музичної мови. Щедріна. Хід лекції 16 грудня 2012 року виповнилось 80 років з дня народження Родіона Костянтиновича Щедріна одного з найвідоміших композиторів другої половини XX століття.
53815. Святковий концерт до 8 Березня «Зустріч з зірками» 46 KB
  8-ий ученьСвята і грішна Ніжна і жагуча Цнотлива й пристрасна І сильна і слабка Ви жінка неповторна і чарівна Ви жінка вічно мудра й молода. Ви жінка жінка мати і дружина Безмежне море доброти й тепла. 10-ий учень Пянка і чуйна Ліки і отрута Земна й небесна Горда і проста Ви жінка королева берегиня Мінлива непізнанна дорога. Для вас імена вчителів художній номер 3тя учениця Воістину небесна і земна Заквітчана і терном і барвінком Свята і грішна рідна й чарівна Повіки будь благословенна жінка.