Dlaczego wyrażanie obliczeń jako mnożenie macierzy przyspiesza je?

W samouczku Google MNist z użyciem TensorFlow pokazano obliczenia, w których jeden krok jest równoważny pomnożeniu macierzy przez wektor. Google najpierw pokazuje obraz, w którym każde mnożenie i dodawanie liczbowe, które byłoby potrzebne do wykonania obliczenia, jest zapisywane w całości. Następnie pokazują obraz, na którym jest on wyrażony jako mnożenie macierzy, twierdząc, że ta wersja obliczeń jest, a przynajmniej może być, szybsza:

Jeśli wypiszemy to jako równania, otrzymamy:

Możemy „wektoryzować” tę procedurę, zamieniając ją w mnożenie macierzy i dodawanie wektora. Jest to pomocne dla wydajności obliczeniowej. (Jest to również przydatny sposób myślenia).

Wiem, że takie równania są zwykle zapisywane w formacie mnożenia macierzy przez praktyków uczenia maszynowego, i oczywiście widzę korzyści z robienia tego z punktu widzenia zwięzłości kodu lub zrozumienia matematyki. To, czego nie rozumiem, to twierdzenie Google, że konwersja z formy długiej do formy macierzowej „jest pomocna dla wydajności obliczeniowej”

Kiedy, dlaczego i jak można uzyskać poprawę wydajności oprogramowania, wyrażając obliczenia jako mnożenia macierzy? Gdybym sam obliczył mnożenie macierzy na drugim obrazie (opartym na macierzy), jako człowiek, zrobiłbym to, wykonując kolejno każde z odrębnych obliczeń pokazanych na pierwszym obrazie (skalarnym). Dla mnie są to tylko dwie notacje dla tej samej sekwencji obliczeń. Dlaczego na moim komputerze jest inaczej? Dlaczego komputer miałby wykonywać obliczenia macierzy szybciej niż obliczenia skalarne?

Może się to wydawać oczywiste, ale komputery nie wykonują formuł , wykonują kod , a czas wykonania zależy bezpośrednio od kodu, który wykonują, i tylko pośrednio od jakiejkolwiek koncepcji, którą implementuje kod. Dwa logicznie identyczne fragmenty kodu mogą mieć bardzo różne charakterystyki wydajności. Niektóre powody, które mogą pojawić się w wyniku mnożenia macierzy:

• Używanie wielu wątków. Prawie nie ma nowoczesnego procesora, który nie ma wielu rdzeni, wiele ma do 8, a wyspecjalizowane maszyny do obliczeń o wysokiej wydajności mogą z łatwością mieć 64 na kilku gniazdach. Pisanie kodu w oczywisty sposób, w normalnym języku programowania, wykorzystuje tylko jeden z nich. Innymi słowy, może zużywać mniej niż 2% dostępnych zasobów obliczeniowych komputera, na którym działa.
• Korzystanie z instrukcji SIMD (myląco nazywane jest to również „wektoryzacją”, ale w innym sensie niż w cytatach tekstowych w pytaniu). Zasadniczo, zamiast 4 lub 8 skalarnych instrukcji arytmetycznych, daj CPU jedną instrukcję, która wykonuje arytmetykę na 4 lub 8 rejestrach równolegle. Może to dosłownie wykonać kilka obliczeń (gdy są one całkowicie niezależne i pasują do zestawu instrukcji) 4 lub 8 razy szybciej.
• Inteligentniejsze wykorzystanie pamięci podręcznej . Dostęp do pamięci jest szybszy, jeśli jest on spójny czasowo i przestrzennie , tzn. Kolejne dostępy są do pobliskich adresów, a podczas uzyskiwania dostępu do adresu dwukrotnie uzyskuje się do niego dwa razy z rzędu, a nie z długą przerwą.
• Korzystanie z akceleratorów, takich jak procesory graficzne. Urządzenia te różnią się znacznie od procesorów, a ich efektywne programowanie jest samodzielną formą sztuki. Na przykład mają setki rdzeni, które są pogrupowane w grupy kilkudziesięciu rdzeni, a te grupy współużytkują zasoby - dzielą kilka KiB pamięci, która jest znacznie szybsza niż normalna pamięć, a kiedy dowolny rdzeń grupy wykonuje ifinstrukcja wszyscy inni w tej grupie muszą na to poczekać.
• Rozłóż pracę na kilka komputerów (bardzo ważne w superkomputerach!), Co wprowadza ogromny zestaw nowych problemów, ale oczywiście może zapewnić dostęp do znacznie większych zasobów obliczeniowych.
• Inteligentniejsze algorytmy. W przypadku mnożenia macierzy prosty algorytm O (n ^ 3), odpowiednio zoptymalizowany przy użyciu powyższych sztuczek, jest często szybszy niż algorytmy pod-sześcienne dla rozsądnych rozmiarów macierzy, ale czasami wygrywa. W szczególnych przypadkach, takich jak rzadkie macierze, możesz pisać wyspecjalizowane algorytmy.

