Przepraszam za długi post, ale chciałem załączyć wszystko, co uważałem za istotne za pierwszym razem.

Czego chcę

Wdrażam równoległą wersję Krystalicznych metod podprzestrzeni dla gęstych matryc. Głównie GMRES, QMR i CG. Zdałem sobie sprawę (po profilowaniu), że moja procedura DGEMV była żałosna. Postanowiłem więc skoncentrować się na tym, izolując to. Próbowałem uruchomić go na 12-rdzeniowym komputerze, ale poniższe wyniki dotyczą 4-rdzeniowego laptopa Intel i3. Trend nie ma dużej różnicy.

Moje KMP_AFFINITY=VERBOSEwyniki są dostępne tutaj .

Napisałem mały kod:

size_N = 15000
A = randomly_generated_dense_matrix(size_N,size_N); %Condition Number is not bad
b = randomly_generated_dense_vector(size_N);
for it=1:n_times %n_times I kept at 50 
 x = Matrix_Vector_Multi(A,b);
end

Wierzę, że to symuluje zachowanie CG przez 50 iteracji.

Co próbowałem:

Tłumaczenie

Pierwotnie napisałem kod w Fortranie. Przetłumaczyłem to na C, MATLAB i Python (Numpy). Nie trzeba dodawać, że MATLAB i Python byli okropni. Nieoczekiwanie, C było lepsze od FORTRAN o sekundę lub dwie dla powyższych wartości. Konsekwentnie

Profilowy

Wyprofilowałem mój kod, aby działał i działał przez 46.075kilka sekund. To było, gdy MKL_DYNAMIC był ustawiony naFALSE i wszystkie rdzenie były używane. Jeśli jako prawdę użyłem MKL_DYNAMIC, tylko (około) połowa rdzeni była używana w danym momencie. Oto kilka szczegółów:

Address Line    Assembly                CPU Time

0x5cb51c        mulpd %xmm9, %xmm14     36.591s

Najbardziej czasochłonnym procesem wydaje się być:

Call Stack                          LAX16_N4_Loop_M16gas_1
CPU Time by Utilization             157.926s
CPU Time:Total by Utilization       94.1%
Overhead Time                       0us
Overhead Time:Total                 0.0%    
Module                              libmkl_mc3.so   

Oto kilka zdjęć:

Wnioski:

Jestem prawdziwym początkującym w profilowaniu, ale zdaję sobie sprawę, że przyspieszenie wciąż nie jest dobre. Kod sekwencyjny (1 rdzeń) kończy się w 53 sekundy. To przyspieszenie mniejsze niż 1,1!

Prawdziwe pytanie: Co powinienem zrobić, aby poprawić moje przyspieszenie?

Rzeczy, które moim zdaniem mogą pomóc, ale nie jestem pewien:

• Implementacja Pthreads
• Implementacja MPI (ScaLapack)
• Strojenie ręczne (nie wiem jak. Proszę polecić zasób, jeśli to zasugerujesz)

Jeśli ktoś potrzebuje więcej (szczególnie dotyczących pamięci) szczegółów, daj mi znać, co powinienem uruchomić i jak. Nigdy wcześniej nie profilowałem pamięci.

Twoja matryca ma rozmiar 15 000 x 15 000, więc masz w niej 225 mln elementów. To daje około 2 GB pamięci. Jest to znacznie więcej niż wielkość pamięci podręcznej procesora, dlatego należy ją ładować całkowicie z pamięci głównej przy każdym pomnożeniu macierzy, co zapewnia około 100 GB transferu danych oraz to, czego potrzebujesz dla wektorów źródłowych i docelowych.

Maksymalna przepustowość pamięci w i3 wynosi około 21 GB / s w oparciu o specyfikacje Intela, ale jeśli spojrzysz w Internecie, przekonasz się, że co najwyżej połowa z nich jest naprawdę dostępna. Zatem przynajmniej można oczekiwać, że test będzie trwał 10 sekund, a faktyczny pomiar 45 sekund nie jest tak daleko od tego znaku.

Jednocześnie wykonujesz około 10 miliardów mnożników zmiennoprzecinkowych i dodaje. Biorąc pod uwagę, powiedzmy, 10 cykli zegara dla kombinacji i częstotliwość taktowania 3 GHz, wyjdziesz na około 30 sekund. Oczywiście mogą działać równolegle z spekulacyjnymi ładowaniami pamięci, jeśli pamięć podręczna jest sprytna.

Podsumowując, powiedziałbym, że nie jesteś zbyt daleko od celu. Czego byś się spodziewał?

Jak sobie radzisz mnożąc wektor macierzowy? Podwójna pętla ręcznie? A może połączenia z BLAS? Jeśli używasz MKL, zdecydowanie polecam korzystanie z procedur BLAS w wersji z wątkami.

Z ciekawości możesz również skompilować własną zestrojoną wersję ATLAS- a i zobaczyć, jak to działa na twój problem.

Aktualizacja

Po dyskusji w komentarzach poniżej okazuje się, że twój Intel Core i3-330M ma tylko dwa „prawdziwe” rdzenie. Dwa brakujące rdzenie są emulowane za pomocą hiperwątkowania . Ponieważ w rdzeniach hiperwątkowych zarówno magistrala pamięci, jak i jednostki zmiennoprzecinkowe są wspólne, nie uzyskasz żadnego przyspieszenia, jeśli którykolwiek z tych dwóch czynników będzie czynnikiem ograniczającym. W rzeczywistości użycie czterech rdzeni prawdopodobnie nawet spowolni sytuację.

Jakie wyniki uzyskujesz na „tylko” dwóch rdzeniach?

Mam wrażenie, że porządkowanie według rzędów jest optymalne dla tego problemu pod względem czasu dostępu do pamięci, użycia linii pamięci podręcznej i braków TLB. Wydaje mi się, że twoja wersja FORTRAN używała zamiast tego porządkowania kolumn, co może wyjaśniać, dlaczego jest konsekwentnie wolniejsze niż wersja C.

$b$ nie jest przechowywany w pamięci podręcznej. Możesz sprawdzić, czy obserwujesz taką samą (efektywną) przepustowość pamięci dla rozmiaru_N = 15000 niż dla wielkości_N = 5000. Jeśli to zrobisz, istnieje spora szansa, że ​​kod jest już optymalny i że przepustowość pamięci twojego systemu jest po prostu nie tak wspaniale.

Możesz także przetestować prędkość, jeśli po prostu zsumujesz wszystkie elementy macierzy w jednej pętli zamiast mnożenia wektora macierzy. (Możesz rozwinąć pętlę o współczynnik 4, ponieważ brak asocjatywności dodawania może uniemożliwić kompilatorowi wykonanie tej optymalizacji.)