Optimizarea Buclelor Program

Când optimizăm performanţele programului cel mai bun beneficiu va veni de la optimizarea regiunilor din program care solicită cel mai mult timp - regiunile repetitive din program. Acestea corespund sau iteraţiilor buclelor ori procedurilor recursive. Aici ne concentrăm pe un pachet de şiretlicuri pe care le vom utiliza pentru optimizarea buclei. Pentru cea mai mare parte ne vom concentra pe bucle numărabile, unde o numărare corectă poate fi determinată fără execuţia buclei, opuse buclei while.

Multe prezentări ale metodelor restructurării buclei se bazează pe legalitate şi beneficiu al performanţelor transformării ori optimizării. Beneficiile transformării nu pot fi determinate până când arhitectura computerului ţintă(computerul pentru care se va optimiza) este cunoscută; vom discuta beneficiile transformărilor pentru felurite arhitecturi. De asemenea, legalitatea transformării depinde de semantica maşinii şi a limbajului ţintă. Multe maşini au în componenţă unul sau mai multe procesoare secvenţiale conectate într-un anumit mod; din acest motiv, ne vom concentra pe compilarea pentru colecţia de maşini secvenţiale.

Regula noastră generală pentru o transformare corectă este simplă. Dacă vom avea succes în capturarea totală a relaţiilor de dependenţă esenţiale din program în graf-urle dependente de datele şi dependenţă a controlului programului, atunci vom putea aplica orice transformare atât timp cât programul transformat păstrează fiecare relaţie de dependenţă. Pe un uniprocesor secvenţial, o relaţie de dependenţă este păstrată prin executarea sursei de dependenţă înainte de dependenţa ţintă. Pe un multiprocesor, există mai multe căi pentru a păstra relaţia de dependenţă, atât prin sheduling ori una din formele variate ale sincronizării. În timp ce programul original (prin definiţie) satisface toate relaţiile dependente, asta nu înseamnă că programul poate fi întotdeauna compilat fără transformare. Ne aducem aminte că chiar şi o sursă secvenţială de limbaj (ca FORTRAN 90) poate include construcţii paralele (ca atribuirea de tabluouri, sau intrucţiunea forall). Executarea acestor construcţii pe o maţină secvenţială necesită analiză şi poate transformare pentru a satisface toate relaţiile de dependentă .

A)Transformari simple

1. Reordonarea instrucţiuniilor

Prima transformare prezentată aici este reordonarea instrucţiuniilor. Reordonarea poate fi făcută la orice granulaţie, operaţie maşină, intrucţiune, secvenţă de instrucţiuni, ş.a.m.d. Aici considerăm reordonarea la nivelul instrucţiuniilor şi a granulaţiei buclei cu un graf de control a fluxului aciclic(CFG=Control Flow Graph); un nod în CFG sau în graful de dependenţă este sau o simpla intrucţiune sau o buclă întreagă. Pentru că CFG este aciclic, graful de dependenţa este de asemenea aciclic. Reordonarea poate fi aplicată recursiv înăuntrul corpului unei buclei interioare, tratând fiecare instrucţiune simplă sau buclă interioară ca şi un nod. Reamintim că o transformare este legală atât timp cât relaţiile de dependentă sunt păstrate, orice fel de topologie a graf-ului de dependenţe este o ordonare corectă de instrucţiuni.