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


 

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

55780. Розв’язування комбінаторних задач 532.5 KB
  Мета дидактична (навчальна): формування умінь і навичок розв’язування різних видів комбінаторних задач, застосовування основних теорем комбінаторики – правил суми та добутку, закріплення відомих методів і способів на практиці, вміння застосовувати знання в комплексі;
55781. Таблиці з логічними зв’язками 1.39 MB
  комірка формула книга немає вірної відповіді Що робить Excel якщо в складеній формулі знаходиться помилка повертає 0 як значення комірки виводить повідомлення про тип помилки як значення комірки виправляє помилку у формулі видаляє формулу з помилкою Яке з посилань є абсолютним З22 R1C2 5 5 Впорядкування значень діапазону коміркок у певній послідовності називають. електронні таблиці графіки й діаграми діапазон комірок сортування й фільтрація Яких форматів числових даних не існує числовий грошовий процентний округлений Логічна функція...
55782. Методична розробка з інженерної графіки, збірка завдань та рекомендацій до виконання розрахунково-графічних завдань 4.87 MB
  Мета розробки - надання допомоги студентам в освоєнні теоретичних і практичних знань, графічних умінь і навиків, активізації процесу і пізнавального інтересу. Розвитку просторових уявлень, мислення і творчих здібностей.
55783. Поняття про мультимедійні дані. Формати аудіо- та відеофайлів. Мультимедійні програвачі 85 KB
  Мета: навчитися: додавати до графічних зображень та тексту слайдів анімаційні ефекти, що супроводжуються звуком; вставляти до слайду презентації звукові об’єкти і настроювати їх параметри.
55784. Музично-виконавський розвиток учня-піаніста в процесі роботи над творами малої форми в 4 класі ДМШ 144.5 KB
  Педагог оголошує тему уроку план уроку в який входять такі твори: П. Педагог. Кілька пєс з цих альбомів вже були в твоєму репертуарі Лєра багато ти чула в концертах Дитячої Філармонії школи а також у записах відомих виконавцівпедагогів. Педагог.
55785. Омбудсмени року 384.5 KB
  Ми не просто розпочати нашу програму з визначення права. Справа в тому що так ми наблизились до першого нашого конкурсу яке і має таку назву Знавці права.
55786. Ой, не вітер в полі грає, не орел літає – ото Сірко з товариством по степу гуляє! 61.5 KB
  Мета: увіковічення та вшанування визначного військово-політичного діяча козацького періоду Івана Сірка; популяризація козацьких звичаїв та традицій серед учнівської...
55787. ПОЛІТИКА ВЛАДИ У ЦАРИНІ КУЛЬТУРИ В 1921-1928 рр. УКРАЇНІЗАЦІЯ (КОРЕНІЗАЦІЯ) 311 KB
  Мета: методична – удосконалення методики проведення лекціїдіалогу та активізації пізнавальної діяльності студентів шляхом використання групових форм роботи...
55788. Які правила визначають гармонію людини із собою та найближчим оточенням 245 KB
  Стежка Правдивості Команди слухають визначення понять Додаток 3 які вивчали на попередніх уроках етики потім радяться 30 секунд і записують кожне слово на окремому аркуші паперу.