Aktualna wersja na dzień 08:48, 28 sie 2023

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

Ćwiczenie: Szybkie mnożenie macierzy przez wektor

Zaimplementuj samodzielnie algorytm mnożenia macierzy kwadratowej przez wektor:

y_{i} = \sum_{j = 1}^{N} a_{i j} 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

Ć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

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 $A x = 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

Rozwiązanie

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.

@@ Linia 1: / Linia 1: @@
 <!--
 Konwertowane  z pliku LaTeX przez latex2mediawiki, zob. http://www.ii.uj.edu.pl/&nbsp;pawlik1/latex2mediawiki.php.
@@ Linia 35: / Linia 34: @@
 Zaimplementuj samodzielnie algorytm mnożenia macierzy kwadratowej przez wektor:
-<center><math>\displaystyle
+<center><math>
 y_i = \sum_{j=1}^N a_{ij}x_j
 </math></center>
-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.
+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.
 <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">
@@ Linia 68: / Linia 67: @@
 Zaimplementuj algorytm Strassena mnożenia dwóch macierzy i porównaj czas jego działania z czasem działania procedury  <code style="color: #903">DGEMM</code>, najlepiej zoptymalizowanej na Twoją architekturę.
-testuj dla macierzy wymiaru <math>\displaystyle 2^k</math>, gdzie <math>\displaystyle k=0,\ldots,11</math>.
+testuj dla macierzy wymiaru <math>2^k</math>, gdzie <math>k=0,\ldots,11</math>.
 <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">
@@ Linia 83: / Linia 82: @@
 <div class="exercise">
-Rozwiąż układ równań liniowych <math>\displaystyle Ax=b</math> programując, niczym [http://www.gajdaw.pl/wiersze/julian_tuwim/zosia_samosia.html  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
+Rozwiąż układ równań liniowych <math>Ax=b</math> programując, niczym [http://www.gajdaw.pl/wiersze/julian_tuwim/zosia_samosia.html  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
 <code style="color: #903">DGESV</code>, najlepiej wspartą dobrze podrasowanymi BLASami.
 <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">
-<div style="font-size:smaller; background-color:#f9fff9; padding: 1em"> To zadanie to wyzwanie! </div>
+<div style="font-size:smaller; background-color:#f9fff9; padding: 1em"> To zadanie to prawdziwe wyzwanie! No tak, namawiamy cię do zmierzenia się z LAPACKiem i ATLASem... </div>
 </div></div>
@@ Linia 93: / Linia 92: @@
 <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none"><div style="margin-left:1em">
-No tak, namawiamy cię do zmierzenia się z LAPACKiem i ATLASem....
 Prościutki program --- po prostu tłumaczący [[MN05#Rozkład LU metodą eliminacji Gaussa|algorytm z wykładu]] bezpośrednio
 na C --- u nas spisał
-się (dla macierzy wymiaru <math>\displaystyle N=1\ldots 1024</math>) następująco:
+się (dla macierzy wymiaru <math>N=1\ldots 1024</math>) następująco:
-[[Image:MNdegsvtiming.png|thumb|550px|center|Prosty solver w C kontra LAPACK i LAPACK z ATLASem. Zwróć uwagę na piki zwykłego kodu dla <math>\displaystyle N</math> będących potęgami dwójki]]
+[[Image:MNdegsvtiming.png|thumb|550px|center|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]]
 [[Image:MNdegsvtiminglogscale.png|thumb|550px|center|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 <strong>50 razy wolniejszy</strong> od kodu korzystającego z LAPACKa i ATLASa.]]
 </div></div></div>

MN06LAB: Różnice pomiędzy wersjami

Aktualna wersja na dzień 08:48, 28 sie 2023

BLAS, LAPACK, pamięć podręczna

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia