Jaki jest najlepszy sposób określenia liczby niezerowych w rzadkim mnożeniu macierzy?

17

Zastanawiałem się, czy istnieje szybka i skuteczna metoda wcześniejszego znalezienia liczby niezerowych dla operacji rzadkiego mnożenia macierzy, zakładając, że obie macierze są w formacie CSC lub CSR.

Wiem, że jest jeden w pakiecie smmp, ale potrzebuję czegoś, co jest już zaimplementowane w C lub C ++.

Każda pomoc będzie mile widziana. Z góry dziękuję.

Recker
źródło
czy macierze mają jakąkolwiek symetrię lub strukturę do lokalizacji ich niezerowych wpisów?
Godric Seer,
@GodricSeer ... nie Mówię tylko o ogólnych macierzach rzadkich. Matlab ma nnz (A), gdzie A jest metodą macierzy rzadkich w celu znalezienia liczby niezerowych. Zastanawiałem się, czy istnieje taka metoda.
Recker,
Osobiście nie mogę wymyślić żadnego sposobu, aby obliczyć tę liczbę, która byłaby niższa, niż zwykłe pomnożenie macierzy bez wykorzystania jakiejś symetrii lub struktury. Zakładam, że chcesz tego przydzielić pamięć przed wykonaniem mnożenia?
Godric Seer,
Znalazłem również ten artykuł, który opisuje, jak oszacować liczbę na iloczynie boolowskim (co jest identyczne z liczeniem elementów w dowolnym iloczynie macierzy).
Godric Seer,
@ GodricSeer..Tak masz rację Potrzebuję dokładnej liczby tylko do alokacji pamięci wynikowej macierzy. Dziękuję za link do papieru. Może to na chwilę zacząć w pewnym kierunku.
Recker

Odpowiedzi:

14

Możesz po prostu symulować iloczyn macierzowo-matrycowy, tworząc iloczyn dwóch wzorców sparsity - tzn. Wziąłeś pod uwagę wzór sparsity (który jest przechowywany w oddzielnych tablicach w formacie CSR) jako matrycę zawierającą zero lub jeden w każdy wpis. Wykonanie tego symulowanego produktu wymaga jedynie utworzenia ioperacja na tych zerach i zerach, a zatem jest znacznie szybsza niż rzeczywisty produkt macierz-macierz - w rzeczywistości wszystko, co musisz zrobić, to przejść przez rzędy i kolumny dwóch macierzy i sprawdzić, czy jest co najmniej jeden wpis w wiersz i kolumna, którą mnożymy, gdzie obie macierze są niezerowe. Jest to tania operacja - w każdym razie znacznie tańsza niż faktyczne mnożenie liczb zmiennoprzecinkowych w rzeczywistym produkcie, co wymaga nie tylko wykonywania arytmetyki zmiennoprzecinkowej (kosztowne), ale także odczytywania rzeczywistych liczb zmiennoprzecinkowych z pamięci ( nawet droższe, ale nie potrzebujesz tego przy pomnażaniu wzorca rzadkości, ponieważ niezerowe wartości macierzy są przechowywane osobno w CSR).

Wolfgang Bangerth
źródło
6
Nazywa się to mnożeniem symbolicznym. Niekoniecznie jest to tańsze niż mnożenie numeryczne, zwłaszcza równolegle, ale należy to zrobić tylko raz na wzór sparityzacji. Wiele algorytmów wykona operację wiele razy z różnymi wartościami liczbowymi, ale z tym samym wzorem rzadkości, w którym to przypadku można ponownie użyć symbolicznego mnożenia.
Jed Brown
To fajny pomysł, ale biorąc pod uwagę miliony tranzystorów, które robią float * float równolegle, mówimy tylko o oszczędności prędkości 50% lub mniej więcej tutaj.
Evgeni Sergeevev
1
@EvgeniSergeev - nie chodzi o oszczędności w obliczeniach, ale o oszczędności w transferze pamięci. Ponieważ spędzasz dziś 80% lub więcej czasu na przenoszeniu pamięci na rzadkie mnożenie macierzy, prawdopodobnie zyskasz znacznie, jeśli nie będziesz musiał czytać / zapisywać danych zmiennoprzecinkowych z / do pamięci.
Wolfgang Bangerth,
Czy wyraźnie podasz złożoność swojej metody? Jeśli jest m na k , wydaje mi się, że twoja metoda wymaga pracy O ( m k ) , prawda? domkO(mk)
Carl Christian
@CarlChristian - musiałbym opracować szczegóły, ale z pewnością nie może to być . Musi uwzględniać liczbę niezerowych na wiersz. Jeśli masz średnio p nonzerów w każdym rzędzie, a dla uproszczenia, jeśli masz m = k , to wyobrażam sobie, że powinieneś być w stanie zaimplementować metodę w czymś takim jak O ( m p log p ) lub podobnym. To o wiele lepsze niż O ( m 2 ) . O(mk)pm=kO(mplogp)O(m2))
Wolfgang Bangerth
13

Właściwie napisałem oryginalny kod w Matlabie dla A * B, zarówno A, jak i B rzadki. Wstępne przydzielenie miejsca na wynik było rzeczywiście interesującą częścią. Zauważyliśmy to, na co wskazuje Godric - że znajomość liczby niezerowych w AB jest tak samo kosztowna jak obliczanie AB.

