SCIAGA2.pdf

1.1 Blokowanie rejestrów 2x2

Okazuje sie ze przy przesyłce danych pamiec podreczna – rejestry

– pamiec podreczna zastosowanie techniki blokowej zmniejsza ilosc

ładowan rejestrów (register’s reuse) i tez słuzy do podniesienia

wydajnosci algorytmu.

Blokowanie rejestrów zmniejsza ilosc przesyłek danych cache-rejestr-cache

w skutek utrzymania czesci danych w rejestrach. To powoduje zwiekszenie

współczynnika ilosc arytmetycznych operacji/ilosc przesyłek danych na

poziomie pamiec podreczna – rejestr – pamiec podreczn

Im wiecej rejestrów double zawiera procesor, tym wiekszy rozmiar bloku

uda sie zrealizowac, tym bardziej wysoka bedzie wydajnosc.

W petle wewnetrznej:

Ilosc ładowan w rejestry: 4

Ilosc operacji arytmetycznych: 8 (4 mnozenia + 4 dodawania)

Q=2

To jest znacznie lepiej, niz dla poprzedniego algorytmu, przeciez potrzebuje

obecnosci 8 rejestrów typu double.

Naiwny:

W petle wewnetrznej:

Ilosc ładowan rejestrów: 2

1 odczyt aik + 1 odczyt bik

Ilosc operacji arytmetycznych: 2

1 mnozenie + 1 dodawanie

1.2 Pakowanie IMKL, mnożenie macierzy

Pakowanie Intel MKL: góra – poziom macierzy; dół – poziom bloków

mr × nr - schemat blokowania rejestrów; lb – szerokosc paneli. Z punktu

widzenia wydajnosci obliczen przy wykonaniu petli wewnetrznej w cache L1

maja byc umieszczone bloki danych, zakreskowane na rys, plus blok mrxnr

2. Metoda blokowa Choleskiego

Umieszczanie danych w pamięci:

Rozdzielenie na bloki nadaje mozliwosc na drugim i trzecim etapach

utrzymac poziom BLAS-III – zastapic procedury mnozenia macierzy przez

wektor (BLAS-I – BLAS - II) procedurami mnozenia macierzy przez macierz.

5. Uwarunkowanie wstępne – cechy metod interacyjnych

Prekonditioning– to specjalnie skonstruowany operator, przeznaczony

do przyspieszenia zbieznosci.

Oszacowanie ilosci operacji zmiennoprzecinkowych dla metod

iteracyjnych wynosi rzedu C1·N, gdzie C1 zalezy od zdolnosci

prekonditioningu polepszyc uwarunkowanie układu równan.

Z tego wynika, ze dla kazdego problemu istnieje taki rozmiar zadania NA i

taki punkt A, zaczynajac od którego przy zwiekszeni N iteracyjna metoda

staje bardziej skuteczna od bezposredniej (jesli ta metoda iteracyjna

demonstruje stabilna zbieznosc dla podanej klasy zagadnien).

Metody iteracyjne doprowadzaja do rozwiazania przyblizonego z podana

dokładnoscia za pewna ilosc iteracji – ilosc operacji nie pozostaje

przewidywana z góry.

Główna cecha metod iteracyjnych jest zbieznosc. Jesli dla zagadnienia

podanego proces iteracyjny sie zbiega za nie wielka ilosc iteracji (zwykłe

ilosc iteracji odnosza do rozmiary zadania), mówimy ze zbieznosc jest

szybka. W przeciwnym przypadku – wolna. Czesto wystepuje sytuacje, gdy

ogóle nie da sie osiagnac podanej dokładnosci rozwiazania – mówimy o

braku zbieznosci.

1. Współczynnik wydajności dla mnożenia macierzy przez macierz

metodą blokową.

5. obliczenia iloczynu skalarnego dwóch wektorów w trybie

wielowątkowym

Coarse granularity

Ilosc podziałów danych jest taka sama, jak ilosc procesorów. Zabezpiecza

load

balance (zrównowazenie pomiedzy watkami).

Narzut OS na tworzenie i planowanie watków jest minimalny. Zwiazek

komunikacyjny pomiedzy watkami jest słaby. Synchronizacja – na poziomie

sygnałów przy zakonczeni watków. Operacje „reduction” (sumowanie

wyników

działania kazdego watku po ich zakonczeniu – sekwencyjna czesc kodu) –

minimalne.

Dane w pamieci dla kazdego watku sa umieszczone ciagłe – brak skoków

danych, minimalna ilosc przeładowan pamieci podręcznej

Ilosc podziałów danych istotnie wieksza od ilosci procesorów. Zabezpiecza

load balance (zrównowazenie pomiedzy potokami). Ilosc potoków jest taka

sama jak ilosc procesorów.

Narzut OS na tworzenie i planowanie potoków jest minimalny.

Synchronizacja – na poziomie sygnałów przy zakonczeni potoków. Operacje

„reduction” (sumowanie wyników działania kazdego potoku po ich

zakonczeniu

– sekwencyjna czesc kodu) – minimalne. Tu zakładamy, ze potoki nie beda

komunikowali pomiedzy soba przy przejsciu od jednego podziału danych do

innego – dla tego i coarse granularity.

Dane dla kazdego potoku sa pobierane ze skokami – czeste przeładowanie

pamieci podrecznej - powoduje drastyczny spad wydajności

Fine granularity

Ilosc podziałów danych istotnie wieksza od ilosci procesorów. Zabezpiecza

load balance (zrównowazenie pomiedzy potokami). Ilosc potoków jest taka

sama jak ilosc podziałów danych.

Narzut OS na tworzenie i planowanie potoków jest duzy. Synchronizacja –

poziomie sygnałów przy zakonczeni potoków. Operacje „reduction”

(sumowanie

wyników działania kazdego potoku po ich zakonczeniu – sekwencyjna czesc

kodu) – duze.

Dane dla kazdego potoku sa pobierane ciagłe, przeciez stack kazdego

potoku jest lokalny – tworzenie nowego potoku powoduje umieszczenie

jego

stack’u w pamieci głównej i ładowanie w pamiec podreczna - powoduje

drastyczny spad wydajnosci.

Dla zabezpieczenia poprawnosci danych globalnych jest koniecznie

uzycie synchronizacji. Przeciez synchronizacja istotnie zmniejsza wydajnosc

kodu i jego zdolnosc do przyspieszenia przy zwiekszeniu ilosci procesorów

(speed up).

Projektujemy bezpieczny algorytm tak, zeby minimalizowac synchronizacje

o Uzywamy dane lokalne potoku

o Dla dynamicznej alokacji pamieci – Thread Local Storage (TLS)

o Dla synchronizacji w architekturze SMP – sekcje krytyczne.

o Spin-blocking

Dla małych tablic danych skalowalność tego algorytmu jest wysoka. Wynika

to z faktu, że wszystkie dane ładowane są do pamięci cache. Dla dużego

zadania wzrost przyśpieszenia jest o wiele mniejszy. Związane jest to z

ograniczoną przepustowością magistrali pamięci (wąskie gardło).

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: