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

16

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.

smilingbuddha
źródło
Jeśli weźmiemy pod uwagę obliczenie b = A * x z wektorem kolumny x, dla A-dur rzędu możemy zastosować iloczyn wewnętrzny wektorów, A (i,:) ^ T x, aby otrzymać b (i); dla głównych kolumn możemy potrzebować tylko wektorów mnożących skalarnie, sum_i A (:, i) x (i). Wydaje mi się, że kolumna główna jest znacznie lepsza! Co myślisz?
Hui Zhang
Wytrenuj się, aby polubić kolumny główne. Łatwo jest wizualizować wektory jako kolumny lub ich transpozycję jako wiersze. Ułatwia to wizualizację mnożenia macierzy i ułatwia śledzenie wielu opublikowanych obliczeń matematycznych.
Mike Dunlavey,

Odpowiedzi:

18

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 Pamięć wewnętrzna głównego formatu kolumny

Brian Borchers
źródło
11

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 , XZAX=XΛXmacierz 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.

Victor Liu
źródło
2
Myślę, że to kiepskie argumenty. Fakt, że ostatni wskaźnik w podwójnej liczbie [3] [2] '' zmienia się najszybciej, nie jest przypadkiem - była to świadoma decyzja projektowa w taki sam sposób, jak była świadoma decyzja projektowa w Fortran zrób to na odwrót, gdy masz prawdziwą tablicę (3,2).
Wolfgang Bangerth,
1
Co więcej, nie jest już prawdą, że prawie cała wysoce wydajna numeryczna algebra liniowa jest kolumna główna. Może to nadal dotyczyć BLAS i LAPACK, ale wcale nie jest prawdą w przypadku każdej większej biblioteki algebry liniowej, która pojawiła się w ciągu ostatnich 15 lat: na przykład zarówno PETSc, jak i Trilinos używają głównych formatów przechowywania rzadkich macierzy.
Wolfgang Bangerth,
Wiem, że konwencja C była świadomą decyzją, prawdopodobnie opartą na naturalnym porządku czytania. Miałem na myśli, że prawdopodobnie nie został zaprojektowany z myślą o numerycznej algebrze liniowej, co zbiegło się w tym, że jest to rząd rzędów. Po drugie, nie zamierzałem argumentować za rzadkimi matrycami, tylko gęstymi. W rzadkich przypadkach jest to trochę mieszane, zarówno ze skompresowanymi formatami wierszy, jak i kolumn.
Victor Liu
5
Nie wspominając o tym, ale C był pierwotnie językiem systemowym, opartym na wcześniejszych językach B i BCPL, działającym na systemach takich jak PDP-11, które początkowo nie miały liczb zmiennoprzecinkowych. Stwierdzenie, że zaprojektowali go z myślą o numeryce, jest dość trudne.
Victor Liu,
7
Byłem tam itp. Powodem, dla którego macierze w C najszybciej przesuwają ostatni indeks, jest to, że C nie ma macierzy. Ma wektory wektorów, które można transparentnie zaimplementować jako stałe bloki pamięci lub jako tablice wskaźników do tablic. Zgodność kolejności indeksów z Fortranem (zgaduję) nawet nie była na radarze Dennisa Ritchiego.
Mike Dunlavey,
2

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.

Paweł
źródło
2

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 am×n matryca zostanie ułożona liniowo:

  • element mja,jot będą przechowywane w indeksie ja×m+jot jeśli używana jest kolejność rzędów głównych
  • element mja,jot będą przechowywane w indeksie jot×n+ja 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 ja×m+jotsekwencyjnie, 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 ...)

BrunoLevy
źródło