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


 

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

11270. Определение коэффициента вязкости жидкости методом стокса 315 KB
  Определение коэффициента вязкости жидкости методом стокса Указания содержат краткое описание явления внутреннего трения и метода определения коэффициента вязкости динамического жидкости. Методические указания предназначены для студентов инженерных специ
11271. Определение скорости снаряда методом крутильных колебаний 1.37 MB
  Определение скорости снаряда методом крутильных колебаний Указания содержат краткое изложение устройства и принципа действия крутильного баллистического маятника. Методические указания предназначены для выполнения лабораторной работы студентами все
11272. Определение моментов инерции тел на приборе Обербека 255.5 KB
  Определение моментов инерции тел на приборе Обербека Методические указания к лабораторной работе № 10А по физике Раздел Механика Указания содержат краткое описание рабочей установки и методики определения момента инерции на приборе Обе
11273. ОПРЕДЕЛЕНИЕ ЗАВИСИМОСТИ МОМЕНТА ИНЕРЦИИ СИСТЕМЫ ОТ РАСПРЕДЕЛЕНИЯ МАССЫ ОТНОСИТЕЛЬНО ОСИ ВРАЩЕНИЯ 235 KB
  ОПРЕДЕЛЕНИЕ ЗАВИСИМОСТИ МОМЕНТА ИНЕРЦИИ СИСТЕМЫ ОТ РАСПРЕДЕЛЕНИЯ МАССЫ ОТНОСИТЕЛЬНО ОСИ ВРАЩЕНИЯ Методические указания к лабораторной работе № 10Б по физике Раздел Механика Указания содержат краткое описание рабочей установки и методики ...
11274. Определение момента сил трения и момента инерции махового колеса 266 KB
  Определение момента сил трения и момента инерции махового колеса. Указания содержат краткое описание рабочей установки и методики определения момента инерции махового колеса. Методические указания предназначены для студентов инженерных специальностей...
11275. Определение момента инерции твердых тел методом трифилярного подвеса 235 KB
  Определение момента инерции твердых тел методом трифилярного подвеса Указания содержат описание рабочей установки и методики определения момента инерции твердых тел методом трифилярного подвеса. Методические указания предназначены для студентов инжене
11276. Изучение динамики вращательного движения с помощью маятника максвелла 231 KB
  Изучение динамики вращательного движения с помощью маятника максвелла Указания содержат краткое описание рабочей установки и методики определения момента инерции с помощью маятника Максвелла. Методические указания предназначены для студентов инженерных спе...
11277. Определение коэффициентов трения качения и трения скольжения с помощью наклонного маятника 7.79 MB
  Лабораторная работа Определение коэффициентов трения качения и трения скольжения с помощью наклонного маятника Цель работы: определение коэффициентов трения качения и трения скольжения. Оборудование: измерительная установка секу
11278. Определение ускорения свободного падения на машине Атвуда 258 KB
  Определение ускорения свободного падения на машине Атвуда. Указания содержат краткое описание рабочей установки и методику определения ускорения свободного падения с помощью машины Атвуда. Методические указания предназначены для студентов инженерных специально