Jak zrównolegla się algorytmy - projektowanie.pdf

(815 KB) Pobierz
721799974 UNPDF
Jak zrównolegla się algorytmy - projektowanie
algorytmów równoległych
1
Dekompozycja problemu
● Pierwszym krokiem w zrównoleglaniu algorytmu jest podział problemu na
zadania (ang. task), które mogą być wykonane niezależnie. Podział ten
nazywany jest dekompozycją .
● Problem może być podzielony na zadania na wiele różnych sposobów.
● Zadania mogą być takich samych bądź też różnych rozmiarów.
● Podział zbioru na zadania może być zilustrowany w postaci grafu skierowanego,
którego wierzchołki odpowiadają zadaniom, a krawędzie wskazują, że wynik
jednego z zadań jest potrzebny przez drugie.
● Graf ten nazywamy grafem zależności zadań (ang. task dependency graph.)
2
Przykład: mnożenie macierzy i wektora
● y=Ab, gdzie b oraz y to n-elementowe wektory, A jest macierzą nxn.
● Przypomnienie i-ty element wektora y obliczamy mnożąc i-ty wiersz macierzy A
przez wektor b.
● Jedno zadanie = obliczenie jednego elementu y.
3
721799974.001.png
Mnożenie macierzy i wektora
● Obliczenie jednego elementu n-elementowego wektora y, będącego iloczynem
macierzy nxn A i wektora n-elementowego b, jest niezależne od obliczenia
pozostałych elementów y.
● Wykorzystując ten fakt możemy podzielić problem na n zadań.
● Pomimo, że zadania współdzielą dane (wektor b), to nie ma pomiędzy nimi
żadnych zależności sterujących. Żadne z zadań nie potrzebuje wyniku
jakiegokolwiek z pozostałych. Oznacza to, że żądne z zadań nie musi czekać na
wykonanie pozostałych.
● Graf zależności zadań składa się z n wierzchołków i nie ma krawędzi.
● Każde zadanie ma taki sam rozmiar, jeżeli chodzi o liczbę elementarnych
operacji arytmetycznych.
● Pytanie: czy problemu nie udałoby się podzielić na więcej zadań ?
4
Przykład: zapytanie do bazy danych
● Rozwążmy zapytanie:
MODEL=”CIVIC” AND YEAR=2001 AND (COLOR=”GREEN” OR
COLOR=”WHITE”)
skierowane do następującej tabeli w bazie danych:
ID#
Model
Year
Color
Dealer
Price
4523
Civic
2002
Blue
MN
$18,000
3476
Corolla
1999
White
IL
$15,000
7623
Camry
2001
Green
NY
$21,000
9834
Prius
2001
Green
CA
$18,000
6734
Civic
2001
White
OR
$17,000
5342
Altima
2001
Green
FL
$19,000
3845
Maxima
2001
Blue
NY
$22,000
8354
Accord
2000
Green
VT
$18,000
4395
Civic
2001
Red
CA
$17,000
7352
Civic
2002
Red
WA
$18,000
5
721799974.002.png

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin