Algorytm unikania komunikacji
Algorytmy unikające komunikacji minimalizują przenoszenie danych w hierarchii pamięci w celu poprawy jej czasu działania i zużycia energii. Minimalizują one sumę dwóch kosztów (pod względem czasu i energii): arytmetyki i komunikacji. Komunikacja w tym kontekście odnosi się do przenoszenia danych między poziomami pamięci lub między wieloma procesorami w sieci. Jest znacznie droższy niż arytmetyka.
Motywacja
Rozważ następujący model czasu pracy:
- Miara obliczeń = Czas na FLOP = γ
- Miara komunikacji = liczba słów przeniesionych danych = β
⇒ Całkowity czas działania = γ·(liczba FLOPów ) + β·(liczba słów)
Z faktu, że β >> γ mierzone w czasie i energii, koszt komunikacji dominuje w kosztach obliczeniowych. Trendy technologiczne wskazują, że względny koszt komunikacji rośnie na różnych platformach, od przetwarzania w chmurze po superkomputery i urządzenia mobilne. Raport przewiduje również, że różnica między pamięci DRAM a liczbą FLOP wzrośnie 100 razy w nadchodzącej dekadzie, aby zrównoważyć zużycie energii między procesorami a pamięcią DRAM.
| Współczynnik FLOP (γ) | Przepustowość pamięci DRAM (β) | Przepustowość sieci (β) |
|---|---|---|
| 59% / rok | 23% / rok | 26% / rok |
Zużycie energii wzrasta o rzędy wielkości, gdy idziemy wyżej w hierarchii pamięci. Prezydent Stanów Zjednoczonych Barack Obama zacytował algorytmy unikające komunikacji we wniosku Departamentu Energii do Kongresu o budżet na rok budżetowy 2012:
Nowy algorytm poprawia wydajność i dokładność systemów komputerowych o ekstremalnej skali. W nowoczesnych architekturach komputerów komunikacja między procesorami trwa dłużej niż wykonanie arytmetycznej na liczbach zmiennoprzecinkowych przez dany procesor. Badacze ASCR opracowali nową metodę, wywodzącą się z powszechnie stosowanych metod algebry liniowej, aby zminimalizować komunikację między procesorami a hierarchią pamięci, poprzez przeformułowanie wzorców komunikacji określonych w algorytmie. Metoda ta została wdrożona w ramach TRILINOS, cenionego pakietu oprogramowania, który zapewnia naukowcom z całego świata funkcjonalność umożliwiającą rozwiązywanie złożonych problemów wielofizycznych na dużą skalę.
Cele
Algorytmy unikania komunikacji zostały zaprojektowane w następujących celach:
- Zreorganizuj algorytmy, aby ograniczyć komunikację między wszystkimi hierarchiami pamięci.
- Osiągnij dolną granicę komunikacji, jeśli to możliwe.
Poniższy prosty przykład pokazuje, w jaki sposób można to osiągnąć.
Przykład mnożenia macierzy
Niech A, B i C będą macierzami kwadratowymi rzędu n × n . Poniższy naiwny algorytm implementuje C = C + A * B:
dla i = 1 do n dla j = 1 do n dla k = 1 do n C(i,j) = C(i,j) + A(i,k) * B(k,j)
Koszt arytmetyczny (złożoność czasowa): n 2 (2 n − 1) dla wystarczająco dużego n lub O( n 3 ).
Przepisanie tego algorytmu z kosztem komunikacji oznaczonym na każdym kroku
dla i = 1 do n {odczytaj wiersz i z A do szybkiej pamięci} - n² odczytuje dla j = 1 do n {odczytaj C(i,j) do szybkiej pamięci} - n² odczytuje {odczytaj kolumnę j z B do szybkiej pamięci} - n³ odczytuje dla k = 1 do n C(i,j) = C(i,j) + A(i,k) * B(k,j) {zapisz C(i,j) z powrotem do wolnej pamięci} - n² pisze
Szybka pamięć może być zdefiniowana jako lokalna pamięć procesora (pamięć podręczna procesora ) o rozmiarze M, a wolna pamięć może być zdefiniowana jako DRAM.
Koszt komunikacji (odczyt/zapis): n 3 + 3 n 2 lub O( n 3 )
Ponieważ całkowity czas pracy = γ ·O( n3 ) + β ·O( n3 ) i β >> γ , koszt komunikacji jest dominujący. Zablokowany (kafelkowy) algorytm mnożenia macierzy redukuje ten dominujący składnik:
Zablokowane (kafelkowe) mnożenie macierzy
Rozważmy, że A, B i C to macierze n / b -by- n / b podbloków b -by- b , gdzie b nazywa się rozmiarem bloku; załóżmy, że trzy bloki b -by- b mieszczą się w szybkiej pamięci.
dla i = 1 do n/b dla j = 1 do n/b {wczytaj blok C(i,j) do szybkiej pamięci} - b² × (n/b)² = n² czyta dla k = 1 do n/b { wczytaj blok A(i,k) do szybkiej pamięci} - b² × (n/b)³ = n³/b wczytaj {wczytaj blok B(k,j) do szybkiej pamięci} - b² × (n/b)³ = n³ /b czyta C(i,j) = C(i,j) + A(i,k) * B(k,j) - {zrób macierz mnożenia na blokach} {zapisz blok C(i,j) z powrotem do wolna pamięć} - b² × (n/b)² = n² zapisuje
Koszt komunikacji: 2 n 3 / b + 2 n 2 odczyty/zapisy << 2 n 3 koszt arytmetyczny
Uczynienie b tak dużym, jak to możliwe:
- 3 b 2 ≤ M
osiągamy następującą dolną granicę komunikacji:
- 3 1/2 n 3 / M 1/2 + 2 n 2 lub Ω (liczba FLOPów / M 1/2 )
Poprzednie podejścia do ograniczania komunikacji
Większość podejść badanych w przeszłości w celu rozwiązania tego problemu opiera się na technikach planowania lub dostrajania, które mają na celu nakładanie się komunikacji z obliczeniami. Jednak takie podejście może prowadzić do poprawy co najwyżej o współczynnik dwóch. Ghosting to inna technika ograniczania komunikacji, w której procesor przechowuje i nadmiarowo przetwarza dane z sąsiednich procesorów do przyszłych obliczeń. Algorytmy nieświadome pamięci podręcznej reprezentują inne podejście wprowadzone w 1999 r. Do szybkich transformat Fouriera , a następnie rozszerzone na algorytmy grafowe, programowanie dynamiczne itp. Zostały również zastosowane do kilku operacji w algebrze liniowej jako gęste faktoryzacje LU i QR. Projektowanie algorytmów specyficznych dla architektury to kolejne podejście, które można wykorzystać do ograniczenia komunikacji w algorytmach równoległych, aw literaturze jest wiele przykładów algorytmów dostosowanych do danej topologii komunikacji.