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:<
выход >


 

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

49243. Комбинированная газопаротурбинная установка 2.96 MB
  Схема представляет собой одноконтурную ТУК без промперегрева, в которую дополнительно введены элементы судового пропульсивного комплекса. В данной схеме на пропульсивной комплекс (т.е. на винт) работает ГТД и паровая турбина (ПТ1). Вторая паровая турбина (ПТ2) работает на электрогенератор и поэтому называется турбогенератором.
49246. Взаємозвязок рівня емпатії та самоставлення особистості 47.58 KB
  Вплив батьківського відношення на розвиток самоставлення у дитини. З перших днів життя дитини соціальне середовище представлена їй як система сімейної взаємодії. На перших порах саме батьки дитини є єдиними носіями соціальних відносин і єдиною ланкою яка опосередковує всі інші зв'язки дитини зі світом. Зупинюсь на особливостях взаємин батьки дитя що мають вирішальне значення в становленні особистості дитини її самооцінки і самоставлення.
49247. Програма пошуку оптимального варіанту купівлі нерухомості 2.26 MB
  Моя головна сторінка буде складатися з чотирьох блоків які реалізовуватимуться за допомогою тегу div. Тег div це так званий контейнер блок який може містити форматований текст зображення та ін Важливою особливістю блоків є їх здатність накладатися один на одного при верстці. Верстка div активно використовує CSS для гнучкого й зручного форматування елементів вебсторінок.Застосування тегу div Другий блок складатиметься з двох частин які будуть розміщенні вертикально одна відносно іншої.
49249. ПЛАНИРОВАНИЕ ТЕХНИЧЕСКОГО ОБСЛУЖИВАНИЯ ТРАКТОРОВ И АВТОМОБИЛЕЙ 79.83 KB
  ОПРЕДЕЛЕНИЕ СОСТАВА МТП И ПЛАНИРОВАНИЕ ТЕХНИЧЕСКОГО ОБСЛУЖИВАНИЯ ТРАКТОРОВ ПЛАНИРОВАНИЕ ТЕХНИЧЕСКОГО ОБСЛУЖИВАНИЯ ТРАКТОРОВ РАСЧЕТ ТРУДОЕМКОСТИ И ПРОДОЛЖИТЕЛЬНОСТИ ПРОСТОЕВ ТРАКТОРОВ НА ТО Усвоить методику и приобрести...