Dlaczego w mnożeniu macierzy 2048x2048 w porównaniu do mnożenia 2047x2047 występuje ogromny wzrost wydajności?

127

Wykonuję pewne testy porównawcze mnożenia macierzy, jak wspomniano wcześniej w Dlaczego MATLAB jest tak szybki w mnożeniu macierzy?

Teraz mam inny problem, kiedy mnożymy dwie macierze 2048x2048, istnieje duża różnica między C # a innymi. Kiedy próbuję pomnożyć tylko macierze 2047x2047, wydaje się to normalne. Dodano też inne dla porównania.

1024x1024 - 10 sekund.

1027x1027 - 10 sekund.

2047x2047 - 90 sekund.

2048x2048 - 300 sekund.

2049x2049 - 91 sekund. (aktualizacja)

2500x2500 - 166 sekund

To różnica trzech i pół minuty w przypadku 2k na 2k.

za pomocą tablic 2dim

//Array init like this
int rozmer = 2048;
float[,] matice = new float[rozmer, rozmer];

//Main multiply code
for(int j = 0; j < rozmer; j++)
{
   for (int k = 0; k < rozmer; k++)
   {
     float temp = 0;
     for (int m = 0; m < rozmer; m++)
     {
       temp = temp + matice1[j,m] * matice2[m,k];
     }
     matice3[j, k] = temp;
   }
 }
Wilk
źródło
23
To byłoby świetne pytanie egzaminacyjne dla zaawansowanego poziomu programowania C lub klasy projektowania systemu operacyjnego ;-)
Dana the Sane
Czy próbowałeś przetestować zarówno tablice wielowymiarowe [,], jak i tablice postrzępione [] [], a także 32 i 64-bitowe? Testowałem tylko kilka razy, ale postrzępiony wydawał się bardziej zgodny z twoimi wynikami, ale postrzępiony 64-bitowy był wysoki. Nie wiem, czy w jicie są jakieś heurystyki, które mają zastosowanie do tej sytuacji, czy też jego pamięć podręczna była powiązana z wcześniej sugerowaną. Jeśli potrzebujesz rozwiązania GPGPU, to research.microsoft.com/en-us/projects/accelerator powinno być konkurencyjne w stosunku do czasów w Twoim drugim poście.
Kris
Trochę naiwne pytanie, ale ile operacji (dodawanie / mnożenie) jest zaangażowanych w mnożenie dwóch kwadratowych macierzy?
Nick T

Odpowiedzi:

61

Prawdopodobnie ma to związek z konfliktami w pamięci podręcznej L2.

Chybienia w pamięci podręcznej matice1 nie stanowią problemu, ponieważ dostęp do nich odbywa się sekwencyjnie. Jednak dla matice2, jeśli pełna kolumna mieści się w L2 (tj. Kiedy uzyskujesz dostęp do matice2 [0, 0], matice2 [1, 0], matice2 [2, 0] ... itd., Nic nie zostanie eksmitowane), to nie ma problemu z Cache misses z matice2.

Teraz, aby zagłębić się w działanie pamięci podręcznych, jeśli adres bajtowy zmiennej to X, niż wiersz pamięci podręcznej dla niej będzie (X >> 6) & (L - 1). Gdzie L to całkowita liczba linii pamięci podręcznej w pamięci podręcznej. L jest zawsze potęgą 2. Szóstka pochodzi z faktu, że 2 ^ 6 == 64 bajty to standardowy rozmiar linii pamięci podręcznej.

Co to teraz oznacza? To znaczy, że jeśli mam adres X i adres Y, a (X >> 6) - (Y >> 6) jest podzielne przez L (czyli jakąś dużą potęgę 2), zostaną one zapisane w tej samej linii pamięci.

Wróćmy teraz do problemu, jaka jest różnica między rokiem 2048 a 2049,

kiedy twój rozmiar to 2048:

jeśli weźmiesz & matice2 [x, k] i & matice2 [y, k] różnica (& matice2 [x, k] >> 6) - (& matice2 [y, k] >> 6) będzie podzielna przez 2048 * 4 (rozmiar pływaka). Więc duża moc 2.

Zatem w zależności od rozmiaru twojego L2 będziesz miał wiele konfliktów linii pamięci podręcznej i wykorzystasz tylko niewielką część twojego L2 do przechowywania kolumny, więc nie będziesz w stanie przechowywać pełnej kolumny w pamięci podręcznej, więc uzyskasz złą wydajność .

