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


 

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

30991. ІНФОРМАТИКА та КОМП’ЮТЕРНА ТЕХНІКА 6.63 MB
  Інформаційна технологія – це людино – машинна технологія збору, обробки та передачі інформації. Це технологія, яка базується на обчислювальній техніці, швидко розвивається, охоплюючи усі види сучасної діяльності: виробництво, управління, науку, освіту, проектні розробки, торгівлю, фінансово-банківські операції, медицину, криміналістику, охорону оточуючого середовища, побут та інше.
30992. Электронная торговля 881.5 KB
  Многие крупные компании уже давно прибегают к электронному бизнесу, электронной коммерции при проведении деловых операций. Электронный обмен данными (Electronic Data Interchange, EDI) по частным компьютерным сетям начался в 60-годы XX века. Он представлял собой обмен документами в стандартном виде
30993. Характеристика кормів, технологія заготівлі та способи їх ефективного використання у годівлі поросят 191 KB
  Особливості обміну речовин у поросят на початку постнатального періоду 1.4 Розвиток внутрішніх органів у поросят за різних рівнів годівлі.5 Раціони режим і техніка годівлі поросят 1.
30995. Расчёты объёмов вентиляции по углекислоте и влажности в свинарнике 162 KB
  Комплексы по выращиванию и откорму свиней должны находиться на режиме предприятий закрытого типа. В производственную зону комплекса запрещается вход посторонним лицам и въезд на территорию транспорта, не связанного с обслуживанием комплекса. Обслуживающему персоналу разрешается вход на территорию комплекса только через санпропускник, а въезд транспорта- через дезинфекционно- промывочное помещение (дезбарьер).
30996. Какие изменения в кормах могут возникнуть вследствие влияния на них неблагоприятной погоды 85.12 KB
  Расчетная часть. При выполнении курсовой работы нужно дать ответы на такие вопросы: Определить часовой объем вентиляции. Сравнить приходную и расходную части теплового баланса и определить ∆t теплового баланса. У людей от хлеба со спорыньей бывают судороги общий паралич и часто смерть.
30997. ЭКОНОМИКА ОРГАНИЗАЦИИ 93.5 KB
  Целью выполнения курсовой работы является расширение и углубление знаний обучающихся по дисциплине «Экономика организации», овладение практическими навыками расчетов экономических показателей, характеризующих состояние организации и эффективность осуществляемой ею деятельности, формирование умения анализировать и оценивать полученные результаты.
30998. Создание эффективно работающей компьютерной сети для организации “Х” в которой находится 29 ПЭВМ 555.31 KB
  Выбор топологии сети типа кабеля и видов необходимого коммуникационного оборудования. Структурная схема вычислительной сети и описание принципов работы.Уязвимость сетис. Сетевые концентраторы также могут иметь связь друг с другом объединяя вместе подсети различных участков здания.
30999. Форма, содержание и ответственность кредитного договора 170 KB
  Предмет кредитного договора. Форма содержание и ответственность кредитного договора. Форма кредитного договора. Содержание кредитного договора. Ответственность по кредитному договору. Виды кредитного договора...