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


 

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

77531. Фреймовое представление знаний 1.36 MB
  Термин фрейм frme рамка остов каркас предложен в 1975 г. Фрейм это единица представления знаний заполненная в прошлом детали которой могут быть изменены согласно текущей ситуации т. Получается что фрейм это абстрактный образ объект или ситуация.
77532. Экспертные системы. Приобретение (извлечение) знаний 255.5 KB
  В экспертных системах знания отделены от данных и мощность ЭС обусловлена в первую очередь мощностью базы знаний и только во вторую очередь используемыми методами решения задач. системы функциональные возможности которых являются в первую очередь следствием их наращиваемой базы знаний БЗ и только во вторую очередь определяется используемыми методами принятия решения. Правильное функционирование ЭС как систем основанных на знаниях зависит от качества и количества знаний хранимых в их БЗ. Поэтому приобретение знаний для ЭС является очень...
77533. Нечеткая логика: история проблемы, практические приложения 1.22 MB
  Для этого значения степень принадлежности физической величины к терму будет равна единице а для всех остальных значений в зависимости от выбранной функции принадлежности. Здесь необходимо описать лингвистические переменные которые вы будете использовать; их функции принадлежности; описать стратегию управления посредством нечетких правил которые вы сможете объединить в единую базу правил или знаний о системе. Другими словами множество А образуют такие объекты элементы для которых указанная выше функция называемая функцией...
77534. НЕЙРОННЫЕ СИСТЕМЫ И СЕТИ. БИОЛОГИЧЕСКИЕ НЕЙРОННЫЕ СЕТИ 463 KB
  С появлением дешевых компьютеров появилась возможность использовать в этой области нейронные сети НС. Крупный толчок развитию нейрокибернетики дал американский нейрофизиолог Френк Розенблатт предложивший в 1962 году свою модель нейронной сети персептрон. Хопфилд предложил оригинальную модель нейронной сети названную его именем.
77535. Проблемно-ориентированные языки. Языки представления знаний 97.5 KB
  Стремление к эффективной программной реализации моделей представления знаний привело к разработке большого числа языков представления знаний от простых, предназначенных для решения отдельных специальных задач, до мощных универсальных.
77536. ГЕНЕТИЧЕСКИЕ АЛГОРИТМЫ И ИХ ПРИМЕНЕНИЕ 299 KB
  В животной клетке каждая молекула ДНК окружена оболочкой такое образование называется хромосомой. Основная часть хромосомы нить ДНК определяющая какие химические реакции будут происходить в данной клетке как она будет развиваться и как функции выполнять. В каждой соматической клетке человека содержится 46 хромосом. Эти 46 хромосом на самом деле 23 пары причем в каждой паре одна из хромосом получена от отца а вторая от матери.
77537. РАСПОЗНАВАНИЕ ОБРАЗОВ И СИТУАЦИЙ 89 KB
  Суть задачи распознавания установить обладают ли изучаемые объекты фиксированным конечным набором признаков позволяющим отнести и ке определенному классу. Цели науки распознавания образов: замена человеческого эксперта или сложной экспертной системы более простой системой автоматизация деятельности человека или упрощение сложных систем; построение обучающихся систем которые умеют принимать решения без указания четких правил а именно систем которые умеют сами синтезировать правила принятия решений на основе некоторого конечного...
77538. МУЛЬТИ-АГЕНТНЫЕ ИНТЕЛЛЕКТУАЛЬНЫЕ СИСТЕМЫ 96.5 KB
  Системы группового управления должны обеспечить возможность быстрой перестройки производства к изменению типа и объёма выпускаемой продукции в изменяющейся среде. Первоначально были разработаны принципы централизованного и децентрализованного группового управления сложными робототехническими системами. При децентрализованном управлении использовались распределённая группа микропроцессоров встроенных в локальные системы управления гибко программирующие поведение роботов и оборудования в соответствии с заданной в реальном времени...
77539. ИНТЕЛЛЕКТУАЛЬНЫЕ СИСТЕМЫ УПРАВЛЕНИЯ 66 KB
  Изменения во внешней среде влияют не только на сам МО но и на выбор требований к цели и качеству управления и как следствие на характер желаемых траекторий движения рабочих органов. Современные МО должны обладать возможностями выполнения функций принятия решений и управления близкими к интеллектуальным функциям человека а по скорости получения решений существенно превышать возможности человека. Эти функции реализуются с помощью современных средств вычислительной техники в интеллектуальных системах управления ИСУ.