Wielu inteligentnych ludzi napisało bardzo skuteczny kod dla typowych operacji algebry liniowej , używając powyższych sztuczek i wielu innych, a zwykle nawet głupich sztuczek specyficznych dla platformy. Dlatego przekształcenie formuły w mnożenie macierzy, a następnie wdrożenie tego obliczenia przez wywołanie dojrzałej biblioteki algebry liniowej korzysta z tego wysiłku optymalizacji. Z drugiej strony, jeśli po prostu wypiszesz formułę w oczywisty sposób w języku wysokiego poziomu, wygenerowany kod maszynowy nie wykorzysta wszystkich tych sztuczek i nie będzie tak szybki. Jest to również prawdą, jeśli weźmiesz formułowanie macierzy i zaimplementujesz ją przez wywołanie naiwnej procedury mnożenia macierzy, którą sam napisałeś (ponownie, w oczywisty sposób).

Szybkie tworzenie kodu wymaga pracy , a często dużo pracy, jeśli chcesz uzyskać ostatnią uncję wydajności. Ponieważ tak wiele ważnych obliczeń można wyrazić jako połączenie kilku operacji algebry liniowej, ekonomicznie jest stworzyć wysoce zoptymalizowany kod dla tych operacji. Ale twój wyjątkowy przypadek specjalnego zastosowania? Nikt nie dba o to oprócz ciebie, więc optymalizacja tego nie jest ekonomiczna.

(rzadkie) Mnożenie macierzy-wektora jest wysoce równoległe. Jest to bardzo przydatne, jeśli twoje dane są duże i masz do dyspozycji farmę serwerów.

Oznacza to, że możesz podzielić macierz i wektor na części i pozwolić oddzielnym maszynom wykonać część pracy. Następnie podziel się niektórymi wynikami, a następnie uzyskaj wynik końcowy.

W twoim przykładzie operacje wyglądałyby następująco

1. ustaw siatkę procesorów, z których każdy ma Wx, y zgodnie z ich współrzędną w siatce

2. rozgłaszać wektor źródłowy wzdłuż każdej kolumny (koszt O(log height))

3. mieć lokalnie każdy procesor do mnożenia (koszt O(width of submatrix * heightof submatrix))

4. zwiń wynik wzdłuż każdego wiersza za pomocą sumy (kosztu O(log width))

Ta ostatnia operacja jest poprawna, ponieważ suma jest skojarzona.

Pozwala to również na budowanie redundancji i pozwala uniknąć konieczności umieszczania wszystkich informacji w jednym komputerze.

W przypadku małych matryc 4x4, jak widać w grafice, procesor ma specjalne instrukcje i rejestry do obsługi tych operacji.

Najbardziej pouczającą rzeczą byłoby porównanie wydajności twojego kodu z wydajnością zaimplementowanego przez alredy mnożenia macierzy.

Zawsze istnieje pewna optymalizacja niższego poziomu, o której nie pomyślałeś, tutaj możesz znaleźć przykład:

https://simulationcorner.net/index.php?page=fastmatrixvector