Gdy rozmiar wynosi 2049, różnica wynosi 2049 * 4, co nie jest potęgą 2, dzięki czemu będziesz mieć mniej konfliktów, a twoja kolumna bezpiecznie zmieści się w twojej pamięci podręcznej.

Aby przetestować tę teorię, możesz zrobić kilka rzeczy:

Przydziel swoją tablicę macierz matice2 tak jak ta matice2 [razmor, 4096] i uruchom z razmor = 1024, 1025 lub dowolnym rozmiarem, a powinieneś zobaczyć bardzo słabą wydajność w porównaniu z tym, co miałeś wcześniej. Dzieje się tak, ponieważ wymuszasz wyrównanie wszystkich kolumn tak, aby były ze sobą w konflikcie.

Następnie spróbuj matice2 [razmor, 4097] i uruchom go z dowolnym rozmiarem, a powinieneś zobaczyć znacznie lepszą wydajność.

zviadm
źródło
Czy popełniłeś błąd w dwóch ostatnich akapitach? Obie próby są dokładnie takie same. :)
Xeo
Asocjatywność pamięci podręcznej również odgrywa rolę.
Ben Jackson
20

Prawdopodobnie efekt buforowania. Przy wymiarach macierzy, które są dużymi potęgami dwójki i rozmiarem pamięci podręcznej, który jest również potęgą dwóch, możesz w końcu użyć tylko niewielkiej części pamięci podręcznej L1, co znacznie spowalnia działanie. Naiwne mnożenie macierzy jest zwykle ograniczone potrzebą pobrania danych do pamięci podręcznej. Zoptymalizowane algorytmy wykorzystujące kafelki (lub algorytmy nieświadome pamięci podręcznej) koncentrują się na lepszym wykorzystaniu pamięci podręcznej L1.

Jeśli zmierzysz czas z innymi parami (2 ^ n-1,2 ^ n), spodziewam się, że zobaczysz podobne efekty.

Aby dokładniej wyjaśnić, w wewnętrznej pętli, w której uzyskujesz dostęp do matice2 [m, k], jest prawdopodobne, że matice2 [m, k] i matice2 [m + 1, k] są przesunięte względem siebie o 2048 * sizeof (float) iw ten sposób mapować do tego samego indeksu w pamięci podręcznej L1. W przypadku N-kierunkowej asocjacyjnej pamięci podręcznej będziesz mieć zazwyczaj 1-8 lokalizacji pamięci podręcznej dla wszystkich z nich. Zatem prawie wszystkie te próby dostępu spowodują eksmisję pamięci podręcznej L1 i pobranie danych z wolniejszej pamięci podręcznej lub pamięci głównej.

Jonathan Moore
źródło
+1. Brzmi prawdopodobne. Należy uważać na asocjatywność pamięci podręcznej.
Macke
16

Może to mieć związek z rozmiarem pamięci podręcznej procesora. Jeśli 2 rzędy macierzy macierzy nie będą pasować, to stracisz czas na zamianę elementów z pamięci RAM. Dodatkowe 4095 elementów może wystarczyć, aby zapobiec dopasowaniu rzędów.

W twoim przypadku 2 wiersze dla 2047 macierzy 2d mieszczą się w 16 KB pamięci (zakładając typy 32-bitowe). Na przykład, jeśli masz pamięć podręczną L1 (najbliżej procesora w magistrali) o wielkości 64 KB, możesz zmieścić co najmniej 4 wiersze (z 2047 * 32) jednocześnie. W przypadku dłuższych rzędów, jeśli wymagane jest wypełnienie, które wypycha pary wierszy poza 16 KB, sytuacja zaczyna się brudzić. Ponadto za każdym razem, gdy `` przegapisz '' pamięć podręczną, zamiana danych z innej pamięci podręcznej lub pamięci głównej powoduje opóźnienia.

Domyślam się, że różnice w czasie wykonywania, które widzisz w przypadku macierzy o różnych rozmiarach, zależą od tego, jak skutecznie system operacyjny może wykorzystać dostępną pamięć podręczną (a niektóre kombinacje są po prostu problematyczne). Oczywiście to wszystko jest z mojej strony wielkim uproszczeniem.

