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


 

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

72467. Древняя Русь (IX-начало XII вв.). Русские земли в период политической раздробленности (XII-первая половина XV в.) 113.5 KB
  Этногенез - это происхождение народа: начальные этапы его возникновения и его дальнейшее формирование. Славянской прародиной была территория от реки Одер на западе до Карпатских гор на востоке.
72468. Теория и методика развития речи дошкольников 228.5 KB
  Методика развития речи и обучения родному языку дошкольников так как в нашей книге некоторые вопросы рассматриваются кратко а некоторые например вопросы развития речи детей в зарубежной педагогике; подготовка детей к обучению грамоте и др.
72469. Подготовка будущего читателя в дошкольном учреждении. Особенности восприятия детьми литературных произведений 178 KB
  Они помогают формировать у детей нравственные оценки оказывают влияние на поведение ребят их взаимоотношения со сверстниками и взрослыми. По их мнению эстетическое отношение к окружающему формируется в процессе жизни детей в связи с общим ходом их психологического развития...
72470. Введение в методику развития речи 236 KB
  Компетентностная направленность изучения темы Задание: прочитайте подчеркните важные с вашей точки зрения слова словосочетания предложения абзацы. Материал темы Введение в методику развития речи изучаемой в курсе современной Теории и методики развития речи...
72471. ПОНЯТИЕ О НЕОТЛОЖНЫХ СОСТОЯНИЯХ. ПРИЧИНЫ И ФАКТОРЫ ИХ ВЫЗЫВАЮЩИЕ И ПЕРВАЯ ДОВРАЧЕБНАЯ ПОМОЩЬ 63.5 KB
  В жизни каждого человека вследствие различных причин могут произойти случаи когда его соматическое и физическое здоровье резко меняется ему становится плохо он может даже потерять сознание. При таком состоянии человеку требуется срочная помощь.
72472. Восточные славяне в древности 89 KB
  Славянские народы принадлежат к древнему индоевропейскому единству, включающему такие народы как германские, балтийские, романские, греческие, кельтские, иранские, индийские раскинувшиеся на огромном пространстве от Атлантического океана до Индийского, от Ледовитого океана до Средиземного моря.
72473. ВОЛНОВЫЕ МЕХАНИЧЕСКИЕ ПЕРЕДАЧИ 609 KB
  Генератор устроен так чтобы деформированное гибкое колесо прижималось к внутренней цилиндрической поверхности жесткого колеса с силой достаточной для передачи нагрузки за счет сил трения. При вращении генератора волна перемещений бежит по окружности гибкого колеса.
72474. Подшипники. Назначение и классификация 473.5 KB
  Подшипники служат опорами для валов и вращающихся осей. Они воспринимают радиальные и осевые нагрузки, приложенные к валу, и передают их на раму машины. При этом вал должен фиксироваться в определенном положении и вращаться вокруг заданной геометрической оси.