IA039: Architektura superpočítačů a náročné výpočty Překladače Luděk Matýska Fakulta informatiky MU Jaro 2013 Luděk Matýska (Fl MU) Překladače Jaro 2013 1/30 Opakovaní - RICS procesory • limitovaný počet instrukcí, jednotná délka • jednoduché adresní módy, load/store, hodně registru • delay branches, brach prediction, out-of-order execution 0 superskalární (MIPS - 2xFPU, 2xALU, adresace) • superpipeline (ANDES) • vyrovnávací paměti Luděk Matýska (Fl MU) Překladače Jaro 2013 2 / 30 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 (Fl MU) Překladače Jaro 2013 3 / 30 Mezijazyk Čtveřice (obecně n-tice) 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 (Fl MU) 4/30 Základní překlad while ( j < n ) { k = k + j*2 m = j*2 tl = J m := t9 t2 = n tio := J t3 = tl < t2 til := tlO+1 jmp (B) t3 j := til jmp (C) TRUE (A) TRUE t4 = k C: : t5 = J t6 = t5*2 t7 = t4+t6 k = t7 t8 = J t9 = t8*2 Luděk Matýska (Fl MU) Překladače Jaro 2013 5 / 30 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 (Fl MU) Překladače Jaro 2013 6 / 30 Directed Acyclic Graph Luděk Matýska (Fl MU) Překladače Jaro 2013 7 / 30 Modifikovaný překlad t4 = k B: : t4 = k t5 = j t5 = J t6 = t5*2 t6 = t5*2 t7 = t4+t6 m = t6 k = t7 t7 = t6+t4 t8 = j k = t7 t9 = t8*2 tll = t5+l m = t9 j = tll tio = j jmp (A) TRUE tll = tlO+1 j = tll jmp (A) TRUE Luděk Matýska (Fl MU) 8/30 Další pojmy • Proměnné • Definice a místa použití • Cykly • Proces generování cílového kódu • Součástí tzv. peephole optimalizace Luděk Matýska (Fl MU) Jaro 2013 9 / 30 Optimalizovaný překlad tl = j A: : tl = J t2 = n t2 = n t3 = tl < t2 t4 = k jmp (B) t3 t9 = m jmp (C) TRUE tl2 = tl+tl t4 = k t3 = tl >= t2 t5 = j jmp (Bl) t3 t6 = t5*2 B: : t4 = t4+tl2 t7 = t4+t6 t9 = tl2 k = t7 tl = tl+1 t8 = j tl2 = tl2+2 t9 = t8*2 t3 = tl < t2 m = t9 jmp (B) t3 tio = j Bl: : k = t4 til = tlO+1 m = t9 j = til C: : jmp (A) TRUE 10 / 30 Klasické optimalizace • Propagace kopírováním a Příklad: • Zpracování konstant • propagace konstant • Odstranění mrtvého kódu • nedosažitelný kód • šetření cache pro instrukce X = Y Z = 1. + X X = Y Z = 1. + Y Luděk Matýska (Fl MU) Překladače Jaro 2013 11 / 30 Klasické optimalizace II • Strength reduction • Příklad: K**2 =3> K*K • Přejmenování proměnných • Příklad x = y*z; xO = y*z; q = r+x+x; =>- q = r+xO+xO; 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 (Fl MU) Překladače Jaro 2013 12 / 30 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) + (1-1)*sizeof_datatype(A) což lze snadno v lineárním cyklu převést na mimo cyklus: 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 (Fl MU) Překladače Jaro 2013 13 / 30 Odstraňovaní smetí • Podprogramy, makra a 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 (Fl MU) 14 / 30 Podmíněné výrazy - příklad DD 1=1,K IF (N .EQ 0) THEN A(I)=A(I)+B(I)*C ELSE A(I)=0 END IF IF (N .EQ 0) THEN DD 1=1,K A(I)=A(I)+B(I)*C CONTINUE ELSE DD 1=1,K A(I)=0 CONTINUE END IF Luděk Matýska (Fl MU) Překladače Jaro 2013 15 / 30 Odstraňovaní smetí I • Redukce • min (nebo max): for(i=0;i z) ? a[i] : z; • jak obejít rekurzivní závislost: for(i=0;i zO) ? a[i] : zO; zl=(a[i+l] > zl) ? a[i+l] : zl; } z=(zO < zl) ? zl : zO; Luděk Matýska (Fl MU) Překladače Jaro 2013 16 / 30 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 (Fl MU) Překladače Jaro 2013 17 / 30 Odstraňovaní smetí I • Skoky • Konverze typů REAL*8 A(1000) REAL*4 B(1000) DO I 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č, C a ukazatele) Luděk Matýska (Fl MU) Překladače Jaro 2013 18 / 30 Optimalizace cyklů Cíle: • Redukce režie • Zlepšení přístupu k paměti (cache) • Zvýšení paralelismu Luděk Matýska (Fl MU) 19 / 30 Datové závislosti I • Flow Dependencies (backward dependencies) • Příklad: ™ T- „ ,T 00 1=2,N,2 .m'lrx n „m => A(l)=A(l-l)+B(l) A(I)=A(I-1)+B(I) A(I+1)=A(I-1)+B(I)+B(I+1) • Anti-Dependencies • Standardně přejmenování proměnných • Příklad DO 1=1:N A(I) = B(I) * E B(I) = A(I+2) * C DO 1=1:N A'(I)= B(I) * E DO 1=1:N B(I) = A(1+2) * C DO 1=1:N A(I) = A'(I) Luděk Matýska (Fl MU) Překladače Jaro 2013 20 / 30 Datové závislosti I • 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 (Fl MU) Překladače Jaro 2013 21 / 30 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+1)=A(I+1)+B(I+1)*C A(I+2)=A(I+2)+B(I+2)*C A(I+3)=A(I+3)+B(I+3)*C Luděk Matýska (Fl MU) Překladače Rozvoj cyklů (loop unrolling) II • Hlavní smysl a 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 (Fl MU) Překladače Jaro 2013 23 / 30 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 (Fl MU) Překladače Jaro 2013 24 / 30 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 (Fl MU) Překladače Jaro 2013 25 / 30 Spojovaní cyklů opakované použití dat větší tělo cyklu kompilátor zvládne sám, pokud mezi cykly není jiný kód a[0]=b [0]+l for(i=0;i DO 10 1=1,N A(I,J)=B(I,J)+C(I)*D A(I,J)=B(I,J)+C(J)*D Luděk Matýska (Fl MU) Překladače Jaro 2013 28 / 30 Optimalizace přístupů k paměti II • Skládání do bloků • Příklad: DO 1=1,N DO 10 J=1,N A(J,I)=A(J,I)+B(I,J) DO 1=1,N,2 DO 10 J=1,N,2 A(J,I)=A(J,I)+B(I,J) A(J+1,I)=A(J+1,I)+B(I,J+l) A(J,I+1)=A(J,I+1)+B(I+1, J) A(J+1,I+1)=A(J+1,I+1)+B(I+1,J+l) Luděk Matýska (Fl MU) Překladače Jaro 2013 29 / 30 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 (Fl MU) Překladače Jaro 2013 30 / 30