Dana the Sane
źródło
2
ale jest bardzo mało prawdopodobne, że ma 16,7 MB pamięci podręcznej procesora
Marino Šimić
Zaktualizowałem wyniki o 2049x2049 - 91 sekund. Jeśli był to „problem z pamięcią podręczną”, czy nie powinien to być nadal 300+ s?
Wolf
@Marino odpowiedź została zaktualizowana, aby to uwzględnić.
Dana the Sane
1
Wydaje mi się, że żadne z tych wyjaśnień nie może odpowiednio zająć się nowymi szczegółami dotyczącymi różnych i rzadkich rozmiarów, które wywołują ten problem, a inne pozostają nienaruszone.
Ken Rockot
2
Nie sądzę, żeby to wyjaśnienie było poprawne. Problem polega na tym, że nie wykorzystuje się w pełni pojemności pamięci podręcznej z powodu konfliktów linii pamięci podręcznej, gdy rozmiar wynosi potęgę 2. Również system operacyjny nie ma tak naprawdę nic wspólnego z pamięcią podręczną, ponieważ to nie system operacyjny decyduje, co buforować, a co eksmitować, to wszystko w sprzęcie. System operacyjny ma coś wspólnego z wyrównywaniem danych, ale w tym przypadku chodzi o to, jak C # decyduje się na alokację danych i jak reprezentować tablicę 2D w pamięci, OS nie ma z tym nic wspólnego.
zviadm
5

Biorąc pod uwagę, że przy większych rozmiarach skraca się czas, czy nie byłoby bardziej prawdopodobne, że wystąpią konflikty pamięci podręcznej, szczególnie przy potęgach 2 dla problematycznych rozmiarów macierzy? Nie jestem ekspertem w kwestiach buforowania, ale doskonałe informacje na temat problemów z wydajnością związanych z pamięcią podręczną tutaj .


źródło
Sekcja 5 odsyłacza o asocjatywności pamięci podręcznej wydaje się mieć zastosowanie w szczególności.
Dana the Sane
4

Gdy uzyskujesz dostęp do matice2tablicy w pionie, będzie ona znacznie częściej wymieniana w pamięci podręcznej i poza nią. Jeśli dublujesz tablicę po przekątnej, aby uzyskać do niej dostęp za pomocą [k,m]zamiast [m,k], kod będzie działał znacznie szybciej.

Testowałem to dla matryc 1024x1024 i jest to około dwa razy szybsze. W przypadku matryc 2048x2048 jest to około dziesięć razy szybsze.

Guffa
źródło
To nie wyjaśnia, dlaczego 2049 jest szybszy niż 2048.
Macke
@Macke: To dlatego, że przekracza pewien limit w buforowaniu pamięci, więc jest dużo więcej braków w pamięci podręcznej.
Guffa
Dlaczego głos przeciw? Jeśli nie powiesz tego, co uważasz za złe, nie poprawi to odpowiedzi.
Guffa
Kolejny głos przeciwny bez żadnego wyjaśnienia… Czy moja odpowiedź zawiera za mało głosów „prawdopodobnie”, „zgaduję” i „powinien”, jak odpowiedzi, które otrzymują najwięcej głosów…?
Guffa
4

Aliasing pamięci podręcznej

Albo walenie w pamięć podręczną , jeśli potrafię wymyślić termin.

Pamięci podręczne działają na zasadzie indeksowania bitami o najniższej kolejności i znakowania bitami o najwyższym porządku.

Wyobrażanie sobie, że twoja pamięć podręczna ma 4 słowa, a twoja macierz ma 4 x 4. Kiedy uzyskuje się dostęp do kolumny, a wiersz ma dowolną potęgę dwóch, każdy element kolumny w pamięci będzie mapowany na ten sam element pamięci podręcznej.

Potęga dwa plus jeden jest właściwie optymalna dla tego problemu. Każdy nowy element kolumny będzie mapowany na następny slot pamięci podręcznej dokładnie tak, jak przy dostępie przez wiersz.

W rzeczywistości tag obejmuje wiele kolejno rosnących adresów, które będą buforować kilka sąsiednich elementów w rzędzie. Przesuwając zasobnik, do którego odwzorowuje każdy nowy wiersz, przechodzenie przez kolumnę nie zastępuje poprzedniego wpisu. Podczas przechodzenia przez następną kolumnę cała pamięć podręczna zostanie wypełniona różnymi wierszami, a każda sekcja wiersza, która mieści się w pamięci podręcznej, będzie trafiać przez kilka kolumn.

Ponieważ pamięć podręczna jest znacznie szybsza niż DRAM (głównie ze względu na to, że jest na chipie), szybkość trafień jest wszystkim.

DigitalRoss
źródło
2

