Krzysztof Banaś

Obliczenia równoległe i rozproszone.

Architektury systemów komputerowych

do obliczeń równoległych

Krzysztof Banaś

Obliczenia równoległe i rozproszone.

Przegląd

➔

komputer von Neumanna

➔

abstrakcyjne maszyny RAM i PRAM

➔

klasyfikacja Flynna 

➔

komputery macierzowe

➔

komputery wektorowe

➔

współczesne procesory

➔

systemy wieloprocesorowe

➔

systemy wielokomputerowe

➔

sieci i klastry stacji roboczych i komputerów osobistych

Krzysztof Banaś

Obliczenia równoległe i rozproszone.

Architektura von Neumanna

➔

program i dane w pamięci komputera

➔

pojedynczy procesor:



pobiera rozkaz z pamięci



rozkodowuje rozkaz i znajduje adresy argumentów



pobiera dane z pamięci



wykonuje operacje na danych



zapisuje wynik w pamięci

Krzysztof Banaś

Obliczenia równoległe i rozproszone.

Pomysły na równoległość 1

➔

Teoretyczne modele obliczeń (do analizy algorytmów)



maszyna o dostępie swobodnym (RAM) 



równoległa maszyna o dostępie swobodnym (PRAM) – pominięcie 

zagadnień czasowej złożoności synchronizacji i komunikacji, 

koncentracja na współbieżności z pełną synchronizacją



EREW – wyłączny odczyt, wyłączny zapis



CREW– jednoczesny odczyt, wyłączny zapis



ERCW– wyłączny odczyt, jednoczesny zapis



CRCW– jednoczesny odczyt, jednoczesny zapis; strategie:

➢

jednolita (common) – dopuszcza zapis tylko identycznych danych

➢

dowolna (arbitrary) – wybiera losowo dane do zapisu

➢

priorytetowa (priority) – wybiera dane na zasadzie priorytetów

Krzysztof Banaś

Obliczenia równoległe i rozproszone.

Pomysły na równoległość 1

➔

Algorytm obliczania elementu maksymalnego tablicy A na n

2

 

procesorowej maszynie CRCW PRAM ze strategią jednolitą:

element_maks( A, p, k ): maks{ // uchwyt do tablicy i skrajne indeksy

DLA i= p,...,k { 

||

 m[i] := PRAWDA }

// tablica pomocnicza m

DLA i=p,...,k{

// dzięki użyciu n

2

 procesorów równoległe 

DLA j=p,...,k{

// wykonanie pętli zajmuje O(1) czasu 

||

JEŻELI( A[i] < A[j] ) m[i] := FAŁSZ

} }
DLA i=p,...,k { 

||

JEŻELI( m[i]=PRAWDA ) maks := A[i] }

ZWRÓĆ maks

}

Krzysztof Banaś

Obliczenia równoległe i rozproszone.

Pomysły na równoległość 2

➔

zwielokrotnienie strumieni przetwarzania rozkazów i danych



klasyfikacja Flynna



SISD (oryginalna architektura von Neumanna)



SIMD – jeden strumień rozkazów i wiele strumieni danych



MISD – wiele strumieni rozkazów i jeden strumień danych (w teorii coś na 

kształt taśmy produkcyjnej, w praktyce brak przykładów)



MIMD – wiele strumieni danych i wiele strumieni rozkazów



warianty



z pamięcią wspólną – konieczna wysoka przepustowość dostępu do pamięci



z pamięcią rozproszoną – brak pojedynczej przestrzeni adresowej



hybrydowe (rozproszona pamięć wspólna – DSM, distributed shared 

memory, zwana także wirtualną pamięcią wspólną) – problem spójności

Krzysztof Banaś

Obliczenia równoległe i rozproszone.

Pomysły na równoległość 3

➔

Rozwój architektur procesorów – procesory wektorowe



w procesorze jednostki skalarne i wektorowe (czasem adresowe)



operacje wektorowe (w tym operacje redukcji)



op V ­> V (np. a[i]:= ­b[i])



op V ­> S – redukcja (np. r:=max(b[i]))



V op V ­> V (np. a[i]:=b[i]+c[i])



V op S ­> V (np. a[i]:= s*b[i])



dostęp do pamięci: wielobankowość, przeplot, potoki



rejestry wektorowe (długość 64 do 128) – w tym maska



potokowe jednostki funkcjonalne



łączenie operacji w łańcuchy (chaining) (a[i] := b[i] + s*c[i] )

Krzysztof Banaś

Obliczenia równoległe i rozproszone.

Pomysły na równoległość 4

➔

Rozwój architektur mikroprocesorów



prawo Moore'a



równoległość na poziomie realizacji pojedynczych rozkazów 

(ILP – instruction level parallelism)



procesory potokowe – podział realizacji rozkazu nie na dwa, ale 

na wiele etapów (Northwood – ok. 20, Prescott – ok. 30)



procesory superskalarne (wiele jednostek funkcjonalnych w 

jednym procesorze, możliwość realizacji wielu identycznych 

rozkazów w każdym cyklu)



procesory wielordzeniowe (kilka potokowych superskalarnych 

rdzeni na jednej płytce)



procesory VLIW

Krzysztof Banaś

Obliczenia równoległe i rozproszone.

Pomysły na równoległość 4

➔

Problemy przetwarzania potokowego:



hazardy (konflikty jednocześnie wykonywanych różnych faz 

różnych rozkazów zaburzające płynne funkcjonowanie potoku):



strukturalne – klasyczna konkurencja o zasoby procesora



sterowania – związane z rozgałęzieniami 



danych – WAR, WAW, RAW



zależności danych (hazardy danych z punktu widzenia 

programowania)



anty­zależności – WAR – zapis po odczycie



zależności wyjścia – WAW – zapis po zapisie



rzeczywiste zależności (danych) – RAW – odczyt po zapisie

Krzysztof Banaś

Obliczenia równoległe i rozproszone.

Pomysły na równoległość 5

➔

Systemy równoległe z procesorów ogólnego przeznaczenia 

(superskalarnych, wielordzeniowych, VLIW)



SMP – symetryczna wieloprocesorowość



szybki, jednolity dostęp do wspólnej pamięci i innych zasobów



DSM – systemy z pamięcią hierarchiczną



systemy masywnie równoległe – bez globalnego mechanizmu 

pamięci wspólnej, złożone z pojedynczych procesorów lub 

wieloprocesorowych węzłów przetwarzających (np. SMP lub DSM)



klastry i sieci stacji roboczych – podobnie jak systemy masywnie 

równoległe lecz złożone z odrębnych komputerów (jedno lub 

wieloprocesorowych) 

Krzysztof Banaś

Obliczenia równoległe i rozproszone.

Podsumowanie

➔

Praktyczne alternatywy:



programowanie sekwencyjne ze zrównolegleniem:



niejawnym poprzez układ procesora superskalarnego



niejawnym poprzez automatyczny kompilator zrównoleglający



programowanie w modelu z pamięcią wspólną



programowanie w modelu równoległości danych



programowanie w modelu z przesyłaniem komunikatów



programowanie w hybrydowym modelu łączącym oba powyższe