Algoritmus zabraňující komunikaci - Communication-avoiding algorithm

Algoritmy zabraňující komunikaci minimalizovat pohyb dat v rámci a hierarchie paměti pro zlepšení jeho doby chodu a spotřeby energie. Ty minimalizují součet dvou nákladů (z hlediska času a energie): aritmetiky a komunikace. Komunikace v této souvislosti označuje přesun dat, a to buď mezi úrovněmi paměti, nebo mezi více procesory po síti. Je to mnohem dražší než aritmetika.[1]

Motivace

Zvažte následující model za běhu:[2]

  • Míra výpočtu = čas na FLOP = γ
  • Míra komunikace = počet slov dat přesunutých = β

⇒ Celková doba provozu = γ · (počet z FLOPy ) + β · (počet slov)

Ze skutečnosti, že β >> y měřeno v čase a energii, náklady na komunikaci dominují výpočtovým nákladům. Technologické trendy[3] naznačují, že relativní náklady na komunikaci rostou na různých platformách od cloud computing na superpočítače do mobilních zařízení. Zpráva také předpovídá tento rozdíl mezi DOUŠEK přístupová doba a FLOPy se v nadcházejícím desetiletí zvýší stokrát, aby se vyrovnalo využití energie mezi procesory a DRAM.[1]

Rychlost FLOP (γ)Šířka pásma DRAM (β)Šířka pásma sítě (β)
59% / rok23% / rok26% / rok
Energetické náklady na pohyb dat v roce 2010: On-chip vs. Off-chip

Spotřeba energie se zvyšuje řádově, jak jdeme výše v hierarchii paměti.[4] Americký prezident Barack Obama uvedl v Kongresu žádost o rozpočet FY 2012 na algoritmy, které se vyhýbají komunikaci:[1]

Nový algoritmus zvyšuje výkon a přesnost v extrémních počítačích. Na moderních počítačových architekturách trvá komunikace mezi procesory déle než výkon aritmetické operace s plovoucí desetinnou čárkou daným procesorem. Vědci AV ČR vyvinuli novou metodu odvozenou od běžně používaných metod lineární algebry, která minimalizuje komunikaci mezi procesory a hierarchií paměti přeformulováním komunikačních vzorů specifikovaných v algoritmu. Tato metoda byla implementována v rámci TRILINOS, vysoce ceněné sadě softwaru, která poskytuje funkcionalitu pro výzkumné pracovníky z celého světa při řešení rozsáhlých komplexních multifyzikálních problémů.

Cíle

Algoritmy zabraňující komunikaci jsou navrženy s následujícími cíli:

  • Reorganizujte algoritmy, abyste snížili komunikaci napříč všemi hierarchiemi paměti.
  • Pokud je to možné, dosáhněte dolní meze komunikace.

Následující jednoduchý příklad[1] ukazuje, jak je jich dosaženo.

Příklad násobení matic

Nechť A, B a C jsou čtvercové matice řádu n × n. Následující naivní algoritmus implementuje C = C + A * B:

Maticový multiplikační algoritmus diagram.png

 pro i = 1 až n pro j = 1 až n pro k = 1 až n C (i, j) = C (i, j) + A (i, k) * B (k, j)

Aritmetické náklady (časová složitost): n2(2n - 1) pro dostatečně velké n nebo O (n3).

Přepisování tohoto algoritmu s náklady na komunikaci označenými v každém kroku

 pro i = 1 až n {číst řádek i z A do rychlé paměti} - n² čte pro j = 1 až n {číst C (i, j) do rychlé paměti} - n² číst {číst sloupec j B do rychlé paměti} - n³ čte pro k = 1 až n C (i, j) = C (i, j) + A (i, k) * B (k, j) {zapsat C (i, j) zpět do pomalé paměti} - n² píše

Rychlou paměť lze definovat jako lokální paměť procesoru (Mezipaměť CPU ) o velikosti M a pomalé paměti lze definovat jako DRAM.

Náklady na komunikaci (čtení / zápis): n3 + 3n2 nebo O (n3)

Od celkové doby provozu = y·Ó(n3) + β·Ó(n3) a β >> y náklady na komunikaci jsou dominantní. Blokovaný (skládaný) maticový multiplikační algoritmus[1] snižuje tento dominantní výraz:

