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


 

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

81989. А вже весна, а вже красна… 80 KB
  Показати, як поети і письменники засобами художнього слова розкривають багатство і красу навколишнього світу; розвивати навички виразного читання, формувати уміння робити посильні висновки з прочитаного, побаченого, почутого; збагачувати лексичний словник учнів...
81990. Бринить струною гілочка весни. (Весна у природі) 61.5 KB
  Закріплення елементарних уявлень про найхарактерніші ознаки весни в живій і неживій природі, які можна виявити в процесі спостережень, а саме: з пробудженням рослин, з поведінкою перелітних птахів; показати, як зміни в неживій природі впливають на живу природу; поповнювати знання учнів...
81991. Зігріємо землю своєю любов’ю, для наших нащадків її збережемо 231 KB
  Мета. Поглиблювати знання учнів про природу, її красу та багатства, сприяти розумінню необхідності захищати і берегти навколишнє середовище, виховувати любов і повагу до рідної землі, трепетне ставлення до всього живого на ній.
81992. РАЗРАБОТКА СИСТЕМЫ БЮДЖЕТИРОВАНИЯ НА БАЗЕ 1С:ПРЕДПРИЯТИЕ 8.0: ОБМЕН ИНФОРМАЦИЕЙ С БУХГАЛТЕРСКОЙ КОНФИГУРАЦИЕЙ, РАЗРАБОТКА БИЗНЕС-ПРОЦЕССОВ 888 KB
  Созданы обработки для обмена данными между разрабатываемой конфигураций и стандартной конфигурацией 1С:Бухгалтерия, разработаны бизнес-процессы, необходимые для формирования бюджета.
81993. Стежинами рідного міста 155 KB
  Познайомити учнів з головними історичними подіями в процесі розвитку рідного міста. Розвивати зв’язне мовлення, пізнавальний інтерес, уміння робити висновки. Виховувати патріотичні почуття, бажання набувати нові знання.
81994. Дзеркало людської душі 46.51 KB
  На початку виховної години для розвитку креативного мислення проводиться мозковий штурм Вихователь пропонує дітям відгадати що в неї в подарунковому пакеті пропонуючи підказки з історії виникнення дзеркала його форми і де воно зустрічається в літературі.
81995. ЛЮБОВ – ЦЕ ДАР. І БОГ САМ ВИБИРА, ХТО ЗАСЛУЖИВ ОЦЕ ПІЗНАТИ ДИВО 42.5 KB
  Мета: поспілкуватися з учнями про кохання, про те, що вважається природним і що є небажаним у взаєминах молоді; зорієнтувати учнів на толерантне ставлення до вираження почуттів протилежними статями; допомогти учням розібратися у собі, підготувати до майбутнього сімейного життя.
81996. Виховна година «Злочин і покарання» 35.5 KB
  Мета: запобігати шкідливим звичкам, які негативно впливають на здоров’я підлітків; формувати вміння і навички учнів щодо власної безпеки, розуміння відповідальності за власні вчинки та їх наслідки; виховувати в учнів бажання зберегти власне здоров’я.
81997. Прийди до серця, Україно, благослови добром мене… 45.5 KB
  Мета: виховувати почуття патріотизму, національної гордості, любові до рідного краю, розуміння своєї причетності до всіх подій, які відбувалися в Україні; формувати переконаність у нетлінності духовних скарбів народу.