tutorial

Optimalizace ahodnocení efektivitylineárních kódůIvan Šimeček, Pavel TvrdíkDepartment of Computer Science and EngineeringFaculty of Electrical EngineeringCzech Technical UniversityKarlovo nám. 13121 35 Prague 2Czech RepublicThis research has been supported by grant IBS 3086102.Obsah prezentace 2(1) Proč optimalizovat?(2) Architektura procesorů Intel (AMD) a některé nové rysy(3) SW techniky pro optimalizaci(4) Pravděpodobnostní model chování skryté paměti(5) Knihovny pro LA, výhody a nevýhody(6) Příklady použití jednotlivých optimalizačních postupůProč optimalizovat? 3Motivační příkladNásobení matic (MMM): A(n,n)×B(n,n) = C(n,n) Klasický algoritmus pro násobení (podle definice). Pro uložení čísel a výpočet použita dvojitá přesnost (typ double).Pro všechna měření (kromě vyjímky na slajdu 15) byla použita následující konfigurace: Intel Pentium 4• 2.4GHz, výrobcem udávaná špičková výkonnost procesoru 2.4 Gflops.• 512MB hlavní paměť na 400MHz, 8KB skrytá paměť 1. úrovně (L1) a 128KB skrytápaměti 2. úrovně (L2). Intel kompilátor (ICC) s přepínači pro maximální výkon.Standardní implementace MMM 4AlgorithmSMMM(in double A,B[1,...,n][1,...,n]; out C[1,...,n][1,...,n])(∗ Standardní implementace MMM∗)for i = 1 to n dofor j = 1 to n dobegins = 0;for k = 1 to n dos+ = A[i][k]∗B[k][j];C[i][j] = s;endPožadavky na paměťovou sběrniciNa 1 prvek výsledné matice je třeba z paměti načíst 2n čísel.VýkonnostPočet aritmetických FPU operací za ...