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


 

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

32126. la problematique de cette science est riche ce qui s’explique par le parcours assez long qu’elle a suivi avant de retrouver son autonomie 11.47 KB
  On peut essyer de controler les definitions de lobjet detude de l stylistique proposes pr des uteurs de mnuels : on ur chque fois une definition prticuliere. Les stylisticiens estimeent que cette science étudie les styles de l lngue les procédés expressifs propres ux unités linguistiques les styles des oeuvres littérires publicistes scintifiques et utres ; les prticulrités expressifs des styles fonctionnels. Guirud lobjet detudes de l stylistique est exprime comme c L tâche de l stque est de reconnître de décrire de définir et de...
32128. Le concept de style est compliqué, polyvalent et controversé 11.22 KB
  Le concept de style est compliqué polyvlent et controversé. Le style est ussi ssocie ux genres litterires dont il represente des modes dexpression necessires ; Les nciens distinguient 3 styles : le simple le tempéré et le sublime. Puis les linguistes ont élrgi le nomenclture de styles en ttribunt non seuleument ux genres littérires style lyrique épistolire épique historique etc mis ussi ux groupes sociux styles précieux populire cmpgnrd etc. ux 16 et 17 siècles on conçoit le style comme lexpression de l nture de lhomme styles...
32131. La connatation c’est tout ce que le mot suggère en plus de la dénotation 11.59 KB
  Guirud : Ce sont des ssocitions extrnotionnelles qui sns ltérer le concept le colorent . Il existe dns chque science un ensemble de termes propres elle seule болезни астрономические термины dutres mots ne semploient guere en dehors des belleslettres perir bsoudre 2 Con. Locles et ntionles évoquent les dilectes frnçis ou des emprunts job mrijun 3 Temporelles qui ssocient les mots à une époque concrète pssé ou contmporine des néologismes et rchismes télérélité glmour ou fontgne zouve. 4 Sociles évoquent un groupe...
32133. Le classement stylistique du lexique 11.75 KB
  L discription stylistique du lexique represente un gros probleme qui sexplique vnt tout pr le fit que les mots sont polysemique et peuvent se rpporter plusieurs styles. Les vrints lexico semntiques dun meme mot peuvent se rpporter ux groupes differents. Tells que les neologismeнов слово les rchisme устар слово котор замен синонимами les emprunts le lexique : prlee fmilier livresque les mots poetique. Les mots entrent dns des differents clsses.
32134. Un archaïsme est un emploi lexical ou grammatical passé de mode 11.54 KB
  La notion d’archaïsme a été jusqu’à présent beaucoup moins abordée que la néologie. Une réflexion générale autour de la problématique des genres littéraires: le choix que peuvent faire un auteur, une école ou une communauté