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


 

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

30017. Особенности приготовления блюд русской кухни 1022.86 KB
  Русская кухня давно пользуется широкой известностью во всем мире. Это проявляется как в прямом проникновении в международную ресторанную кухню исконно русских пищевых продуктов
30018. Учет труда и расчетов с персоналом по оплате труда 177.69 KB
  Методика учета расчетов с персоналом по оплате труда 14 1. Структура оплаты труда работников предприятия 19 2.2 Оценка состояния учета расчетов с персоналом по оплате труда 29 2.
30019. Технические условия на изготовление сварочной конструкции 490.35 KB
  Закономерности сварки плавлением излагаются в тесной связи со спецификой отдельных ее видов. Наибольшее внимание уделено дуговой сварке занимающей ведущее положение по сравнению с другими видами сварки. Применение сварки способствует совершенствованию машиностроения и развитию таких отраслей техники как ракетостроение атомная энергетика радиоэлектроника и др.
30021. «Богатырь русского леса. Шишкин И.И.» (мультимедиа программа) 995 KB
  Картина №1. Афонасовский как прозывается он в наших краях под Елабугой Картина эта имела успех у публики. А для меня эта картина стала первой где многолетние свои наблюдения природы пытался я претворить в единый образ русского леса образ родины. Картина №2.
30023. Практические рекомендации по развитию интернет коммуникаций Фонда венчурных инвестиций ЧР www.e-birzha.cap.ru 1.39 MB
  Специфика корпоративного сайта как PRинструмента. Анализ официального сайта Фонда венчурных инвестиций ЧР www. История создания и ключевые требования к содержанию сайта. Анализ существующего состояния сайта www.
30024. Опытно - экспериментальная работа по формированию умений письма и письменной речи по средствам информационно – коммуникационных технологий 121.3 KB
  Информационнокоммуникационные технологии заняли прочное место в процессе обучения иностранному языку. Практика показывает что информационнокоммуникационные технологии имеют немало преимуществ перед традиционными методами обучения. Среди них можно выделить интенсификацию самостоятельной работы учащихся повышение познавательной активности и индивидуализацию обучения.
30025. Моделирование стрижек 61.22 KB
  Стрижка волос довольно сложная и серьезная операция которая требует предельного внимания и собранности. Укладка Волос это изменение структуры волоса на непродолжительное время чаще всего от мытья до мытья. В моде светлый цвет волос.