1. Pamieć rozproszona oraz jej dwie podgrupy: rysunki, opisy, wady, zalety ?

Pamięć rozproszona (distributed memory architecture), czyli architektury gdzie pamięć jest podzielona na fragmenty zarządzane przez poszczególne procesory (lub grupy procesorów). Można wyróżnić 2 podgrupy:

1. Architektura z przesyłaniem komunikatów

-wczesne konstrukcje jeden komputer wieloprocesorowy z jednym systemem operacyjnym

-nowsze rozwiązanie: architektura wielokomputerowa oddzielny system operacyjny dla każdego procesora

-często stosowana nazwa MPP

-do klasy tej zalicza się również klastry komputerów

b) architektura z pamięcią fizyczną, lecz wirtualnie wspólną

-emulacja pamięci wspólnej za pomocą dodatkowych jednostek funkcjonalnych i oprogramowania

-stosowane nazwy DSM, VSM

-dostęp do informacji we wspólnej (wirtualnej) pamięci zależy od jej umiejscowienia w konkretnej pamięci lokalnej - maszyny o niejednokrotnym dostępie do pamięci (NUMA)

2. 
   Coś tam z procesorami wektorowymi i schemat mechanizmu potokowego przy wykonywaniu operacji arytmetycznych i logicznych (dla dodawania zmiennoprzecinkowego).

Dodawanie

1. Wejście
   Wydzielenie cech
   (rejestr)
   Porównanie cech
   (rejestr)
   Przesunięcie mantysy
   (rejestr)
   Dodawanie mantys
   (rejestr)
   Normalizacja sumy
   (rejestr)
   Badanie nadmiaru / niedomiaru
   Wyjście

3. Wzór na średnicę hipersześcianu i obliczyć taką średnicę dla k = 5.

4. Maksymalna ilosc polaczen procesora w kratownicy i sieci przetasowanej

Siec przetasowana (ang. perfect shuffle)

n=2^k procesów ponumerowanych od 0 do n-1 jest ze sobą połączonych następująco:

- procesor i jednokierunkowo z procesorem 2i mod (n-1):

łącza tasowania

- procesor 2i dwukierunkowo z procesorem 2i+1:

łącza wymiany

c=3 (w tym tylko jedno łącze jednokierunkowe)

p=(3n -4)/2 = 0(n)

Średnica d= 2 log₂n - 1=0(n)

Zastosowanie:

transpozycja macierzy

mnożenie macierzy

sortowanie

teoria grafów

5. Narysowac system z pamiecia wieloportowa

Pamięć wieloportowa (multiport memory)-Organizacja pamięci, w której możliwy jest dostęp do różnych bloków.

6. Co to jest arbitrator w systemie ze wspolna magistrala i jakie ma funkcje

7. 
   Czym charakteryzuje sie kolejka FIFO, a czym LIFO

8. Jakie wartosci moze przyjmowac semafor ogolny, a jakie binarny

1. Semafor binarny: początkowa wartość zmiennej semaforowej równa jest maksymalnej liczbie procesów, mogących jednocześnie korzystać z zasobu (parametr określany dla każdego zasobu)

2. Semafor binarny: poczatkowa wartość zmiennej semaforowej równa 1

9. Z iloma innymi moze sie laczyc procesor w drzewie

1. binarnym

Drzewo binarne (dwójkowe):

DRZEWO BINARNE:

c=3

p=n-1

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

Główne zastosowanie:

- równoległe przeszukiwanie plików;

- mnożenia macierzy przez wektor;

- składowe spójne (w grafice)

2. piramidzie

Piramida

Drzewo czwórkowe wzbogacone o dodatkowe połączenie między wieżchołkamitworzące na każdm poziomie krate

c=9

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

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