Wygląda na to, że osiągnąłeś limit rozmiaru pamięci podręcznej lub być może masz problemy z powtarzalnością czasów.

Jakikolwiek jest problem, po prostu nie powinieneś sam pisać mnożenia macierzy w C # i zamiast tego używać zoptymalizowanej wersji BLAS-a. Ten rozmiar matrycy powinien zostać pomnożony w czasie poniżej sekundy na dowolnej nowoczesnej maszynie.

David Heffernan
źródło
1
Znam BLAS-a, ale moim zadaniem nie było jak najszybsze jego wykonanie, ale napisanie i przetestowanie go w różnych językach. Jest to dla mnie bardzo dziwny problem i jestem naprawdę ciekawy, dlaczego wyniki są takie, jakie są.
Wolf
3
@Wolf Trudno mi się ekscytować tym, czy coś, co powinno zająć sekundę, zajmuje 90, czy 300 sekund.
David Heffernan
4
Najlepszym sposobem, aby dowiedzieć się, jak coś działa, jest napisanie tego samodzielnie i sprawdzenie, jak możesz ulepszyć swoją implementację; to (miejmy nadzieję) robi Wolf.
Callum Rogers
@Callum Rogers, zgodził się. W ten sposób dowiedziałem się, jak ważne są rozmiary buforów w operacjach kopiowania plików.
Kelly S. French
1

Bardzo ważne jest efektywne wykorzystanie hierarchii pamięci podręcznej. Musisz upewnić się, że tablice wielowymiarowe zawierają dane w ładnym układzie, co można osiągnąć poprzez kafelkowanie . Aby to zrobić, musisz zapisać tablicę 2D jako tablicę 1D wraz z mechanizmem indeksowania. Problem z tradycyjną metodą polega na tym, że chociaż dwa sąsiednie elementy tablicy, które znajdują się w tym samym wierszu, znajdują się obok siebie w pamięci, dwa sąsiednie elementy w tej samej kolumnie zostaną oddzielone przez W elementów w pamięci, gdzie W jest liczbą kolumn . Kafelkowanie może spowodować nawet dziesięciokrotną różnicę w wydajności.

Arlen
źródło
Hmm - jednak tablica zadeklarowana jako 2D (float [,] matice = new float [rozmer, rozmer];) jest zawsze alokowana w pamięci RAM tylko jako jednowymiarowa tablica i obliczenia wiersza / kroku wykonywane pod maską. Dlaczego więc deklarowanie tego jako 1D i wykonywanie ręcznych obliczeń wiersz / krok miałoby być szybsze? Czy masz na myśli, że sol'n alokuje dużą tablicę jako tablicę mniejszych płytek, z których każda może zmieścić się w pamięci podręcznej, podczas gdy duża tablica nie?
Eric M
1
Jeśli Twoja biblioteka lub jakiekolwiek narzędzie, z którego korzystasz, wykonuje kafelkowanie, nie musisz tego robić. Ale gdybyś miał użyć tradycyjnej tablicy 2D w, powiedzmy, C / C ++, kafelkowanie poprawiłoby wydajność.
Arlen
0

Podejrzewam, że jest to rezultat czegoś, co nazywa się „ Sequential Flooding ”. Chodzi o to, że próbujesz przejrzeć listę obiektów, która jest nieco większa niż rozmiar pamięci podręcznej, więc każde żądanie do listy (tablicy) musi być wykonane z pamięci RAM, a nie otrzymasz ani jednej pamięci podręcznej trafienie.

W twoim przypadku przechodzisz przez swoje tablice 2048 indeksów 2048 razy, ale masz tylko miejsce na 2047 (prawdopodobnie ze względu na trochę narzutów ze struktury tablicy), więc za każdym razem, gdy uzyskujesz dostęp do pozycji tablicy, musi uzyskać tę pozycję tablicy z barana. Następnie jest przechowywany w pamięci podręcznej, ale tuż przed ponownym użyciem jest zrzucany. Zatem pamięć podręczna jest zasadniczo bezużyteczna, co prowadzi do znacznie dłuższego czasu wykonywania.

Automatico
źródło
1
Błędny. 2049 jest szybszy niż 2048, co odrzuca Twoje roszczenie.
Macke
@Macke: To całkiem możliwe. Istnieje jednak niewielka szansa, że ​​polityka pamięci podręcznej zastosowana w jego procesorze może nadal powodować taką decyzję. Jest to mało prawdopodobne, ale nie do pomyślenia.
Automatico