FACULTY OF INFORMATICS Masaryk University IA039: Architektura superpočítačů a náročné výpočty Překladače Luděk Matýska Jaro 2020 Luděk Matýska • Překladače • Jaro 2020 1/31 FACULTY OF INFORMATICS Masaryk University Opakování - RICS procesory ■ Limitovaný počet instrukcí, jednotná déLka ■ jednoduché adresní módy, Load/store, hodně registrů ■ delay branches, brach prediction, out-of-order execution ■ superskaLární (MIPS - 2xFPU, 2xALU, adresace) ■ superpipeLine (ANDES) ■ vyrovnávací paměti Luděk Matýska • Překladače • Jaro 2020 2/31 FACULTY OF INFORMATICS Masaryk University Optimalizující překladač ■ překlad do mezijazyka ■ optimalizace ■ meziprocedurální analýza ■ optimalizace cyklů ■ globální optimalizace ■ generování kódu ■ využití všech jednotek Luděk Matýska • Překladače • Jaro 2020 3/31 FACULTY OF INFORMATICS I Masaryk University Mezijazyk ■ Čtveřice (obecně n-ť\ce) ■ Instrukce: operátor, dva operandy, výsledek ■ Příklad ■ Přiřazení: X := Y op Z ■ Pamět: přes dočasné proměnné tn ■ Skoky: podmínka počítána samostatně ■ Skoky: na absolutní adresy Luděk Matýska • Překladače • Jaro 2020 4/31 FACULTY OF INFORMATICS Masaryk University Základní překlad while ( j < n ) { } A: B: t4 t5 t6 t7 k t8 t9 k = k + j*2 m = j*2 j++ = j = n = tl < t2 (B) t3 tl t2 t3 jmp jmp (C) TRUE k j t5*2 t4+t6 t7 j t8*2 m tie tn = t9 = j = tl0+l = til jmp (A) TRUE C: : Luděk Matýska • Překladače • Jaro 2020 FACULTY OF INFORMATICS Masaryk University Základní bloky ■ Program je pak reprezentován grafem toku (flow graph) ■ BLok -část programu bez skoků ■ Jeden vstupní a jeden výstupní bod ■ Blok jako DAG (Directed Acyclic Graph) ■ Optimalizace uvnitř bloků ■ Odstranění opakovaných (pod)výrazů ■ Odstranění přebytečných proměnných Luděk Matýska • Překladače • Jaro 2020 6/31 FACULTY OF INFORMATICS Masaryk University Directed Acyclic Graph B:: t4 t5 t6 t7 k t8 t9 m tie tn 3 k 3 t5*2 t4+t6 t7 D t8*2 t9 D tl0+l til jmp (A) TRUE "2" J,t5,t8,t10 \ A / K5t4 W7 V f * 1 / \ t6,t9,M \ ^ ^ / \ \ >x \ x **• \ X **• \ X "v \ X \ X ««■» \ X >. \ X \ X % *x *** t7,K (+} (+) tn,j Luděk Matýska • Překladače • Jaro 2020 7/31 FACULTY OF INFORMATICS Masaryk University Modifikovaný překlad t4 ■ — k B: : t4 := k t5 : ■ = • t5 • := 3 t6 : ■ = t5*2 t6 := t5*2 t7 : ■ ZZ 14+16 m := t6 k : ■ = t7 t7 := t6+t4 t8 ■ ZZ • k := t7 t9 : ■ = t8*2 til := t5+l m ■ ZZ t9 • 3 := til tie : ■ ZZ • 3 jmp (A) TRUE til : ■ = tl0+l • 3 : ■ ZZ til jmp CA) TRUE Luděk Matýska • Překladače • Jaro 2020 8/31 FACULTY OF INFORMATICS Masaryk University Další pojmy ■ Proměnné ■ Definice a místa použití ■ Cykly ■ Proces generovaní cílového kódu ■ Součástí tzv. peephole optimalizace Luděk Matýska • Překladače • Jaro 2020 FACULTY OF INFORMATICS Masaryk University Optimalizovaný překlad tl ■= j t2 := n t3 := tl < jmp (B) t3 jmp (C) TRUE t4 := k t5 := J t6 := t5*2 t7 := t4+t6 k •= t7 t8 = j t9 = t8*2 m = t9 tl0 = J til = tl0+l ■ = til jmp (A) TRUE C: : Luděk Matýska • Překladače • Jaro 2020 A: : tl := j t2 := n t4 := k t9 := m tl2 := tl+tl t3 := tl >= t2 jmp (Bl) t3 B: : t4 := t4+tl2 t9 := tl2 tl := tl+1 tl2 := tl2+2 t3 := tl < t2 jmp (B) t3 Bl:: k := t4 m := t9 C: : 10/31 FACULTY OF INFORMATICS Masaryk University Klasické optimalizace ■ Propagace kopírováním ■ Příklad: X = Y Z = 1. + X ■ Zpracování konstant ■ propagace konstant ■ Odstranění mrtvého kódu ■ nedosažitelný kód ■ šetření cache pro instrukce Luděk Matýska • Překladače • Jaro 2020 FACULTY OF INFORMATICS Masaryk University Klasické optimalizace II ■ Strength reduction ■ Příklad: K**2 K*K ■ Přejmenování proměnných ■ Příklad x = y*z; x0 = y*z; q = r+x+x; =>► q = r+x0+x0; x = a+b x = a+b ■ Odstraňování společných podvýrazů (podstatné zejména pro výpočet adres prvků polí) Luděk Matýska • Překladače • Jaro 2020 12/31 FACULTY OF INFORMATICS Masaryk University Klasické optimalizace III ■ Přesun invariantního kódu z cyklů ■ Zjednodušení indukčních proměnných (výrazů s) ■ A(I) je většinou počítáno jako: address = base_address(A) + (I-l)*sizeof _datatype(A) což lze snadno v lineárním cyklu převést na mimo cykíus: address = base_address(A) - sizeof _datatype(A) v cyklu: address = address + sizeof _datatype(A) ■ Přiřazení registrů proměnným Luděk Matýska • Překladače • Jaro 2020 13/31 FACULTY OF INFORMATICS Masaryk University Odstraňování smetí ■ Podprogramy, makra ■ Inlining ■ Podmíněné výrazy ■ Reorganizace složitých výrazů ■ Nadbytečné testy (if versus case) ■ Podmíněné výrazy uprostřed cyklů ■ Nezávislé na cyklu ■ Závislé na cyklu ■ Nezávislé na iteraci ■ Závislé mezi iteracemi Luděk Matýska • Překladače • Jaro 2020 14/31 FACULTY OF INFORMATICS Masaryk University Podmíněné výrazy - příklad if (n .eq 0) then do 1=1 k 00 1=1'k IF CH eo ch then aci)=aci)+bci)* IF cn .eq 0) then continue aci)=aci)+bci)^c LUiNixiNUt Fl SF aci>0 00 1=1'K endÍ D AW=0 continue endif Luděk Matýska • Překladače • Jaro 2020 FACULTY OF INFORMATICS Masaryk University Odstraňování smetí ■ Redukce ■ min (nebo max): for(i=0;i z) ? a[i] : z; ■ jak obejít rekurzivní závislost: for(i=0;i z0) ? a[i] : z0; zl=(a[i+l] > zl) ? a[i+l] : zl; } z=(z0 < zl) ? zl : z0; Luděk Matýska • Překladače • Jaro 2020 16/31 FACULTY OF INFORMATICS Masaryk University Redukce - Asociativní transformace ■ Numerická nepřesnost: 4 platná desetinná místa (X + Y) + Z = (.00005 + .00005) + 1.0000 .00010 + + 1.0000 = 1.0001 ale X + (Y + Z) = .00005 + (.00005 + 1.0000) = .00005 + 1.0000 = 1.0000 ■ Redukce DO 1=1,N SUM=SUM+A(I)*B(I) Redukce s rekurzivní závislostí - můžeme použít stejný trik jako u min redukce? Luděk Matýska • Překladače • Jaro 2020 17/31 FACULTY OF INFORMATICS Masaryk University Odstraňování smetí III ■ Skoky ■ Konverze typů REAL*8 A(1000) REAL*4 B(1000) DO 1=1,1000 A(I)=A(I)^B(I) ■ Ruční optimalizace ■ Společné podvýrazy ■ Přesun kódu ■ Zpracování polí (inteligentní překladač,Ca ukazatele) Luděk Matýska • Překladače • Jaro 2020 18/31 FACULTY OF INFORMATICS Masaryk University Optimalizace cyklů ■ Redukce režie ■ Zlepšení přístupu k paměti (cache) ■ Zvýšení paralelismu Luděk Matýska • Překladače • Jaro 2020 19/31 FACULTY OF INFORMATICS Masaryk University Datové závislosti Flow Dependencies (backward dependencies) ■ Příklad: AC2:N) = A(l:N-i;)+B(2:N) DO 1=2 N 00 I=2'N'2 Arn:An iw:n a(I)=aci-i)+bci) A(I)-ACI 1D+BCID A(l+l)=ACi-i)+B(l)+B(l+l) Anti-Dependencies ■ Standardně přejmenování proměnných ■ Příklad DO 1=1:N DO 1=1-N A'm= Bm * E DO 1=1-N acd = BCD * E uyz^ AfI+2. * c BCI) = ACI+2) * C DO 1=1:N A(I)'= A'(I) Luděk Matýska • Překladače • Jaro 2020 20/31 FACULTY OF INFORMATICS Masaryk University Datové závislosti ■ Output Dependencies ■ Příklad: A(I) = C(I) * 2 A(I+2) = D(I) + E ■ V cyklu je vypočteno několik hodnot konkrétní proměnné, zapsat však lze pouze tu „poslední" ■ Může být problém zjistit, která je ta „poslední" Luděk Matýska • Překladače • Jaro 2020 21/31 FACULTY OF INFORMATICS Masaryk University Rozvoj cyklů (loop unrolling) I TěLo cyklu se několikrát zkopíruje: DO 1=1,N A(I)=A(I)+B(i:)*C DO 1=1,N,4 A(I)=A(I)+B(I)*C A(I+l>A(I+l)+B(I+i;)*C A(I+2>A(I+2)+B(I+2;)*C ACI+3)=A(I+3)+BCI+3)*C Luděk Matýska • Překladače • Jaro 2020 22/31 FACULTY OF INFORMATICS I Masaryk University Rozvoj cyklu (Loop unrolling) II ■ Hlavní smysl ■ Snížení režie ■ Snížení počtu průchodů cyklem ■ Zvýšení paralelizace (i v rámci jednoho procesoru) ■ Software pipelining ■ Pre-a postconditioning Loops ■ Adaptace na skutečný počet průchodů Luděk Matýska • Překladače • Jaro 2020 23/31 FACULTY OF INFORMATICS Masaryk University Rozvoj cyklů (loop unrolling) III ■ Nevhodné cykly ■ Malý počet iterací —> úplný rozvoj cyklů ■ „Tlusté" (=velké) cykly: samy obsahují dostatek příležitostí k paralelizaci ■ Cykly s voláním procedur: souvislost s rozvojem procedur (inlining) ■ Cykly s podmíněnými výrazy: spíše starší typy procesorů ■ „Rekurzivní" cykly: cykly s vnitřními závislostmi (a[i]=a[i]+a[i-l]*b) Luděk Matýska • Překladače • Jaro 2020 24/31 FACULTY OF INFORMATICS Masaryk University Problémy s rozvojem cyklů ■ Rozvoj špatným počtem iterací ■ Zahlcení registrů ■ Výpadky vyrovnávací paměti instrukcí (příliš velký cyklus) ■ Hardwarové problémy ■ Především na multiprocesorech se sdílenou pamětí (cache koherence, přetížení sběrnice) ■ Speciální případy: rozvoj vnějších cyklů, spojování cyklů Luděk Matýska • Překladače • Jaro 2020 25/31 FACULTY OF INFORMATICS I Masaryk University Spojování cyklů ■ opakované použití dat ■ větší tělo cykLu ■ kompilátor zvládne sám, pokud mezi cykly není jiný kód for(i=0;i► DO 10 1=1, N A(I,D)=B(I,D)+C(I)^D A(I,D)=B(I,D)+C(D)^D Luděk Matýska • Překladače • Jaro 2020 28/31 FACULTY OF INFORMATICS Masaryk University Optimalizace přístupů k paměti II ■ Skládání do bloků ■ Příklad: DO 1=1,N DO 10 3=1,N AC3,I)=A(3,I)+BCI,3) DO 1=1,N,2 DO 10 3=1,N,2 A(3,I)=A(3,I)+B(I,3) A(3+l,TO=A(3+l,I)+B(I,3+l) A(3,I+1)=A(3,I+1)+B(I+1,3) A(3+l,I+1)=AC3+1,I+1)+B(I+1,3+1) Luděk Matýska • Překladače • Jaro 2020 29/31 FACULTY OF INFORMATICS Masaryk University Optimalizace přístupů k paměti III ■ Nepřímá adresace ■ Příklad: b[i]=a[i+k]*c, hodnota k neznáma při překladu a[k[i]] += b[i]*c ■ Použití ukazatelů ■ Nedostatečná kapacita paměti ■ „Ruční" zpracování ■ Virtuální pamět Luděk Matýska • Překladače • Jaro 2020 30/31 FACULTY OF INFORMATICS Masaryk University Další čtení ■ http://www.inf.ed.ac.uk/teaching/courses/copt/ Luděk Matýska • Překladače • Jaro 2020 31/31