29360

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

Доклад

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

Рассмотрим возможные преобразования над цикличными участками покажем на примере констрии цикла с заданным количеством повторения.В языке Паскаль такая циклическая конструкция имеет следующий вид: for i: =a to b dobeginтело циклаend;В бейсике: for i =a to b step Sтело циклаnext iв таких конструкциях а и b – границы изменения переменной циклаНад подобными конструкциями выполняются следующие оптимизационные преобразования:1. вынесение из тела цикла операций операций которые не измен. в теле цикла;2.

Английский

2013-08-21

28 KB

0 чел.

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

Рассмотрим возможные преобразования, над цикличными участками, покажем на примере констрии цикла с заданным количеством повторения.
В языке Паскаль такая циклическая конструкция имеет следующий вид:

for i: =a to b do
begin
тело цикла
end;

В бейсике:

for i =a to b step S
тело цикла
next i

(в таких конструкциях а и b – границы изменения переменной цикла)
Над подобными конструкциями выполняются следующие оптимизационные преобразования:
1. вынесение из тела цикла операций, операций которые не измен. в теле цикла;
2. замена слож. операций в циклах на более прост, более быстрые. Умножение в теле цикла заменяется сложением.
Покажем, идею выполнения этих преобразований:

for i=a to b steps
операторы
x=2*j
y=i*K
операторы
next i
Если переменная j не зависит от i , то вычисление значения х можно вынести из цикла: 

x=2*j
for i =a to b step s
операторы
y = i *K
операторы
next i
Рассмотрим, как изменяется значение переменной y при изменении переменной. цикла. 

i=a y=a+k
i= a=s y= (a+s) *K=a*k+ s+k
i= a+s+s y=a*k+s+k+s*k
Отсюда можно заметить, что умножение в теле цикла можно заменить опер. Сложения с накопл. рез-те. При входе в тело цикла y =a*K и для кажд. опер. y увеличивается на шаг Sy: y=y+Sy, равный Sy= s*K
После замены умножения на сложение такая цикличность конструкция примет следующий вид:

х=2*j
y=a*k
sy= s*k
for i=a to b step s
операторы
операторы
y=y+sy
next i
Замена умножения сложением в теле цикла позволит существенно сократить время вычисления цикличности участка.В трансляторах указанное преобразование выполняется над циклическими конструкциями, представленными во внутренней форме.
Для преобразования во внутреннюю форму циклические участки представляются в след. виде: 
UNIT: i=a
TEST: <if i>b then go to OUER>
LOOP: <тело цикла>
INCR: i=i+s
<
go to TEST>
OVER:<выход из цикла>
Такую конструкцию можно представить в тетрадной форме:

UNIT: ( =, а, ,i) (1)
TEST: (- , i, b,
Т1) (2)
(JMP, <k+4>,T1, ) (3)
LOOP: ( ) (4)
…………
( ) (k)
INCR: (+,i , s, T2) (k+1)
(= ,
T2, , i) (k+2)
(
JM, <2>, , ) (k+3)
OVER: ( ) (k+4)
После оптимизации циклическая конструкция изменится следующим образом:

UNIT: i=a
<
начало операции>
TEST: <if i>b then go to OUER>
LOOP: <
изм. тело цикла>
INCR: i=i+s
<
операция приращения>
<go to TEST>
OVER:<
выход >


 

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

18688. Эталонные (базисные) стратегии развития 14.19 KB
  Эталонные базисные стратегии развития. Эталонными базисными стратегиями развития бизнеса обычно называют наиболее распространенные выверенные практикой и широко освещенные в литературе стратегии. Они отражают 4 различных подхода к росту фирмы и связаны с изменени
18689. Информация для инвестора в интернете 14.32 KB
  Информация для инвестора в интернете. Связи с инвесторами или IR акроним от англ. Investor Relations сфера деятельности организации находящаяся на пересечении финансов коммуникационной политики маркетинга и права имеющая целью построение максимально эффективной двусторо...
18690. Иерархические модели данных 15.32 KB
  Иерархические модели данных. Иерархическая структура представляет совокупность элементов связанных между собой по определенным правилам. Объекты связанные иерархическими отношениями образуют ориентированный граф. основным понятиям: уровень элемент узел связь. У...
18691. Автоматизированное рабочее место 15.32 KB
  Автоматизированное рабочее место. Для реализации идеи распределенного управления потребовалось создание для каждого уровня управления и каждой предметной области автоматизированных рабочих мест на базе профессиональных персональных компьютеров. Например в с...
18692. Механистические организационные структуры 26.63 KB
  Механистические организационные структуры. Способность организации быстро реагировать на внешние угрозы и сохранять положительный баланс между входом и выходом зависит от ее структуры. Структура организации это совокупность предписанных ролей и взаимоотноше
18693. Схематичная конструкция жесткого диска (понятия цилиндр, дорожка, поверхность, сектор) 67.39 KB
  Схематичная конструкция жесткого диска понятия цилиндр дорожка поверхность сектор Говоря о магнитных дисках и жестких и гибких нельзя не сказать об их внутренней структуре. Ее составляют дорожки цилиндры и сектора. Дорожки tracks это концентрические окружности п
18694. Учет труда и заработной платы, регистры учета, среднемесячная заработная плата 16.41 KB
  Учет труда и заработной платы регистры учета среднемесячная заработная плата. Заработная плата это вознаграждение за труд в зависимости от квалификации работника сложности количества качества и условий выполняемой работы а также выплаты компенсационного и сти...
18695. Применение CASE-технологий при создании информационной системы 13.87 KB
  Применение CASEтехнологий при создании информационной системы. CASEтехнология представляет собой совокупность методологий анализа проектирования разработки и сопровождения сложных систем и поддерживается комплексом взаимоувязанных средств автоматизации. CASEтехноло...
18696. Анализ средств управления пакетом 16.36 KB
  Анализ средств управления пакетом. Система управления пакетами набор программного обеспечения позволяющего управлять процессом установки удаления настройки и обновления различных компонентов программного обеспечения. Системы управления пакетами активно исполь...