IA039: Architektura superpočítačů a náročné výpočty Překladače Luděk Matýska Fakulta informatiky MU Jaro 2016 Luděk Matýska (Fl MU) Překladače Jaro 2016 1/30 Opakovaní - 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 Optimalizující překladač • překlad do mezijazyka • optimalizace 9 mezi procedurá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 2016 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ě 9 Skoky: na absolutní adresy Luděk Matýska (Fl MU) Překladače Jaro 2016 4 / 30 Základní preklad while ( j < n ) { k = k + j*2 m = j*2 } A:: tl := j t2 := n t3 := tl < t2 jmp (B) t3 jmp (C) TRUE B:: t4 := k t5 := j t6 := t5*2 17 := t4+t6 k := t7 t8 := j t9 := t8*2 m := t9 tlO := j tll := tlO+1 j := tll jmp (A) TRUE Luděk Matýska (Fl MU) Překladače 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ů 9 Odstranění přebytečných proměnných Luděk Matýska (Fl MU) Překladače Jaro 2016 6 / 30 Directed Acyclic Graph Luděk Matýska (Fl MU) Překladače Jaro 2016 Modifikovaný překlad t4 := k t5 • t6 := t5*2 tľ : := t4+t6 k : := tľ t8 : • := J t9 : := t8*2 m : = t9 tlO : • = J tll : = tlO+1 j • = tll jmp (A) TRUE t4 := k t5 t6 := t5*2 m := t6 tľ : := t6+t4 k : := tľ tll : := t5+l j : = tll jmp (A) TRUE Další pojmy • Proměnné • Definice a místa použití • Cykly 9 Proces generování cílového kódu • Součástí tzv. peephole optimalizace Luděk Matýska (Fl MU) Překladače Jaro 2016 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 : := tl tl : := tl+1 t8 : tl2 : = tl2+2 t9 : := t8*2 t3 : = tl < t2 m : := t9 jmp (B) t3 tlO : ■ Bl:: k : = t4 til : = tlO+1 m : = t9 j : = til C: : jmp (A) TRUE C: 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 Překladače Klasické optimalizace II « Strength reduction • Příklad: K**2 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 2016 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 2016 13 / 30 Odstraňovaní smetí • Podprogramy, makra • Inlining • Podmíněné výrazy • Reorganizace složitých výrazů • Nadbytečné testy (if versus case) a 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) Překladače Jaro 2016 14 / 30 Podmíněné výrazy - příklad DO 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 DO 1=1,K A(I)=A(I)+B(I)*C CONTINUE ELSE DO 1=1,K A(I)=0 CONTINUE END IF Luděk Matýska (Fl MU) Překladače Jaro Odstraňovaní smetí • 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] : } z=(zO < zl) ? zl : zO; Luděk Matýska (Fl MU) Překladače 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 redukce? Luděk Matýska (Fl MU) Překladače Jaro 2016 Odstraňovaní smetí • Skoky • Konverze typů REAL*8 A(1000) REAL*4 B(1000) DO I 1=1,1000 A(I)=A(I)*B(I) a 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 2016 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) Překladače Jaro 2016 19 / 30 Datové závislosti Flow Dependencies (backward dependencies) • Příklad: DO 1=2,N,2 * r!.T ^ ,m A(I)=A(I-1)+B(I) 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 DO I-l:N r,„í;(": B<1) * E i(I)-B(I).E -* D0B-!!1(M).C A(I) = A'(I) Luděk Matýska (Fl MU) Překladače Jaro 2016 20 / 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í" 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 Rozvoj cyklů (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 (Fl MU) Překladače Jaro 2016 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) 9 9 Luděk Matýska (Fl MU) Překladače Jaro 2016 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 2016 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