29359

Машинно-независимая оптимизация линейных участков программ

Доклад

Информатика, кибернетика и программирование

Покажем простейшие преобразования линейных и циклических участков для тетрадной формы программ:Машиннонезависимая оптимизация линейных участков программЛинейным участком программы называется последовательность операцийкоманд которая не содержит условных переходов возможно кроме последней операции. Для оптимизации линейных участков в простейшем случае используется два основных преобразования:1. В списке тетрад выделит границы участков включающих вычисления выражений по операторам присвоения;2.

Английский

2013-08-21

26.5 KB

3 чел.

25) Машинно-независимая оптимизация линейных участков программ.

При выполнении такой оптимизации наиболее часто преобразуются линейные и циклические участки программ. Самой удобной формой представления программы при машинно-независимой оптимизации является тетрадная форма.
Покажем простейшие 
преобразования линейных и циклических участков для тетрадной формы программ:
Машинно-независимая оптимизация линейных участков программ
Линейным участком программы называется последовательность операций(команд), которая не содержит условных переходов, возможно кроме последней операции.
Для линейного участка программы последовательность выполняемых действий не зависит от обрабатываемых данных. Для оптимизации линейных участков в простейшем случае используется два основных преобразования:
1. свертка, т.е. выполнение операций для которых операнды известны во время трансляции ( напр. константы)
2. исключение избыточных операций за счет определения общих подвыражений.
Рассмотрим примеры алгоритмлв, реализ-х эти преобразования над арифмитическими выражениями, заданными в тетрадной форме.
Алгоритм свертки
1. В списке тетрад найти такую тетраду, все операнды которой заданы константами;
2. Выполнить операцию, заданную этой тетрадой и создать новую константу; (поместить ее в таблицу констант)
3. Исключить найденную тетраду из списка, а все ссылки на ее результат заменить обращением к новой константе;
4. Повторять шаги с 1-го по 3-ий, пока в списке тетрад появятся изменения.
Алгоритм исключения избыточных операций
1. В списке тетрад выделит границы участков включающих вычисления выражений (по операторам присвоения);
2. для всех тетрад, задающих коммутативные операции упорядочить операнды в соответствии с некоторым правилом;(коммутативн. называются операции результат выполнения которых не изменяется при перестоновке операндов)
3. в каждом выражении найти идентичные тройки вида:
(<оператор> , <операнд1> , <операнд2>). Исключить из списка все соответствующие тетрады, кроме первой и исправить ссылки на результат;
4. повторять шаги 2 и 3 до тех пор, пока появляются изменения в списке тетрад.
Избыточные операции обычно появляются в неочевидных ситуациях. В частности при работе с многомерными массивами.
Любой многомерный массив в конечном итоге преобразуется в одномерный. В послед-ть зарезервированных ячеек памяти. Это неизбежно, т.к. адресация в памяти линейна. Поэтому при использовании 2-х или более индексов обращение к любому элементу предпологает «скрытое» вычисление его номера в этой последовательности решений.


 

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

44646. Собственные и нарицательные имена существительные 21.1 KB
  Орг момент Отгадаем ребус: отец Какие орфограммы встречаются в этом слове Можем ли мы ее проверить Значит это слово словарное. на какие вопросы оно отвечает на какие две большие группы мы можем поделить и. сущ Как отличить Еще на какие чем они отличаются Какие группы слов мы пишем с заглавной буквы фронтальный опрос и. Прочитай1 ученик устно какие группы слов могут быть собственными.
44648. Имена существительные - названия явлений природы и качеств людей 20.63 KB
  Имена существительные названия явлений природы и качеств людей. Тип урока: комбинированный ФОУД: фронтальная индивидуальная групповая Дидактическая цель: создать условия для систематизации знаний учащихся по теме Имя существительное Задачи: 1.Образовательные: познакомиться с лексическим значением групп существительных; находить отличительные особенности групп; учиться использовать их в своей речи; 2. О какой части речи это стихотворение Что такое имя существительное им.
44649. Единственное и множественное число имен существительных 19.43 KB
  Образовательные: систематизировать и углубить знания об именах существительных единственного и множественного числа; учить находить имена существительные единственного и множественно числа в тексте и подбирать их самостоятельно; учить классифицировать имена существительные единственного и множественного числа; отрабатывать умения изменять имена существительные по числам. Даны существительные в единственном числе преобразовать в существительные множественного числа. Даны существительные во множественном числе преобразовать в...
44650. Единственное и множественное число имен существительных 19.98 KB
  Минутка чистописания: пропишем ее три раза 1 человек у доски 1 букву с комментированием пропишем соединение буквы т с буквой о в тетради 3 раза1 человек на доске с комментированием запишем все словарное слово в н. мн ед ч по смыслу умения находить слова мн ед ч и правильно определят чила имен сущ. доске записаны слова сосны с_сна хлеба хле_ грибы гри_ травы тр_ва горы г_ра Что заметили По какому признаку слова записаны в два столбика Запишем первое слово из второго столбика1ч к доске ост. Как мы ее можем проверить С...
44653. Контроль знаний по теме: «Имя существительное» 19.06 KB
  Образовательные: выявить умение находить имена существительные и ставить к ним вопросы выявить уровень усвоения понятия одушевленные и неодушевленные имена существительные умение ставить вопросы; проверить умения отличать имена существительные нарицательные от собственных; проверить умение классифицировать имена существительные на имена существительные единственного и множественного числа; 2.Спиши имена существительные перед каждым словом поставь вопрос и определи одушевленное это имя существительное или неодушевленное.Спиши...