Zastosowanie:
- przetwarzania obrazów (głównie;

- teoria grafów

10. Procesory wektorowe. Wszystko o tym.

11. Podać architekturę Flynna pod względem mechanizmów uwzględniając pełne nazwy angielskie, pełne nazwy polskie, skrót angielski oraz schematy włączając w to oba schematy dla wielokrotnego strumienia danych.

Taksonomia Flynna jest klasyfikacją architektur komputerowych, zaproponowaną w latach sześćdziesiątych XX wieku przez Michaela Flynna, opierająca się na liczbie przetwarzanych strumieni danych i strumieni rozkazów.

W taksonomii tej wyróżnia się cztery grupy:

• SISD (Single Instruction, Single Data) - (pojedynczy strumień rozkazów, jeden strumien danych) architektura klasycznego komputera sekwencyjnego(architektura von Neumana)

• SIMD (Single Instruction, Multiple Data) -(pojedynczy strumień rozkazów, wielokrotny strumien danych) praktyczna implementacją sa procesory macierzowe

• MISD (Multiple Instruction, Single Data) -(wielokrotny strumień rozkazów, pojedynczy strumien danych) do klasy tej należą systemy wieloprocesorowe ; zbliżone do niej sa systemy sieciowe - układy dwu lub więcej maszyn połączonych siecią komputerową

• MIMD (Multiple Instruction, Multiple Data) -(wielokrotny strumień rozkazów, wielokrotny strumien danych) brak praktycznych zastosowań

12. wymienić procesory z pamięcią wspólna i jeden wybrany opisać

1. systemy ze wspólną magistralą

mała zależność funkcjonalna

mały koszt

łatwość rekonfiguracji

konieczność zapewnienia dużej niezawodności

„wąskie gardło” systemu

2. systemy z przełącznicą krzyżową

duża złożoność funkcjonalna

dużą przepustowość

trudność rozbudowy

3. systemy z pamięcią wieloportową

kosztowna pamięć

ograniczenie konfiguracji

duża liczba przewodów

13. Wymień znane ci architektury i opisać (oraz narysować) SISD.

1. SISD - Single Instruction stream - Single Data stream
   2. SIMD - Single Instruction stream - Multiple Data stream
   3. MISD - Multiple Instruction stream - Single Data stream
   4. MIMD - Multiple Instruction stream - Multiple Data stream
   
   SISD - architektura klasycznego komputera sekwencyjnego, zawierającego jeden procesor i jeden blok pamięci operacyjnej. Ciąg instrukcji wykonywany jest sekwencyjnie. Architektura taka może zawierać również pewne elementy równoległości, jak np. przetwarzanie potokowe (ang. pipelining). Procesor może się składać z kilku jednostek przetwarzających, jednak wszystkie te jednostki podlegają jednej jednostce sterującej procesora. Również jeżeli komputer składa się z kilku procesorów, ale wykonują one niezależne od siebie programy, to możemy traktować go jako zestaw maszyn SISD. Przykładem architektury klasy SISD jest najbardziej rozpowszechniona architektura - uniprocesor von Neumanna
   Wygląd:
   
   JS - jednostka sterująca, JP - jednostka procesora, MP - moduł pamięci, SR - strumień rozkazów

14. Semafor - co to jest. Opisać semafor binarny.

Semafor jest to mechanizm wspomagający synchronizacje. Dzięki niemu poszczególne procesy muszą poczekać na swoja kolej, zanim będą mogły korzystać ze wspólnych danych. Semafor jest liczba całkowita dodatnia. Semafor jest jakby `slotami', miejscami na procesy, które mogą w jednym momencie korzystać ze wspólnych danych. Tzn. - gdy semafor przyjmie wartość 0, zamyka się dostęp do danych. Gdy jest większy od 0, wtedy ta liczba oznacza, ile jeszcze procesów może się dołączyć do korzystania z danych.

Semafor binarny może przyjmować wartości całkowite ze zbioru {0, 1}, czyli semafor, który posiada niepodzielny zasób, czyli tylko jeden proces może być wykonywany, a reszta procesów czeka w kolejce...

15. Architektura Piramidy i Hipersześcianu - co to jest, wzory, zalety i wady.

HIPERSZEŚCIAN


- k-wymiarowy hipersześcian ma k-połączeń wychodzących z każdego zwierzchołĸów.
- Algorytm routujący komunikaty jest bardzo prosty: wysyłaj do wierzchołka najbliższego względem odległości Hamminga

- sześcian ma n=2^k wierzchołków

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=0 k=1

k= 2 k=2

Parametry:

Liczba krawędzi c=log n

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

Średnica d=log n=0(log n) (chyba)

Zastosowanie:

mnożenie macierzy

sortowanie

obliczanie wartości własnych macierzy

algorytmy graficzne

16. Opisać mechanizm potokowy obliczania liczb zmiennoprzecinkowych w komputerach wektorowych

Zasadniczo 2 schematy (dla dodawania/odejmowania i mnożenia/dzielenia)

2. 
   Dodawanie
   Wejście
   Wydzielenie cech
   (rejestr)
   Porównanie cech
   (rejestr)
   Przesunięcie mantysy
   (rejestr)
   Dodawanie mantys
   (rejestr)
   Normalizacja sumy
   (rejestr)
   Badanie nadmiaru / niedomiaru
   Wyjście

17. Opisz teoretyczny model komputera PRAM

Model PRAM - zapewnia możliwość jednoczesnego dostępu każdego spośród n procesorów o architekturze RAM do wspólnej pamięci (pamięci współdzielonej). W modelu tym komunikacja między procesami i ich synchronizacja odbywa się z użyciem wspólnych zmiennych. W rezultacie komputery równoległe o wspólnej przestrzeni adresowej są stosunkowo łatwe do programowania, gdyż minimalizują one problemy związane z przydziałem danych do poszczególnych procesorów i dynamicznym równoważeniem ich obciążenia.

Ze względu na sposób podejścia do tego problemu modele PRAM

dzielimy na:

1) EREW PRAM (Exclusive Read, Exclusive Write) - nie zezwala na żaden równoczesny dostęp,

zarówno w sensie pisania, jak i czytania;

2) CREW PRAM (Concurrent Read, Exclusive Write) - zezwala na równoczesność wielu

odczytów, ale nie zapisów;

3) CRCW PRAM (Concurrent Read, Concurrent Write) - zezwala na równoczesność zarówno

odczytów, jak i zapisów.

W przypadku równoczesnego zapisu można przyjąć różną politykę rozwiązywania konfliktów.

Ze względu na nią modele CRCW PRAM dzielimy na:

1) common CRCW PRAM - równoczesny zapis dozwolony jest tylko wtedy, gdy ma być zapisana

jedna i ta sama wartość;

2) arbitrary CRCW PRAM - w przypadku próby równoczesnego zapisu, RAM, który otrzymuje

zezwolenie na zapis, wybierany jest losowo;

3) priority CRCW PRAM - wszystkie RAM-y mają przyporządkowane priorytety (parami różne),

priorytety są liniowo uporządkowane, w przypadku próby równoczesnego zapisu zezwolenie na

zapis otrzymuje RAM o najwyższym priorytecie.

18. Opisz teoretyczny model komputera RAM

Pamięć o dostępie swobodnym (typu RAM) dobrze nadaje się do celów projektowania i organizacji komputerów sekwencyjnych, którym według klasyfikacji M. Flynna odpowiada (rys.1.4) architektura z pojedynczym potokiem rozkazów i pojedynczym potokiem danych typu SISD (ang. Single Instruction stream - Single Data stream).

Rys.1.4. Architektura komputera sekwencyjnego typu SISD

W modelu (maszynie) RAM (ang. Random Access Machine) programy i dane przechowywane są w pamięci o dostępie swobodnym. Model ten pozwala na realizację co najwyżej jednej instrukcji w dowolnym momencie czasu, niezależnie od tego, co reprezentuje sobą dany rozkaz - odwołanie się do pamięci czy też operację arytmetyczno-logiczną. Ściśle sekwencyjny sposób wykonywania operacji przez jedną jednostkę przetwarzającą nie pozwala na faktyczne zrównoleglenie algorytmu nawet, jeśli udoskonalenia w architekturze komputera umożliwiają realizację elementarnych mechanizmów przetwarzania równoległego w postaci np. potokowego wykonania niektórych operacji, organizacji tzw. przeglądu (ang. look-ahead) kolejki rozkazów w przód, a także zastosowania wielopoziomowej pamięci typu cache czy też bezpośredniego dostępu do pamięci (ang. DMA - Direct Memory Access). Dodajmy, że w ostatnim przypadku wykorzystanie trybu bezpośredniej wymiany danych między urządzeniem We/Wy i pamięcią (bez udziału procesora) pozwala na zmniejszenie obciążenia procesora i zwiększenie ogólnej wydajności systemu.

Praktycznie każdy komputer o architekturze von Neumanna i rozkazach jednoadresowych jest maszyną RAM. Analiza złożoności algorytmów dla maszyn RAM sprowadza się do wyznaczenia czasów wykonania poszczególnych rozkazów lub programów, realizowanych w jednoprogramowym trybie pracy.

19. Narysuj ogolny schemat komputera z pamiecia wspolna. Wymien architektury systemow z pamiecia wspolna i wypisz ich wady i zalety

Pamięć wspólna - (współdzielna, dzielona) - zorganizowana ze wspomaganiem sprzętowym dla zapewnienia operacji zapisu i odczytu informacji dostępnej dla wszystkich procesorów systemu. Organizacja typowa dla konstrukcji o stosunkowo niewielkiej liczbie procesorów

20. SIMD (tu nie wiem czy to to)
    - narysować,
    - na czym polega maskowanie,
    - praca synchroniczna (opisać).

Tryb SIMD pracy komputerów równoległych (procesy macierzowe,systemy wieloprocesorowe) głęboka modyfikacja algorytmów klasycznych (sekwencyjna)

Algorytm wyznaczania ciągu sum częściowych. Częste w zastosowaniach technicznych równanie rekurencyjne (fragment programu):

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

Po rozpisaniu poszczególnych:

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

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

A[3]=:=B[2]+A[2]=B[0]+B[1]+B[2]+a[0];

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

Główny element rozwiązania: uzyskanie ciągu sum częściowych

B[0]+B[1]+....B[k]; k=0,1,....,n

Dla n=7 zmniejszenie liczby kroków sumowania z 7 do 3.

Ogólnie złożoność algorytmu zmniejszyla sie z 2 0(n) do 0(logn)

Algorytm sortowania bąbelkowego: porównujesz od prawej do lewej sąsiednie cyfry i jak prawa mniejsza od lewej to je przestawiasz; n(n-1)/2=0(n²) operacji; C²_n=(ⁿ₂)

21. Zadanie o producencie i konsumencie

Synchronizacja producent produkuje jeżeli są wolne miejsca w magazynie w przeciwnym czasie czeka konsument pobiera z magazynu jak coś jest jak nie ma to czeka. Jak producent coś wytworzył to daje to do magazynu to daje o tym znać konsumentowi jeżeli konsument pobrał coś z magazynu i zwolnił miejsce to daje o tym znać producentowi.

PRODUCENT	KONSUMENT
while do true do begin wytwórz produkt if brak wolnych miejsc w magazynie then czekaj złóż produkt zapisz że dodano jedną sztukę produktu; if konsument czeka then zaktywizuj go end;	while true do begin if brak produktów produktów magazynie then pobierz produkt zapisz, że pobrano jedną sztukę produktu; if producent czeka then zaktywizuj go; wykorzystuje produkt end;
while true do begin P(m){wytwórz produkt; if m=0 then czekaj; m:=m-1; złóż produkt; V(p){ p=p+1; if konsument czeka then zaktywizuj go end	while true do begin P(p){ it p=o then czekaj p:=p-1 Pobierz produkt V(m){m:= m+1; if producent then zaktywizuj go ; wykorzystaj produkt end
while true do begin wytwórz produkt P(m) złóż produkt; V(p) End;	while true do begin P(p); Pobierz produkt, V(m) wykorzysta produkt end

Wnioski z Prawa Amdahla.

1. Widoczne jest przyśpieszenie

2. Ułamek obliczeń, wykonywanych równolegle musi być w sposób istotny duży aby przyśpieszenie było znaczące i nawet bowiem przy nieskonczonej liczbie procesorów nie jesteśmy w stanie uzyskać przyśpieszeniea większego niż wynika to z samego ułamka obliczeń, które należy wykonać sekwencyjnie:

lim_p∞S(n,p)=1/f(n)

Procesor wektorowy - klasyfikuje on w sposób potokowy, rozkazy wektorowe. Polega to na powtarzaniu ciągu elementarnych operacji arytmetycznych na strumieniach danych tworzących wektory.

Wektor - uporządkowany zbiór n elementów skalarnych (pojedynczych)elementami mogą być: liczby stało- lub zmiennoprzecinkowe, wartości logiczne, znaki

Przykład dodawanie zmiennoprzecinkowe

L₁=m₁ 2^c1

L₂=m₂ 2^c2 c₂>c₁ , ½<=m₁,m₂<2

L=l₁=l₂=m₁ 2^c1+ m₂ 2^c2 wydzielanie celu

=m₁' 2^c1-c2 2^c2 + m₂ 2^c2= porównanie celu

=m₁' 2^c2 m₂ 2^c2+ m₂ 2^c2= przesówanie mantysy

=m'2^c2 dodawanie mantysy

=m₂^c normalizacja sumy

1

2

3

4

5

6

7

0

LIFO - ang. Last In, First Out (ostatni na wejściu, pierwszy na wyjściu). Inaczej

mówiąc, ostatni będący na wejściu, jest jednocześnie pierwszym, który wychodzi. Jest

to tzw. stos, przeciwieństwo kolejki FIFO. Nowe procesy dodawane są również na

koniec kolejki, jednak to właśnie one są pobierane jako pierwsze.

FIFO - ang. First In, First Out (pierwszy na wejściu, pierwszy na wyjściu). Czyli

nowe procesy dodawane są na koniec kolejki, a pobierane są te, które dodane były

wcześniej, jako pierwsze. Czyli dość logicznie - te, które weszły pierwsze, szybciej

też wychodzą.

poziom 0

korzeń

gałęzie

liście

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

poziom 3

0

3

1

4

2

17

18

19

20

13

14

15

16

9

10

11

12

5

6

7

8

szczyt

poziom 2

poziom 1

podstawa

poziom 0

JS - jednostka sterująca

JP- -||- przetwarzająca

MP - moduł pamięci

SR - strumien rozkazów

SD - strumien danych

SR - strumien rozkazów ; JS - jednostka sterująca ; JP₁ - JP_n - jednostki przetwarzające ; MP₁ - MP_n - moduły pamięci ; SD₁-SD_n - strumien danych

SR₁-SR_n - strumienie rozkazów ; JS₁-JS_n - jednostki sterujące ; JP₁ - JP_n - jednostki przetwarzające ; MP₁ - MP_n - moduły pamięci ; SD₁-SD_n - strumien danych

SR₁-SR_n - strumienie rozkazów ; JS₁-JS_n - jednostki sterujące ; JP₁ - JP_n - jednostki przetwarzające ; MP₁ - MP_n - moduły pamięci ; SD₁-SD_n - strumien danych

b) Mnożenie
Wejście
Mnożenie
Akumulacja
Odejmowanie cech
Przesuwanie mantysy
Dodawanie
Normalizacja
Wyjście

Problemem sortowania ciągu n elementów a₀,a₁,a₂...a_n-1

Metodą bąbelkową (bubble sort)

- w każdym kroku - porównanie, i ewentualna zamianasąsiednich elementów

- po pierwszej iteracji element najwiekszy zajmuje pozycje ostatnia

- w kolejnej iteracji długość ciągu zmniejsza sie o 1

- maksymalna liczba porównań i zamian wynosi n(n-1)/2 => złożoność algorytmu jest 0(n²)

PRODUCENT

KONSUMENT

Komunikacja

Magazyn p

Magazyn m

---