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


 

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

79635. ПЕРСПЕКТИВЫ РАЗВИТИЯ ОРГАНОВ ГОСУДАРСТВЕННОГО ФИНАНСОВОГО КОНТРОЛЯ 92.5 KB
  В 2002 году на IV Конференции Ассоциации контрольно-счетных органов Российской Федерации была принята Декларация принципов деятельности контрольно-счетных органов России что заложило основу для объединения усилий всех органов государственной власти и органов местного самоуправления усилий...
79636. ПОРЯДОК И ОСОБЕННОСТИ ОФОРМЛЕНИЯ ДОГОВОРА ИПОТЕКИ ЖИЛЫХ ПОМЕЩЕНИЙ 175 KB
  Договор о залоге недвижимого имущества договор об ипотеке это договор в котором одна сторона залогодержатель являющийся кредитором по обязательству обеспеченному ипотекой имеет право получить удовлетворение своих денежных требований к должнику по этому обязательству из стоимости...
79637. АДМИНИСТРАТИВНО-ПРАВОВОЙ РЕЖИМ СТРАХОВОЙ ДЕЯТЕЛЬНОСТИ В РОССИЙСКОЙ ФЕДЕРАЦИИ 159 KB
  В правовой научной литературе вопрос о природе правового режима вообще и административно-правового режима в частности поднимался неоднократно. Российский энциклопедический словарь определяет режим как установленный порядок жизни совокупность правил мероприятий норм для достижения...
79638. О БРАЧНОМ ДОГОВОРЕ В РОССИЙСКОЙ ФЕДЕРАЦИИ 92 KB
  Принятие Семейного кодекса России поставило юридическую науку вообще и науку семейного права в частности перед необходимостью исследовать феномен брачного договора (контракта) как института семейного права, его роль и значение в регулировании имущественных семейно-брачных отношений, условия...
79639. КОНФЕДЕРАТИВНЫЕ СОЮЗЫ: ИСТОРИЧЕСКАЯ ХАРАКТЕРИСТИКА И ПРАВОВАЯ ОСНОВА 237.5 KB
  Наиболее остро устаревшие характеристики конфедерации обнаруживают свою несостоятельность в вопросе о правовых основах конфедерации, ибо решение именно этого вопроса обусловливает изучение конфедерации конкретной отраслью юридической науки.
79640. К ВОПРОСУ О ПОНЯТИИ И СОДЕРЖАНИИ ПРАВОВОГО СТАТУСА ПРОКУРАТУРЫ АДМИНИСТРАТИВНОГО ОКРУГА РОССИЙСКОЙ ФЕДЕРАЦИИ 120.5 KB
  Как правило, термин «правовой статус», часто употребляемый в литературе, применяют для характеристики того или иного субъекта правоотношений. Однако возможны случаи использования этого понятия в юридической литературе по отношению к объектам права.
79641. СЕМЬЯ, ЦЕРКОВЬ И ГОСУДАРСТВО КАК СОТРУДНИКИ ГОСПОДА БОГА 157 KB
  Государство должно учитывать традиционную и все усиливающуюся в настоящее время роль церкви в жизни своего народа и проявить особо почтительное и партнерское отношение к церкви в общем деле национально-государственного строительства.
79642. ОСОБЕННОСТИ СОВЕРШЕНСТВОВАНИЯ НОРМАТИВНО-ПРАВОВОГО РЕГУЛИРОВАНИЯ ПОРЯДКА ИСПОЛЬЗОВАНИЯ ГОСУДАРСТВЕННОЙ СОБСТВЕННОСТИ СУБЪЕКТА РОССИЙСКОЙ ФЕДЕРАЦИИ В ПРОЦЕССЕ БЮДЖЕТНОЙ ДЕЯТЕЛЬНОСТИ 99 KB
  Бюджет как экономическая категория представляет собой совокупность общественных отношений, возникающих в процессе создания, распределения и использования государственного централизованного фонда денежных средств и местных фондов денежных средств, необходимых Российской Федерации...
79643. ПРОБЛЕМЫ РАЗВИТИЯ ОРГАНИЗАЦИОННОЙ И ИНФРАСТРУКТУРНОЙ СОСТАВЛЯЮЩИХ ГОСУДАРСТВЕННО-ЧАСТНОГО ПАРТНЕРСТВА В СФЕРЕ ФИНАНСИРОВАНИЯ ОБЩЕГОСУДАРСТВЕННЫХ ПРОГРАММ И ПРЕДОСТАВЛЕНИЯ ГОСУДАРСТВЕННОЙ ПОДДЕРЖКИ ДЛЯ РАЗРАБОТКИ ПРОЕКТНОЙ ДОКУМЕНТАЦИИ ИНВЕСТИЦИОННЫХ ПРОЕК 93.5 KB
  Государственная поддержка развития организационной и инфраструктурной составляющих развития государственно-частного партнерства в сфере финансирования общегосударственных программ предоставляется для разработки проектной документации...