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

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;
   }
 }

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ść.

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.

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.

Louis Brandy napisał dwa posty na blogu analizujące dokładnie ten problem:

Więcej szaleństwa pamięci podręcznej i wydajności obliczeniowej - studium przypadku dla początkujących z kilkoma interesującymi statystykami i próbami bardziej szczegółowego wyjaśnienia zachowania, rzeczywiście sprowadza się do ograniczeń rozmiaru pamięci podręcznej.

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 .

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.

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.

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.

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.

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.