1. Pamięci rozproszone, rysunek i opis

2. Problemy pojawiajace przy obliczaniu zadan na jednostce wieloprocesorowej 4. Problem podzialu zadania [coś w ten deseń]

3. Pamięć wspólna - omówić z uwzględnieniem rysunku poglądowego, wad, zalet takiego systemu oraz wypisać komercyjne komputery posiadające taką strukturę.

4. prawo amdahla - wyprowadzic i opisac "wnisek z tego wzoru"

5. hiperszescian i piramida (opisac i dac wzory)

6. Opisz klasyfikacje Flynn'a. narysuj i opisz SIAD

7. Coś o wyznaczaniu ciągu sum.

8. Krata (oba rodzaje) i drzewo binarne

9. Synchronizacja

Ad.1.

Pamięć rozproszona

a) architektury z przesyłaniem komunikatów (wiadomości) (message passing)

- wczesne konstrukcje (1 komp. - 1 system oper.)
- współczesne - architektura wielokomputerowa (n oddzielnych komputerów) (MPP)

Przykładowe systemy:

- IBM RS6000SP

- Inlet Paragon XP/S

- klastry komputerów

b) architektury z pamięcią fizycznie rozproszoną, lecz wirtualnie wspólną

DSM VSM
równoległość danych
NUMA (niejednolity dostęp do pamięci)

Ad.2.

Problemy:

1. Podział programu na zadania.

2. Dobór języka programowania równoległego.

3. Przydział zadań procesorom.

4. Komunikacja między procesorami i synchronizacja ich pracy.

Zadania współbieżne - fragmenty programu, które można wykonywać w tym samym czasie. Zadaniami są procedury.

for i:=1 to N do

begin

a[i]:=b[i]+c[i];

d[i]:=a[i]+e[i]

end

P1:

for i:=1 to N div 2 do

begin

a[i]:=b[i]+c[i];

d[i]:=a[i]+e[i]

end

P2:

for i:=N div 2+1 to N do

begin

a[i]:=b[i]+c[i];

d[i]:=a[i]+e[i]

end

Ad.3.

Komputer tradycyjny komputer wieloprocesorowy

- moduł PaO

- procesory

VMA- jednolity czas dostępu

• niewielka liczba procesorów

SGI Power Challenge (do 36 procesorów)

HP V2500 (do 32 procesorów)

SUN Enterprise 10000 (64 prosesory)

SMP - symetryczna wieloprocesorowość

Ad.4.

Prawo Amdahla - potencjalny wzrost wydajności, przez zastosowanie wielu procesorów, będzie ograniczony przez szeregowość algorytmów programu.

S = 1/gamma

S- przyspieszenie, Gamma - ilość obliczeń sekwencyjnych

Wzór Amdahla nie bierze pod uwagę rozmiarów rozwiązywanego problemu.

Ad.5.

Hiper sześcian (n-sześcian) (ang. hypercube, n-cube)

n=2^k

k - sąsiadów

0, 1, ..., n-1

00100

01100

Łączenia polegają na różnicy jednego bita.

Liczba, symbol k jest również nazywana wymiarem kiper. sześcianu.

Rozmiar:

k=1 k=2 k=3

Parametry:

Liczba krawędzi c=log n

p= (n log n)/2= 0(n log n)

d=log n=0(log n)

Parametry piramidy:

c=9

p=(2^{└log4n┘+1}-1)²=0(n)

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

Zastosowanie:
- algorytmy graficzne;

- algorytmy przetwarzania obrazów;

Ad.6.

Klasyfikacja Flynn'a :

- SISD - Single Instruction Single Data (komputery klasyczne)

- SIMD - Single Instruction Multiple Data (komputery macierzowe)

- MISD - Multiple Instruction Single Data (Stworzone dla kompletu, np. grupy CDC-6000 I 7000)

- MIMD - Multiple Instruction Multiple Data (Systemy wieloprocesorowe ściśle i luźno połączone)

SISD - pojedyncze rozkazy działające na pojedynczym źródle danych (typ architektury komputerowej)

Ad.7.

1. Algorytm wyznaczania ciągu sum.

for i:=0 to n do A[i+1]:=B[i]+A[i]

A[1]:=B[0]+A[0]

A[2]:=B[0]+B[1]+A[0]

…

A[n+1]:=B[0]+…+B[n]+A[0]

S_k=Σ_[k;i=0]B[i] ,k=0,1,…,n

Wyznaczanie ciągu sum w procesorze macierzowym.

„4-5”-suma

0(n)|0(log n)

Ad.8.

Krata klasyczna:

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

c=4

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

Krata toroidalna:

p=2n

c=4

d=√n-1

Szereg i kratę zaliczamy do struktury typu siatka (mesh).

q - wymiar

q=1 (szereg)

q=2 (krata)

liczba połączeń dla siatki =2q

Zastosowanie architektury kraty:

- sortowanie;

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

- algorytmy grafowe

Drzewo binarne :

c=3

p=n-1

d=2log₂[(n+1)/2]=0(log n)

Zastosowanie:

- równoległe przeszukiwanie plików;

- mnożenia macierzy przez wektor;

- składowe spójne (w grafice)

Ad.9.

- celem synchronizacji jest ograniczenie swobody przeplotu tak, żeby dopuszczalne stały się tylko przeploty zgodne z intencją programisty

- s. na najniższym poziomie polega na wykonaniu określonych instrukcji, które powodują blokowanie wykonywania odpowiednich instrukcji

synchronizujących w innych strumieniach.

- s. na wyższym poziomie polega na przygotowaniu specjalnych konstrukcji programotwórczych, które gwarantują zachowanie określonych

własności w przeplocie instrukcji, zgodnie z intencją programisty.

Inne :

SZEREG:

p=n-1=0(n)

c=2

d=n-1

Stosowane do:

- algorytmów sortowania

- mnożenia macierzy

Warunki zrównoleglenia pętli :

- wartości elementów tablicy w każdej iteracji nie zależą od elementów tej tablicy w innej iteracji.

- obliczenia w pętli nie zmieniają warunkowo zmiennej, która jest następnie używana poza pętlą.

- obliczenia w pętli nie zmieniają tej samej zmiennej prostej w trakcie iteracji.

Sieć połączeń

…

…

…

…

procesory

pamięci lokalne

Procesor 1

program główny

Procedura A

Procesor 1

Procedura B

PaO

Sieć połączeń

Procesor

k=0

0

1

2

3

4

5

6

7

---