Teoria WDI

Wprowadzenie do informatyki
Wykład 1. Architektury systemów
komputerowych
Maszyna von Neumanna
Architektury Princeton, Harvard
Taksonomia Flynna
Architektury równoległe
Tendencje rozwoju technologii półprzewodnikowej
Podzespoły systemu komputerowego
Maszyna von Neumanna
Koncepcja programu przechowywanego w pamięci
(1945 r.)
stored-program concept
John von Neumann
John W. Mauchly
John Presper Eckert
(ENIAC)
Maszyna von Neumanna
Przetwarzanie danych odbywa się na podstawie wykonania
instrukcji programu przechowywanego w pamięci
Zmiana zadania wymaga tylko zmiany zawartości pamięci, bez
ingerencji w strukturę systemu
Uniwersalność
Elastyczność
Podstawowymi elementami architektury w takiej koncepcji są:
CPU, pamięć oraz I/O
Maszyna von Neumanna
ALU
Układ
sterowania
Urządzenia I/O
Pamięć
0
1
2
3
. . . . .
CPU
Adres
Dane
Sterowanie
Maszyna von Neumanna
Podstawowe założenia:
1. Program i dane przechowywane są we wspólnej pamięci
dostępnej do odczytu i zapisu
2. Pamięć ma liniową przestrzeń adresowania (składa się z
pewnej liczby kolejnie ponumerowanych komórek). Każda
komórka ma unikalny adres
3. Sposób przechowywania danych i instrukcji jest identyczny
4. Rozkazy programu są pobierane z pamięci i wykonywane
sekwencyjnie (spod kolejnych zwiększających się adresów)
5. Zawartość pamięci modyfikowana jest przez wykonywany
program
6. Procesor powinien mieć skończoną i funkcjonalnie pełną listę
rozkazów
Architektury systemów komputerowych
CPU
Pamięć
programu
i danych
Dane i
rozkazy
CPU
Pamięć
danych
Pamięć
programu
dane
rozkazy
Architektura Princeton
(von Neumanna)
Architektura Harvard
Architektura Princeton
Wspólna pamięć do przechowywania
programu i danych
Jednolita przestrzeń adresowania
Jedna wspólna magistrala do
przesyłania danych i kodu
Sekwencyjny dostęp do instrukcji i
danych
Wyklucza równoczesne pobieranie
instrukcji i dostęp do danych
von Neumann bottleneck – procesor
jest w stanie szybko przetwarzać
instrukcje i dane, ale musi oczekiwać na
pobranie instrukcji z pamięci, gdyż
magistrala jest zajęta przesyłaniem
danych
Pamięć dostępna do odczytu i zapisu
CPU
Pamięć
programu
i danych
Dane i
rozkazy
Architektura Harvard
Oddzielne pamięci programu i danych
Oddzielne magistrale dostępu do
pamięci danych i programu
Magistrale danych i rozkazów są
niezależne, mogą mieć różną
szerokość
Jednoczesny dostęp do obu pamięci
(w trakcie pobierania argumentów
można równocześnie pobierać
rozkazy)
Skraca to cykl rozkazowy i zwiększa
szybkość pracy
Wysoka wydajność dzięki możliwości
równoczesnego dostępu do obu
pamięci
Pamięć programu dostępna tylko do
odczytu
Niejednoznaczność adresów, stosuje
się różne rozkazy dostępu do instrukcji
i danych
CPU
Pamięć
danych
Pamięć
programu
dane
rozkazy
Architektura Harvard-Princeton
Wspólna pamięć programu i
danych
Dostęp procesora do pamięci
realizowany jest przez oddzielne
dla danych i kodu pamięci
podręczne
Eliminuje konflikty odwołań do
pamięci
Szybkie działanie dzięki
równoległości dostępu
Możliwość zapisu do pamięci
programu
Łączy zalety architektury Harvard
(wydajność) i Princeton
(możliwość modyfikacji pamięci)
CPUPamięć
Pamięć
podręczna
danych
Pamięć
podręczna
programu
dane
rozkazy
Prawo Moore’a
Liczba tranzystorów,
które można umieścić w układzie
scalonym, rośnie wykładniczo w czasie.
Czas potrzebny na podwojenie liczby
elementów szacuje się obecnie na 18 do
24 miesięcy.
Ograniczenia rozwoju technologii
Rozmiary tranzystorów nie mogą być zmniejszane w nieskończoność
Ograniczenie na zwiększenie częstotliwości taktowania – prędkość propagacji
sygnału w przewodzie miedzianym wynosi 20 cm/ns (nieprzekraczalną
wartością jest prędkość światła)
- przy częstotliwości 10GHz całkowity dystans pokonywany przez sygnał nie
może przekroczyć 2 cm
- przy 100GHz – 2 mm
Problem emitowania ciepła przez układ scalony – moc rozpraszana w
procesorze wzrasta ze wzrostem liczby tranzystorów i częstotliwości taktowania
Taksonomia Flynna
MIMD
Multiple Instruction stream,
Multiple Data stream
SIMD
Single Instruction stream,
Multiple Data stream
N
MISD
Multiple Instruction stream,
Single Data stream
SISD
Single Instruction stream,
Single Data stream
1
N1
Liczba strumieni instrukcji
Liczbastrumienidanych
Klasyfikacja systemów równoległych
Systemy równoległe
Wieloprocesory Wielokomputery
Systemy z pamięcią współdzieloną
Komunikacja przez wspólne
obszary pamięci
Systemy z pamięcią rozproszoną
Przekazywanie komunikatów przez
sieć połączeń
Wieloprocesory i wielokomputery
Wieloprocesory (ang. multiprocessors)
W systemach równoległych z pamięcią współdzieloną:
• wszystkie procesory współdzielą tę samą przestrzeń adresową
• komunikacja odbywa się przez zapis/odczyt wspólnych obszarów
współdzielonej pamięci
Wielokomputery (ang. multicomputers)
W systemach równoległych z pamięcią rozproszoną:
• każdy procesor posiada własną pamięć niedostępną dla innych
procesorów
• każdy procesor lub węzeł ma własną lokalną przestrzeń adresową
• procesory komunikują się ze sobą za pośrednictwem sieci połączeń
wymieniając między sobą komunikaty
COMA
NUMA
UMA
Klasyfikacja systemów równoległych
Systemy równoległe
Wieloprocesory Wielokomputery
Systemy równoległe z pamięcią współdzieloną
Podział wieloprocesorów ze względu na sposób realizacji pamięci
współdzielonej:
• UMA (Uniform Memory Access) – jednolity dostęp do pamięci
• NUMA (Non-Uniform Memory Access) – niejednolity dostęp do
pamięci
• COMA (Cache-Only Memory Architecture) – dostęp wyłącznie przez
pamięć cache
Architektura UMA
System wieloprocesorowy ze wspólną pamięcią dla wszystkich
procesorów
Wspólna przestrzeń adresowa pamięci globalnej
Dostęp do pamięci odbywa się poprzez sieć połączeń w identyczny
sposób dla wszystkich procesorów
Czas dostępu do każdej komórki pamięci jest taki sam dla wszystkich
procesorów
Architektura NUMA
Pamięci lokalne procesorów tworzą wspólną pamięć globalną
dostępną dla wszystkich procesorów w jednolitej przestrzeni
adresowania
Czas dostępu do pamięci jest zależny od miejsca pamięci względem
procesora
Procesor uzyskuje szybszy dostęp do swojej pamięci lokalnej, niż do
pamięci lokalnych pozostałych procesorów
Architektura COMA
Pamięć współdzielona składa się jedynie z pamięci podręcznych
poszczególnych procesorów
Wspólna przestrzeń adresowa obejmuje wszystkie dostępne moduły
cache w systemie
MPP
Klasyfikacja systemów równoległych
Systemy równoległe
Wieloprocesory
Wielokomputery
Klastry
Systemy równoległe z pamięcią rozproszoną
Wielokomputery składają się z bloków (węzłów) posiadających własne
pamięci i komunikujących się za pomocą systemu komunikatów
Każdy z węzłów zawiera przynajmniej jeden procesor oraz pamięć,
węzłami takiego systemu mogą być wieloprocesory ze współdzieloną
pamięcią
Wyróżniamy dwie grupy wielokomputerów:
MPP (Massively Parallel Processors) – architektury masywnie
równoległe – węzłami takiego systemy są urządzenia specjalizowane,
specjalnie zaprojektowane wieloprocesory, karty graficzne itp.
klastry obliczeniowe – węzłami są urządzenia typowe, np. komputery
PC albo stacje robocze, połączone są siecią lokalną, współpracujące ze
sobą w celu udostępnienia zintegrowanego środowiska
Klaster obliczeniowy
Chemnitzer Linux Cluster (CLIC), Chemnitz University of Technology, Germany
Architektury masywnie równoległe – MPP
• Superwęzeł – to najczęściej wieloprocesor
• Superwęzeł ma dostęp tylko do swojej własnej pamięci
• Połączone są za pomocą specjalnych urządzeń – przełączników
• Są to z reguły duże systemy zawierające tysiące węzłów
• Mają modułową budowę
• Charakteryzują się dużym stopniem skalowalności
Architektury masywnie równoległe – MPP
Źródło: http://en.wikipedia.org/wiki/Blue_Gene
Architektura Blue Gene/L (IBM, 2004)
Jednostki wydajności obliczeniowej
FLOPS (Floating Point Operations Per Second) – liczba
wykonywanych w ciągu sekundy operacji na liczbach
zmiennoprzecinkowych
MIPS (Million Instructions Per Second)
1024 FLOPSYFLOPSjotta
1021 FLOPSZFLOPSzetta
1018 FLOPSEFLOPSeksa
1015 FLOPSPFLOPSpeta
1012 FLOPSTFLOPStera
109 FLOPSGFLOPSgiga
106 FLOPSMFLOPSmega
Lista TOP500 najszybszych superkomputerów
Moc obliczeniową superkomputerów oceniana jest za pomocą testu
LINPACK. Mierzy on szybkość rozwiązywania gęstych układów
równań liniowych za pomocą metody Gaussa
Superkomputery uzyskujące najwyższe wyniki w tym teście są
publikowane na liście TOP500 aktualizowanej dwa razy w roku
Aktualny rekord wydajności obliczeniowej należy do chińskiego
superkomputera Tianhe-2 (MilkyWay-2) i wynosi 33,86 PFLOPS
Rekord Polski to 373 TFLOPS, należy do superkomputera Zeus, z
Akademickiego Centrum Komputerowego Cyfronet AGH
Sumaryczna moc obliczeniowa 500 największych
superkomputerów z listy TOP500 w czerwcu 2014 wynosiła
274 PFLOPS
Lista TOP500 najszybszych superkomputerów
37 superkomputerów osiągają moc obliczeniową ponad 1 PFLOPS
Procesory wykorzystane do budowy superkomputerów TOP500 :
85,4% – Intel
8% – IBM Power
6% – AMD Opteron
Producenci superkomputerów:
36% (182 superkomputery) – HP
35% (176 superkomputerów ) – IBM
10% (50 superkomputerów) – Cray
Cray rozpoczął pracę nad superkomputerem Cascada, który ma
osiągnąć wydajność 100 PFLOPS
Lista TOP500 najszybszych superkomputerów
33 862.73 120 000Tianhe-2 / 2013, NUDT, China1
3 143.5225 984Cray XC30 / 2014, Cray Inc., United
States
10
4 293.3393 216Vulcan / 2012, IBM, United States9
5 008.9458 752JuQUEEN / 2012, IBM, Germany8
5 168.1462 462Stampede / 2013, Dell, United States7
6 271.0115 984Piz Daint / 2013, Cray Inc., Switzerland6
8 586.6786 432Mira / 2012, IBM, United States5
10 510.0705 024K computer / 2011, Fujitsu, Japan4
17 173.21 572 864Sequoia / 2011, IBM, United States3
17 590.0560 640Titan / 2012, Cray Inc., United States2
Wydajność
[GFLOPS]
Liczba
rdzeni
Nazwa, rok, producent
Superkomputer Tianhe-2 (MilkyWay-2)
Od czerwca 2013 r. najszybszy superkomputer na świecie
33,86 PFLOPS, 3 120 000 rdzeni obliczeniowych, 1,4 EB pamięci
Lawrence Livermore National Laboratory , USA, 2012
Superkomputer Sequoia
#3 na liście TOP500 najszybszych superkomputerów na świecie
17,17 PFLOPS, 1 572 864 rdzenie obliczeniowe, 1,6 PB pamięci
Lawrence Livermore National Laboratory , USA, 2012
Lista TOP500 najszybszych superkomputerów
Surerkomputer Mira, #5 na liście TOP500
Superkomputer Zeus
Zbudowany przez firmę Hewlett-Packard w konfiguracji HP Cluster
Platform 3000 BL 2x220 z procesorów Intel Xeon
25468 rdzeni obliczeniowych, 60 TB pamięci operacyjnej i 2300 TB
pamięci dyskowej, 208 kart Nvidia Tesla M2050 i M2090
Wydajność obliczeniowa 373 TFLOPS (wg testów LINPACK), #176
Wzrost mocy obliczeniowej superkomputerów
Sum – suma mocy obliczeniowej 500 najszybszych superkomputerów
Top – moc najszybszego komputera na świecie
#500 – moc komputera znajdującego się na 500 miejscu listy TOP500
GFLOPS
Podzespoły systemu komputerowego
Jednostka
centralna (CPU)
Pamięć
Podsystem
wejścia-wyjścia
Przetwarzanie danych,
sterowanie systemem
na podstawie wykonania
programu
Przechowywanie
programu i danych
Komunikacja
z otoczeniem
Podsystem połączeń
(magistrale)
Podsystem połączeń
Kilka różnych magistral do połączenia bloków systemu komputerowego
Parametry magistral dostosowane do szybkości podłączonych urządzeń
Krótsze ścieżki przesyłania sygnałów
Istnieje tendencja zastąpienia magistral równoległych połączeniem
szeregowym, skalowalnym, typu punkt-punkt (point-to-point)
Ograniczenia magistrali równoległej:
Skomplikowana struktura połączeń
Wzajemne oddziaływanie na siebie sygnałów przesyłanych równoległymi
ścieżkami, przesłuchy
Ograniczone możliwości zwiększenia częstotliwości taktowania
!
!
Połączenia szeregowe point-to-point vs równoległe
Struktura magistrali równoległej
Przepustowość = szerokość magistrali x częstotliwość taktowania x
(maksymalna x liczba transferów na cykl zegarowy / 8
teoretyczna)
MB/s
GB/sDDR3-1333 64b x 666,6 MHz x 2 / 8 = 10,6 GB/s
Architektura ISA
Magistralę rozszerzenia (we/wy) wprowadzono aby uniezależnić
sposób podłączenia urządzeń we/wy od wersji procesora
Magistrala rozszerzenia ISA na początku dorównywała szybkością
i przepustowością magistrali systemowej, ale bardzo szybko stała
się poważnym ograniczeniem wydajności systemu
Ważnym jest zachowanie kompatybilności standardów
podłączenia urządzeń wejścia-wyjścia
Architektura PCI
Wprowadzono szybką magistralę we/wy do obsługi szybkich urządzeń
Magistrala rozszerzenia ISA pozostała w architekturze dla zapewnienia
kompatybilności, możliwości podłączenia urządzeń w standardzie ISA
Największą wadą takiego rozwiązania jest to, że centralne miejsce w tej
architekturze zajmuje magistrala, która nie jest skalowalna, trudno jest
zwiększyć jej przepustowość, i wkrótce znów stanie się wąskim miejscem
systemu, ograniczając ogólną wydajność
!
Czteroportowa architektura
Dedykowana magistrala do obsługi karty graficznej !
Architektura koncentratorów AHA
Architektura koncentratorów AHA
Zrezygnowano z centralnego miejsca magistrali PCI
Magistrala, która odgrywa ważną rolę w systemie, powinna być
łatwo skalowalna, inaczej szybko staje się wąskim miejscem i
ogranicza ogólną wydajność systemu
Koncentratory połączone są za pomocą szybkiego dedykowanego
interfejsu wewnętrznego
Dwukanałowy dostęp do pamięci (Dual Channel), zwiększona
szerokość magistrali – 128 b, jednoczesny dostęp do dwóch
modułów pamięci
!
Dual Channel
Architektura chipsetu procesora Intel Core 2
Skalowalność magistrali PCI Express
32 GB/sx 16
16 GB/sx 8
8 GB/sx 4
2 GB/sx 1
PCI-Express 3.0
16 GB/sx 16
8 GB/sx 8
4 GB/sx 4
1 GB/sx 1
PCI-Express 2.0
8 GB/sx 16
4 GB/sx 8
2 GB/sx 4
500MB/sx 1
PCI-Express 1.0
PrzepustowośćWersja magistrali
Architektura chipsetu procesora Intel Core i7
Architektura chipsetu procesora Intel Core i7
Kontroler pamięci zintegrowany z procesorem
Dedykowana magistrala łącząca procesor z pamięcią
Trójkanałowy kontroler pamięci (Triple-Channel), szerokość
magistrali pamięciowej 192 b
Wyeliminowano magistralę systemową FSB
Szybki interfejs QPI o przepustowości 25,6 GB/s
Architektura chipsetu X99 Intel Core i7 Extreme
Hierarchia pamięci
Pamięć masowa
Pamięć operacyjna
Pamięć
podręczna
Rejestry
Pojem
ność
Szybkość
Koszt/bit
Pobórm
ocy/bit
Częstotliwośćdostępu
Pamięci dynamiczne a statyczne
Pamięci dynamiczne a statyczne
Pamięci statyczne są szybsze od pamięci dynamicznych
Cykl dostępu do pamięci dynamicznej jest dłuższy ze względu na sposób
organizacji i adresowania pamięci (matryca elementów pamięciowych,
adresowanie dwuetapowe)
Dwuetapowe adresowanie polega na tym, że najpierw podaje się adres
wiersza, a po czasie t RAS/CAS potrzebnym na aktywację wiersza i jego
przepisanie do wzmacniaczy odczytu, podaje się druga część adresu –
adres kolumny
Pamięć dynamiczna wymaga odświeżania (ponowne ładowanie
kondensatorów w regularnych odstępach czasu)
Pamięć dynamiczna ma większa gęstość upakowania na układzie
scalonym (ze względu na mniejsze rozmiary komórki pamięci), pozwala to
umieszczenie na jednym układzie pamięci o większej pojemności ( x4
większy rozmiar w porównaniu do pamięci statycznej)
Organizacja pamięci dynamicznej
Pamięć podręczna
Szybka pamięć o niewielkiej pojemności, przechowuje fragmenty
pamięci operacyjnej, do których procesor ostatnio się odwoływał
Skraca czas dostępu procesora do danych i instrukcji w przypadku,
jeśli znajdują się one w pamięci cache (cache hit)
Zasada lokalności czasowej:
Istnieje duże prawdopodobieństwo, iż dane, których procesor
potrzebuje, będą niedługo znów potrzebne.
Zasada lokalności przestrzennej:
Kolejne odwołania do pamięci zachodzą zwykle w pewnym
niewielkim obszarze, istnieje duże prawdopodobieństwo, iż kolejne
odwołanie będzie wykonano do lokacji sąsiedniej wobec bieżącej
Strategie zapisu
Write-through – jednoczesny zapis do pamięci podręcznej i
głównej
Write-back – zapis tylko do pamięci podręcznej i ustawienie
znacznika informującego o modyfikacji bloku. Pamięć główna nie
jest uaktualniana aż do momentu, kiedy zmodyfikowany blok w
pamięci podręcznej zostanie zastąpiony innym blokiem lub kiedy
inny kontroler odwoła się do danego bloku
Write-once – każdy pierwszy zapis do pamięci podręcznej
powoduje ustawienie znacznika modyfikacji i jednoczesną
aktualizację pamięci głównej. Kolejne zapisy odbywają się tylko do
pamięci podręcznej, ponieważ fakt zmiany zawartości pamięci
został już zasygnalizowany innym procesorom
read hit – szybki dostęp do danych
read miss – ładowanie bloku do pamięci podręcznej
write miss – zapis tylko do pamięci głównej
write hit
Protokół MESI
M – Modified – linia została zmodyfikowana (różni się od pamięci
operacyjnej) i jest dostępna tylko w jednej pamięci podręcznej
E – Exclusive – linia jest zgodna z pamięcią operacyjną i
występuje tylko w jednej pamięci podręcznej
S – Shared – linia jest zgodna z pamięcią operacyjną i występuje
też w innych pamięciach podręcznych
I – Invalid – linia jest nieaktualna (nieważna)
Protokół MESI
RM – Read Miss
ESH-R – External Hit Read
ESH-W – External Hit Write Write-through
Protokół MESI
RM – Read Miss
ESH-R – External Hit Read
ESH-W – External Hit Write Write-back
Protokół MESI
RM – Read Miss
ESH-R – External Hit Read
ESH-W – External Hit Write Write-once
Protokół MESI – systemy wieloprocesorowe
Wielopoziomowa organizacja pamięci podręcznej
Wielopoziomowa organizacja pamięci podręcznej
inclusive cache policy – blok załadowany do pamięci podręcznej
L1 przechowuje się także w pamięciach cache wyższego poziomu
exclusive cache policy – pamięci podręczne różnych poziomów
nigdy nie przechowują tych samych bloków pamięci. Zaleta: więcej
różnych bloków przechowuje się na wszystkich poziomach cache
exclusive cache
inclusive cache
Procesory wielordzeniowe
Organizacja pamięci cache procesora Core i7
inclusive cache policy na wszystkich poziomach cache
Jeśli rdzeń odwołuje się do danych, których nie ma w pamięci L3, oznacza
to, że danych tych nie będzie w żadnej innej pamięci prywatnej L1 czy L2
pozostałych rdzeni
Z każdym blokiem pamięci L3 związane jest 4-bitowe pole atrybutów (po
jednym bicie na rdzeń) informujących, które rdzenie mają kopię danego
bloku w swojej prywatnej pamięci cache
Jest to ważna informacja dla mechanizmu zachowania spójności pamięci
Organizacja pamięci podręcznej
Organizacja pamięci podręcznej Core 2 L1 – 8-way set associative
Rozmiar – 32KB
Rozmiar linii – 64 B
64 zbiory (sets) x 8 linii (ways) w każdym zbiorze
tag –etykieta wykorzystywana do poszukiwania asocjacyjnego, jest to
starsza część (24 bity) adresu fizycznego bloku pamięci
Źródło: http://duartes.org/gustavo/blog/category/software-illustrated
Organizacja pamięci podręcznej Core 2 L1
Rozmiar jednej linii pamięci cache – 64 B
Pamięć przechowuje 64 (sets) x 8 (ways) linii x 64 B = 32 KB
Do każdego zbioru (set) odwzorowują się wszystkie bloki pamięci
głównej, które w polu Set Index zawierają numer danego bloku
Takich bloków jest 236 / 212 = 224 dla każdego zbioru, 8 spośród nich
przechowują się w pamięci podręcznej w danej chwili (8 ways)
Każda linia przechowuje się w pamięci podręcznej wraz z 24-bitową
etykietą (tag), jest to starsza część (24 bity) adresu fizycznego bloku
pamięci
Poszukiwanie asocjacyjne bloku w pamięci podręcznej odbywa się
przez porównanie starszej części adresu bloku (24 bity) z
zawartością pól tag wszystkich spośród 8 linii wybranego zbioru
Wykrycie zgodności z polem tag oznacza, że szukana linia
przechowuje się w pamięci poręcznej (cache hit)
Jeśli żadne pole tag nie zawiera szukanej wartości, oznacza to, że
bloku o danym adresie nie ma w pamięci podręcznej (cache miss)
Funkcje procesora
Procesor działa na podstawie wykonania programu
przechowywanego w pamięci
Program składa się z elementarnych operacji nazywanych
instrukcjami (lub rozkazami)
Zestaw operacji, które rozpoznaje i może wykonywać procesor,
nazywany jest listą rozkazów procesora
Procesor
Przetwarzanie danych,
sterowanie systemem
na podstawie wykonania
programu
Pamięć
rozkaz
rozkaz
rozkaz
rozkaz
rozkaz
rozkaz
Lista rozkazów procesora
Rozkaz – zakodowane polecenie wykonania elementarnych operacji
np. przesyłanie mem ↔ reg
dodawanie op1 + op2
odejmowanie op1 – op2
operacja logiczna op1 AND op2
przesunięcie >> op
Każdy rozkaz przechowywany jest w pos...