Blokované (kachlová) násobení matice

Zvažte A, B a C. n/b-podle-n/b matice z b-podle-b dílčí bloky, kde b se nazývá velikost bloku; předpokládejme tři b-podle-b bloky se vejdou do rychlé paměti.

Kanálový multiplikační diagram.png

 pro i = 1 až n / b pro j = 1 až n / b {čte blok C (i, j) do rychlé paměti} - b² × (n / b) ² = n² čte pro k = 1 až n / b { číst blok A (i, k) do rychlé paměti} - b² × (n / b) ³ = n³ / b čte {číst blok B (k, j) do rychlé paměti} - b² × (n / b) ³ = n³ / b čte C (i, j) = C (i, j) + A (i, k) * B (k, j) - {násobí matici na blocích} {zapisuje blok C (i, j) zpět na pomalá paměť} - b² × (n / b) ² = n² zápisů

Náklady na komunikaci: 2n3/b + 2n2 čte / zapisuje << 2n3 aritmetické náklady

Tvorba b co největší:

3b2 ≤ M

dosáhneme následující komunikace dolní mez:

31/2n3/M1/2 + 2n2 nebo Ω (počet FLOP / M1/2)

Předchozí přístupy ke snížení komunikace

Většina přístupů zkoumaných v minulosti k řešení tohoto problému závisí na technikách plánování nebo ladění, jejichž cílem je překrývání komunikace s výpočtem. Tento přístup však může vést ke zlepšení maximálně o faktor dva. Ghosting je odlišná technika pro snížení komunikace, při které procesor ukládá a redundantně počítá data ze sousedních procesorů pro budoucí výpočty. Algoritmy zapomínající na mezipaměť představují odlišný přístup zavedený v roce 1999 pro rychlé Fourierovy transformace,[5] a poté rozšířeny o grafové algoritmy, dynamické programování atd. Byly také použity pro několik operací v lineární algebře[6][7][8] jako husté faktorizace LU a QR. Návrh algoritmů specifických pro architekturu je dalším přístupem, který lze použít ke snížení komunikace v paralelních algoritmech, a v literatuře existuje mnoho příkladů algoritmů, které jsou přizpůsobeny dané topologii komunikace.[9]

Viz také

Reference

  1. ^ A b C d E Demmel, Jim. Msgstr "Komunikace vyhýbající se algoritmům". 2012 SC Companion: Vysoce výkonné výpočty, síťové úložiště a analýza. IEEE, 2012.
  2. ^ Demmel, James a Kathy Yelick. "Vyhýbání se komunikaci (CA) a další inovativní algoritmy". Laboratoř Berkeley Par Lab: Pokrok v paralelním výpočetním prostředí: 243–250.
  3. ^ Bergman, Keren a kol. "Výpočetní studie Exascale: Technologické výzvy v exascale výpočetních systémech." Agentura pro obranné výzkumné projekty Kancelář technik zpracování informací (DARPA IPTO), Tech. Rep 15 (2008).
  4. ^ Shalf, John, Sudip Dosanjh a John Morrison. "Výzvy výpočetní technologie Exascale". High Performance Computing for Computational Science – VECPAR 2010. Springer Berlin Heidelberg, 2011. 1–25.
  5. ^ M. Frigo, C. E. Leiserson, H. Prokop a S. Ramachandran, „Cacheoblivious algorithms“, In FOCS ’99: Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999. IEEE Computer Society.
  6. ^ S. Toledo, “Lokalita reference v LU Dekompozice s částečným otočením „SIAM J. Matrix Anal. Appl., Sv. 18, č. 4, 1997.
  7. ^ F. Gustavson, „Rekurze vede k automatickému blokování proměnných pro algoritmy husté lineární algebry,“ IBM Journal of Research and Development, sv. 41, č. 6, str. 737–755, 1997.
  8. ^ E. Elmroth, F. Gustavson, I. Jonsson a B. Kagstrom, “Rekurzivní blokované algoritmy a hybridní datové struktury pro software knihovny s hustou maticí „SIAM Review, roč. 46, č. 1, s. 3–45, 2004.
  9. ^ Grigori, Laura. "Úvod do komunikace, vyhýbání se algoritmům lineární algebry ve vysoce výkonných počítačích.