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


 

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

80422. Развитие интеллектуальных умений при обучении математике (на примере умений анализировать, синтезировать, алгоритмизировать) 526 KB
  Чтобы учащиеся могли глубже осознать междисциплинарные связи, понять возможность переноса результатов с одного учебного предмета на другой, у них не должно создаваться впечатления, будто каждый предмет призван решать свои, отдельные от других дисциплин, задачи.
80423. Разработка алгоритма изготовления детали «Втулка-регулирующая» 862 KB
  Простейшие токарные станки были известны еще в глубокой древности. Эти станки были весьма примитивны по конструкции: заготовка вращалась от ножного привода, а режущий инструмент приходилось держать в руках. Работа на таких станках была непроизводительной, утомительной и неточной.
80424. Проектирование высокоскоростной корпоративной сети на базе технологии СЦИ 2.27 MB
  Данная дипломная работа заключается в разработке схемы проектирования и технической реализации корпоративной сети связи, на основе технологии СЦИ, с целью создания каналов связи высокого качества между 11-ми объектами, расположенными на территории Волгоградской области.
80425. Разработка финансовой модели проекта птичника на ЗАО «Агрофирма Боровская» 859 KB
  Необходимость существенного повышения уровня и качества жизни населения выдвигает в качестве неотложной задачи ускорение формирования нового агропромышленного производства на основе модернизации и ускоренного развития инновационных процессов, совокупности последовательно осуществляемых...
80426. СОЗДАНИЕ МОБИЛЬНОГО ИНФОРМАЦИОННОГО РЕСУРСА 143 KB
  В рамках данной дипломной работы будет описан процесс создания мобильной версии информационного ресурса Яковлевской центральной детской библиотеки в городе Строитель ориентированной в частности на учащихся средних школ Яковлевского района Белгородской области.
80427. Принцип разделения властей и его реализация к Конституции Российской федерации 1993-го года 127 KB
  Суть данного принципа заключается в том, чтобы не допустить узурпации власти в руках главы одной ветви власти, чтобы размеренно, путём системы сдержек и противовесов, одна ветвь власти влияла на другую, контролировала и выявляла недостатки в управлении, взаимодействовала, чтобы один орган не оказался таком положении...
80429. Финансово-правовое стимулирование инвестиционной деятельности в субъекте Российской Федерации (на примере Томской области) 43.13 KB
  Как известно, рыночная экономика функционирует по принципу естественного отбора. Но уровень развития производственной, иной хозяйственной деятельности на соответствующей территории едва ли можно назвать исключительно частным делом – ведь от этого зависит уровень жизни проживающих в этой местности граждан.
80430. Компетенция Конституционных ( уставных ) судов Субъектов РФ 111 KB
  Конституции Российской Федерации на основании этих положений разводиться компетенциальный вопрос но вопрос о компетенции и юрисдикции конституционных уставных судов в РФ с судами общей юрисдикцией а именно с публичным производством представляется довольно интересным применительно...