Pierwszą implementację rzadkiego Matlaba wykonaliśmy około 1990 r., Zanim opublikowano artykuł Edith Cohen, który dał pierwszy praktyczny, szybki sposób na dokładne oszacowanie wielkości AB. Zebraliśmy mniejszy estymator wielkości i jeśli zabraknie miejsca w połowie obliczeń, podwoimy alokację i skopiujemy częściowo obliczony wynik.

Nie wiem, co jest teraz w Matlabie.

Inną możliwością byłoby obliczenie AB jednej kolumny na raz. Każda kolumna może być tymczasowo przechowywana w rzadkim akumulatorze (wyjaśnienie ich znajduje się w rzadkim dokumencie Matlab), a miejsce przydzielone do przechowywania dokładnie znanego rozmiaru kolumny wynikowej. Wynik byłby w rozproszonej skompresowanej rzadkiej formie kolumny - każda kolumna w CSC, ale bez ciągłości międzykolumnowej - przy użyciu 2 wektorów numcoli długości (początek kolumny, długość kolumny) zamiast jednego jako metadanych. Jest to forma przechowywania, która może być warta obejrzenia; ma inną siłę - możesz wyhodować kolumnę bez ponownego przydziału całej matrycy.

Rob Schreiber
źródło
Cóż, jeśli chodzi o moją implementację GPU, najpierw znalazłem niezerową strukturę, a potem znajdowałem rzeczywistą macierz. Wydajność była okropna, jak oczekiwano. Myślę, że używają metody opisanej w tej książce, aby skutecznie pomnożyć dwie rzadkie macierze w MATLAB.
Recker
2
Naprawdę fajne, dziękuję za historyczną perspektywę i zapraszamy do scicomp :)
Aron Ahmadia,
4

W tym artykule opisano algorytm przybliżania wielkości wypadkowej z iloczynu macierzy dwóch rzadkich macierzy.

Problem ze znalezieniem dokładnej liczby niezerowych wpisów w rzadkim mnożeniu macierzy polega na tym, że każdy wynikowy wynik zależy od interakcji dwóch wektorów, z których oba prawdopodobnie zawierają co najmniej kilka niezerowych elementów. Dlatego, aby obliczyć liczbę, musisz ocenić operacje logiczne na parze wektorów dla każdego elementu w wyniku. Problem polega na tym, że wymaga wielu operacji podobnych do liczby operacji potrzebnych do obliczenia samego produktu macierzowego. W moich komentarzach wspomniałem o możliwości wykorzystania niektórych struktur w niezerowych elementach pierwotnych macierzy, jednak te same exploity mogłyby zostać wykorzystane do zmniejszenia pracy wykonanej również przy mnożeniu macierzy.

Lepiej byłoby użyć powyższego papieru do przeszacowania wymagań pamięci, wykonać pomnożenie, a następnie skrócić przydzieloną pamięć lub przenieść uzyskaną macierz do tablicy o odpowiednio większym rozmiarze. Ponadto rzadkie produkty matrycowe nie są rzadkim zjawiskiem i prawie gwarantowałbym, że problem ten został już wcześniej rozwiązany. Trochę zagłębiając się w niektóre biblioteki bibliotek macierzowych typu open source powinny prowadzić do algorytmów używanych do wstępnego przydzielania pamięci.

Godric Seer
źródło
0

Czy w przypadku CSR lub CSC masz gwarancję, że tablica elementów macierzy nie ma już zer? W takim przypadku łatwo jest dowiedzieć się, ile jest elementów niezerowych, używając czegoś podobnego do:

int nnz = sizeof(My_Array)/sizeof(long int);

Jeśli jednak tak nie jest (wydaje się to zbyt łatwe), możesz spróbować zmniejszyć . Jeśli tablica elementów macierzy jest bardzo duża, może to być najbardziej efektywny sposób obliczenia liczby elementów niezerowych. Wiele równoległych bibliotek C / C ++, takich jak Thrust (biblioteka CUDA) lub OpenCL (do których nie potrzebujesz GPU), obsługuje redukcje warunkowe - dla każdego elementu dodaj wynik Condition(Element). Jeśli ustawisz warunek na Element != 0to, zsumujesz liczbę niezerowych elementów. Możesz także usunąć elementy o zerowej wartości z tablicy elementów, tablicy wskaźników wierszy / kolumn i dostosować wskaźniki kolumn / wierszy.

limonki
źródło
dzięki za odpowiedź ... ale miałem na myśli niezerowe w A * B, gdzie A i B są rzadkimi macierzami. Potrzebuję z góry liczby niezerowych, aby móc przydzielić dokładną ilość pamięci do przechowywania wynikowej macierzy.
Recker,
0

Najprostszym sposobem na wdrożenie CSR jest wypróbowanie

std::vector< std::map<int, complex<float>> > 

reprezentować macierz. W takim przypadku tak naprawdę nie będziesz się martwić liczbą niezerowych elementów, wszystko jest dostępne za pośrednictwem

std::map< int, complex<float> >::iterator

w każdym rzędzie. Najlepsza ..


źródło
2
STL, ponieważ kiedy myślałeś, że twoje rzadkie procedury macierzowe nie mogą być spowolnione.
Jed Brown