GRANULACJA PROCESÓW

Jest to stosunek czasu potrzebnego do wykonania elementarnej operacji, do czasu realizacji elementarnej operacji obliczeniowej.

• Komputery drobnoziarniste - duża granulacja czyli częste komunikacje między procesami (ang. fine grained)

• Komputery gruboziarniste - mała granulacja czyli rzadka komunikacja między procesami (ang. coarse grained)

TEORETYCZNY MODEL KOMPUTERA RÓWNOLEGŁEGO

Założenia

• n procesorów ma dostęp do n komórek wspólnej pamięci o dowolnych adresach

• dostęp jest realizowany w stałym czasie i identycznym dla procesów i adresów

PRAM - maszyna o równoległym dostępie swobodnym (ang. paralel random access mashine)

Klasy modelu PRAM

• równoczesny odczyt - CREW PRAM (current read exlusive write )

• równoczesny zapis - ERCW PRAM

• równoczesny odczyt i zapis - CRCW PRAM (current read current write)

Strategie:

• PRIORYTETY PROCESORÓW - procesorom przydziela się priorytety, „zwycięża” ten który ma najwyższy priorytet

• RÓWNOCZESNY ZAPIS TEJ SAMEJ WARTOŚCI - pozwala się wszystkim procesorom zapisać wartość, pod warunkiem, że jest ona taka sama

• ZAPIS SUMY (LOGICZNEJ) WARTOŚCI - zapisywana jest logiczna suma wartości

• niedozwolony równoczesny dostęp - ma największe ograniczenia w dostępie, większość komputerów jest właśnie tej klasy, inne są tylko symulowane

STRUKTURA SIECI POŁĄCZEŃ

- sieć połączeń międzyprocesorowych i SIMD

STATYCZNE SIECI POŁĄCZEŃ - połączenia między procesorami są pasywne i nie są rekonfigurowalne

Parametry:

p - liczba bezpośrednich połączeń

c - max liczba połączeń obsługiwalnych przez pojedynczy procesor

d - średnica sieci = liczba połączeń międzyprocesorowych składająca się na najdłuższą ścieżkę

1. SIEĆ O PEŁNYM POŁĄCZENIU (każdy z każdym)

----------------------------------------------------------------------------------------

f(n)

n

------------------------------------------------------------------------------------------

2. SIECI O NIEPEŁNYM POŁĄCZENIU

1. SZEREG

p = n-1 = 0(n) - rzędu n - algorytm sortowania

c = 2 - mnożenie macierzy

d = n-1

2. KRATA TOROIDALNA

KRATA KLASYCZNA

• nie zawiera zewnętrznych połączeń

• p = 2n

c = 4

d = √n -1

1. SIATKA (mesh)

• może być dwuwymiarowa

q = 1 dla szeregu

q = 2 dla kraty

• liczba połączeń = 2q

1. DRZEWO BINARNE

• równoległe przeszukiwanie plików

• mnożenie macierzy przez wektor

• znajdowanie składowych wspólnych

1. PIRAMIDA (o rozmiarze 16)





p = (n(n-1))/2 = 0(n²) - rzędu n²

c = n-1

a b c d

a b c d

e

f

g

h

f

g

h

e

p = 2(n-√n) = 0(n)

c = 4

d = 2(n-√n) = 0(n)

• mnożenie macierzy

• algorytm sortowania

• rozwiązywanie układów równań różniczkowych

• algorytmy grafowe

p = n-1

c = 3

d = 2log(n/2) = 0(logn)

(log = log₂)

0(logn)

0(√n)

0(n)

0(n²)

0(n³)

....

0(n!)

0(nⁿ)

p = (2^log_n^n-1-1)² = 0(n)

c = 9

d = 2(√(3n+1) - 1) = 0(√n)

• algorytmy grafowe

• algorytmy przetwarzania obrazów

---