Główny wiersz a główny układ kolumn w kolumnie

Czy przy programowaniu obliczeń macierzy gęstej istnieje jakiś powód, aby wybrać układ z rzędami większymi niż z układem z kolumnami?

Wiem, że w zależności od układu wybranej matrycy musimy napisać odpowiedni kod, aby efektywnie wykorzystać pamięć podręczną do celów związanych z prędkością.

Układ rzędów wydaje się bardziej naturalny i prostszy (przynajmniej dla mnie). Ale główne biblioteki, takie jak LAPACK, które są napisane w Fortranie, używają głównego układu kolumn, więc musi być jakiś powód, aby dokonać tego wyboru.

Główny układ kolumn jest schematem używanym przez Fortran i dlatego jest używany w LAPACK i innych bibliotekach.

Zasadniczo dostęp do elementów tablicy w kolejności, w jakiej są ułożone w pamięci, jest znacznie bardziej wydajny pod względem wykorzystania przepustowości pamięci i wydajności pamięci podręcznej. W zależności od tego, jak przechowywane są macierze, będziesz chciał wybrać algorytmy, które to wykorzystają.

Pamięć wewnętrzna głównego formatu kolumny

W próżni bez uwzględnienia jakiegokolwiek istniejącego oprogramowania nie ma powodu, aby preferować durę kolumny zamiast duracji rzędu z punktu widzenia kodu. Jednak większość literatury matematycznej jest napisana w sposób, który grupuje wektory w macierz, przechowując je jako kolumny zamiast wierszy. Na przykład, gdy napiszesz pełne równanie wartości własnej , $AX=X\Lambda$$X$macierz zawiera wszystkie wektory własne zapisane w kolumnach. Tak naprawdę nigdy nie widzisz tego napisanego w inny sposób (chociaż słyszę, że ludzie statystyki lubią wektory wierszowe). Dlatego naturalne było, że najwcześniejsze oprogramowanie przyjęło główny format kolumny, więc jeśli masz macierz, która jest zbiorem wektorów, przechowywanie dowolnego pojedynczego wektora jest ciągłe. Tak więc wyobrażam sobie, że tradycja została właśnie przeniesiona do dnia dzisiejszego, a jeśli chcesz wchodzić w interakcje z dawnym Fortranem, chcesz użyć kolumny major. Tak więc prawie cała wysoce wydajna numeryczna algebra liniowa jest wykonywana w kolumnie głównej.

Powodem, dla którego C jest głównym rzędem, jest w pewnym stopniu konsekwencja jego składni tablicowej; deklarujesz tablicę 3 wiersze na 2 kolumny jako double a[3][2], a później indeksy zmieniają się szybciej niż wcześniejsze indeksy, co w przypadku tablic 2D sprawia, że ​​wiersz jest większy. Połącz to z naturalną zachodnią kolejnością czytania od lewej do prawej, dzięki czemu duże rzędy wydają się bardziej naturalne.

Porządek kolumnowy wydaje się bardziej naturalny. Załóżmy na przykład, że jeśli chcesz zapisać film do pliku obraz po obrazie, to używasz kolejności kolumn, a to jest bardzo intuicyjne i nikt nie zapisałby go w kolejności rzędów większych.

Jeśli jesteś programistą w C / C ++, powinieneś użyć bibliotek wyższego poziomu dla macierzy (Eigen, Armadillo, ...) z domyślną kolejnością dużych kolumn. Tylko maniak używałby surowych wskaźników C w kolejności rzędów głównych, chociaż C / C ++ oferuje coś, co przypomina indeksowanie macierzy.

Dla uproszczenia wszystko o kolejności rzędów większych powinno być uważane za co najmniej dziwnie uformowane. Kawałek po plasterku jest po prostu porządkiem naturalnym i oznacza porządek według kolumny (jak Fortran). Nasi ojcowie / matki mieli bardzo dobre powody, dla których to wybrali.

Niestety, zanim stało się jasne, utworzono kilka interesujących bibliotek w kolejności rzędów, prawdopodobnie z powodu braku doświadczenia.

Aby wyjaśnić, przypomnijmy sobie definicję kolejności rzędów głównych, w której prawy indeks zmienia się szybciej w jednym kroku przez pamięć, np. A (x, y, z), jest to indeks Z, oznacza to, że w pamięci piksele z różnych wycinków sąsiadują ze sobą, co nie nie chcę. Dla filmu A (x, y, t) ostatnim indeksem jest czas t. Nietrudno wyobrazić sobie, że po prostu niemożliwe jest zapisanie filmu w trybie rzędowym.

Wybór indeksowania głównych wierszy / głównych kolumn może mieć znaczący wpływ na wydajność ze względu na sposób działania pamięci i pamięci podręcznej oraz sposób przekształcania wielu indeksów w indeks liniowy. Pamięć wewnętrzna jest pojedynczą jednowymiarową tablicą, a elementy a$m\times n$ matryca zostanie ułożona liniowo:

• element $m_{i,j}$ będą przechowywane w indeksie $i \times m + j$ jeśli używana jest kolejność rzędów głównych
• element $m_{i,j}$ będą przechowywane w indeksie $j \times n + i$ jeśli używana jest kolejność według kolumny

Teraz wyobraź sobie następujący algorytm:

for i from 1 to m
   for j from 1 to n
      do something with m(i,j)

Jeśli zostanie użyta kolejność rzędów głównych, przejdzie ona przez wszystkie indeksy liniowe $i \times m + j$sekwencyjnie, co skutkuje dobrą lokalizacją pamięci, natomiast jeśli zastosowany zostanie porządek według kolumny, kolejne dostępy do pamięci będą rozproszone w pamięci. Konsekwencje mogą być dramatyczne, zwłaszcza gdy na scenę wkracza pamięć wirtualna / wymiana.

Wnioski:

1. tak, ma to znaczenie, ale wybór zależy od sposobu uzyskiwania dostępu do danych. W poprzednim przykładzie, jeśli użyto kolejności kolumn, możesz po prostu zamienić dwie pętle.

2. ogólna zasada: szybko zmieniający się indeks powinien być mapowany na kolejne lokalizacje w pamięci.

3. co ważniejsze, mierzenie / porównywanie wpływu wyboru ma fundamentalne znaczenie, ponieważ zależy od wielu parametrów (rozmiar danych, rozmiar pamięci podręcznej, sposób, w jaki używany język mapuje wiele indeksów na indeks liniowy, sposób działania system zarządza pamięcią wirtualną, sposób zagnieżdżania pętli w bibliotece algebry liniowej, której używasz ...)