MN06LAB

BLAS, LAPACK, pamięć podręczna

<<< Powrót do strony głównej przedmiotu Metody numeryczne

Oglądaj wskazówki i rozwiązania __SHOWALL__
Ukryj wskazówki i rozwiązania __HIDEALL__

Warto w tym momencie wrócić także do zadań z poprzedniego wykładu, wymagających wykorzystania BLASów i LAPACKa.

Ćwiczenie: Nie tylko ATLAS

Jeśli korzystasz z komputera z procesorem Intela lub AMD, masz możliwość sięgnięcia po procedury matematyczne zoptymalizowane właśnie na te architektury, zgromadzone w bibliotekach, odpowiednio, MKL i ACML. Spróbuj przeprowadzić testy wydajnościowe procedury mnożenia dwóch macierzy za pomocą takiej biblioteki w porównaniu do ATLASa dla Twojej architektury.

Wskazówka

Dokładnie przeczytaj manual i sprawdź, jakiego ułożenia macierzy w pamięci żądają te biblioteki!

Ćwiczenie: Szybkie mnożenie macierzy przez wektor

Zaimplementuj samodzielnie algorytm mnożenia macierzy kwadratowej przez wektor:

$y_i=\sum _{j=1}^N{a}_{ij}{x}_j$

i zbadaj czas jego działania. Następnie wykonaj to samo przy użyciu procedury BLAS (jakiej?). Sprawdź, na losowym wektorze i losowej macierzy, że w obu przypadkach dostajesz ten sam wynik. Jeśli jest taka potrzeba, spróbuj wprowadzić kilka optymalizacji do swojego kodu.

Wskazówka

Procedura BLAS, której potrzebujesz, to DGEMV.

Wskazówka

Pamiętaj, fortranowski BLAS oczekuje, że macierz będzie zadana kolumnami!

Wskazówka

Na pewno masz bardzo szybki komputer... Będziesz musiał mierzyć czasy dla macierzy dostatecznie dużego wymiaru!

Wskazówka

Sam kompilator może znacznie wspomóc szybkość twojego programu, dokonując samodzielnie pewnych optymalizacji. Jedną z nich może być opcja powodująca automatyczne rozwijanie pętli, gcc -funroll-loops test.c. Warto więc chyba zbadać dokładniej odpowiedni rozdział manuala twojego kompilatora, dotyczący

• opcji optymalizacyjnych dla obliczeń zmiennoprzecinkowych,
• opcji optymalizacyjnych specyficznych dla architektury twojego komputera (np. automatyczna wektoryzacja pętli).

Ćwiczenie: Strassen kontra DGEMM

Zaimplementuj algorytm Strassena mnożenia dwóch macierzy i porównaj czas jego działania z czasem działania procedury DGEMM, najlepiej zoptymalizowanej na Twoją architekturę.

testuj dla macierzy wymiaru $2^k$, gdzie $k=0,\dots ,11$.

Wskazówka

Może warto spróbować wariant hybrydowy metody Strassena, gdzie dostatecznie małe bloki macierzy mnożone są już procedurą DGEMM

Opis algorytmu Strassena znajdziesz np. w rozdziale 28 klasycznego podręcznika

• T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Wprowadzenie do algorytmów, Wydawnictwa Naukowo-Techniczne, Warszawa, 2005, ISBN 83-204-3149-2.

Ćwiczenie: Czy Twoje programy działają naprawdę szybko?

Rozwiąż układ równań liniowych $Ax=b$ programując, niczym Zosia-Samosia, wszystko od początku do końca w czystym C (a może wolałbyś w Pythonie?!). Porównaj czasy działania twojego programu i programu wywołującego po prostu procedurę biblioteczną LAPACKa DGESV, najlepiej wspartą dobrze podrasowanymi BLASami.

Wskazówka

To zadanie to wyzwanie!

Rozwiązanie

No tak, namawiamy cię do zmierzenia się z LAPACKiem i ATLASem....

Prościutki program --- po prostu tłumaczący algorytm z wykładu bezpośrednio na C --- u nas spisał się (dla macierzy wymiaru $N=1\dots 1024$) następująco:

Prosty solver w C kontra LAPACK i LAPACK z ATLASem. Zwróć uwagę na piki zwykłego kodu dla $N$ będących potęgami dwójki

Skala logarytmiczna pozwala lepiej ocenić różnice pomiędzy czasami wykonania. Prosty program w C jest około dziesięć razy wolniejszy od kodu korzystającego z LAPACKa i około 50 razy wolniejszy od kodu korzystającego z LAPACKa i ATLASa.