ak-teoria Flashcards
Opisz cechy architektury CISC
Rozwinięcie -
Complex Instruction Set Computers
Cechy:
wolne, małe i drogie pamięci, nieduża liczba rejestrów, model obliczeń pamięć - pamięć, duża(kompletna) liczba rozkazów, słaba skalowalność, dużo trybów adresowania, niejednorodna forma rozkazów
Opisz cechy architektury RISC
Rozwinięcie
Reduced Instruction Set Computers
Cechy:
wykonanie jednego rozkazu w jednym cyklu maszynowym, stała długość i prosty format rozkazu, nieduża liczba trybów adresowania, niezbyt obszerna lista rozkazów, model obliczeń rejestr-rejestr, dostęp do pamięci operacyjnej tylko w rozkazach LOAD i STORE, duży zbiór rejestrów uniwersalnych, układ sterowania – logika szyta, intensywne wykorzystanie przetwarzania potokowego, kompilatory o dużych możliwościach optymalizacji potoku rozkazów
Opisz rejestry architektury RISC
łącznie w bloku 32 - wysokie (6), lokalne (10), niskie (6), globalne (10),
łącznie łącznie 138
Rejestry niskie jednej procedury stają się rejestrami wysokimi następnej
Porównaj architekturę CISC i RISC
Trybów adresowania: dużo | mało
Model obliczeń: pamięć - pamięć | rejestr- rejestr
Rozmiar rozkazu: zmienny | stały
Ilość rozkazów: dużo | mało
Rejestrów uniwersalnych: mało | dużo
Wykonywanie rozkazów w jednym cyklu maszynowym: nie | tak
Gdzie jest wykorzystywane potokowanie rozkazów
wszędzie do CISC
Jakie są efekty przetwarzania potokowego
zrównoleglenie realizacji ciągu rozkazów, skrócenie czasu realizacji ciągu rozkazów
Dodatkowe rejestry wykorzystywane przez jednostki potokowe
rejestry zatrzaskowe
Rodzaje hazardów - wymień wszystkie wszystkie
Hazard danych, hazard zasobów, hazard sterowania. W hazardzie danych dodatkowo: prawdziwa zależność danych (Read After Write - RAW), zależność wyjściowa (Write After Write - WAW), antyzależność (Write After Read - WAR)
Opisz hazard danych
Zależności między argumentami kolejnych rozkazów.
Metody usuwania hazardu danych
wykrywanie na etapie kompilacji i modyfikacja programu:
- wstawieni rozkazu NOP - wada to strata taktu zegarowego,
- zamiana kolejności rozkazów - brak strata taktu zegarowego.
sprzętowe rozwiązanie:
- wstrzymanie napełniania potoku
wyprzedzające pobieranie argumentów (też do superskalarnej) –||-- Przykład: ADD r1, r2, r3 sub r4, r5, r1
Dla architektury superskalarnej:
Przemianowanie rejestrów - dynamiczne przypisywanie rejestrów. Gdy chcemy zapisać dane do jakiegoś rejestru to tworzy się jego kopie, jeżeli znod chcemy się odwołać do tego rejestru co ostatnio ro rozkaz musi przejść proces przemianowania. Przemianowanie dotyczy tylko fragmentu programu w aktualnym oknie. Dokonuje się go z użyciem stacjami rezerwacji (RS) lub rejestrami roboczymi. Algorytm Tomasulo rozwiązuje problem przemianowania rejestrów.
I1: r1b
Opisz hazard zasobów
Konflikt w dostępie do rejestrów lub do pamięci
Metody usuwania hazardu zasobów:
Rozdzielenie pamięci podręcznej poziomu L1 na pamięć rozkazów (programu) IM i pamięć danych DM pozwala uniknąć tego hazardu.
Dla hazardu dotyczącego dostępu do rejestrów założono, że operacja zapisu ma miejsce w pierwszej połowie taktu, a operacja odczytu w drugiej połowie.
Opisz hazard sterowania
Problemy z potokową realizacją skoków i rozgałęzień - po wykonaniu skoku trzeba usunąć z potoku rozkazy pobrane po skopu, w wypadku nietrafionego przewidywania trzeba się cofnąć.
Metody usuwania hazardu sterowania oraz potokowym wykonywaniem rozgałęzień
Wstrzymanie napełniania potoku po zdekodowaniu rozkazu skoku (rozgałęzienia) - prawdopodobnie strata trzech taktów,
skoki opóźnione - muszą być uwzględnione przez programistę, zapewnia pewne oszczędności czasowe, efekt skoku opóźniony o jeden rozkaz, uproszczenie układu sterowania
Problemy dwóch powyższych rozwiązań - trzeba wyczyścić potok w zależności od wykonania bądź nie skoku
przewidywanie rozgałęzień -
statyczne (zawsze skocz, albo nigdy nie skacz, podejmowanie decyzji na podstawie kodu rozkazu rozgałęzienia aka specjalny bit-wskazówka) || (przewidywanie, że skok wstecz względem licznika rozkazów zawsze nastąpi, przewidywanie, że skok do przodu względem licznika rozkazów nigdy nie nastąpi)
dynamiczne (historia rozgałęzień i na jej podstawie)
Operacje wykonywane na tablicy historii rozgałęzień
Sprawdzenie, po pobraniu rozkazu rozgałęzienia jako kolejnego rozkazu,
czy adres tego rozgałęzienia jest w tablicy:
• Nie – wtedy:
− przewidywanie rozgałęzienia jest wykonywane według jednej ze strategii statycznych
− do tablicy jest wpisywany adres rozkazu rozgałęzienia oraz informacja o wykonaniu/niewykonaniu rozgałęzienia (bit historii)
• Tak – wtedy:
− przewidywanie rozgałęzienia jest wykonywane według bitu historii
(przewidywanie, że będzie tak jak poprzednio)
− do tablicy jest wpisywana informacja o wykonaniu/niewykonaniu
rozgałęzienia (uaktualnienie bitu historii)
Opisz prawdziwą zależność danych
(Read After Write - RAW)
Przykład
I1: r1
Opisz zależność wyjściową
(Write After Write - WAW)
Przykład
I1: r1
Opisz antyzależność
(Write After Read - WAR)
W przypadku równoległej realizacji rozkazów I2 o raz I3, wykonanie rozazu I3 (zapis wyniku) nie może być zakończone, dopuki nie nastąpi pobranie argumentu (odczyt) w rozkazie I2. Analogiczna sytuacja dla rozkazów I3 i I4
Przykład
I1: r1
Co to jest aliasing (hazard sterowania)
Aliasing – sytuacja, dla której dwom różnym rozkazom skoków warunkowych (rozgałęzień) przypisana zostaje ta sama pozycja w tablicy historii rozgałęzień (w wyniku zgodności wybranych m bitów adresów tych skoków) - i tak można przewidywać rozgałęzienia
Predyktora Smith’a
Predyktora Smith’a - 4-stanowy (2 bitowy licznik z nasyceniem):
– dobry dla rozgałęzień powtarzalnych - eliminuje pierwszy błąd
przewidywania rozgałęzień dla zagnieżdżonych pętli
– zły dla często się zmieniających
Co to BTB
BTB (ang. Branch Target Buffer) - miejsce w którym są zapisywane adresy docelowe wykonywanych skoków
Operacje zmiennoprzecinkowe - cechy
Wykonanie
wykonywane zazwyczaj w wielu taktach
Moc komputerów:
podawana w ilości operacji zmiennoprzecinkowych na sekundę, glops
Problem
często jest wymagane wstrzymanie napełniania potoku dla uniknięcia hazardu danych
Architektura superskalarna - cechy
zawiera kilka potokowych jednostek funkcjonalnych, złożone układy przewidywania rozgałęzienia, wykonywanie kilku rozkazów w jednym takcie, pobieranie kilku rozkazów w jednym takcie, niekolejne wykonywanie rozkazów, spekulatywne wykonywanie rozkazów
Etapy rozkazów w procesorach superskalarnych
Pobieranie i inicjowanie rozkazów, wykonywanie rozkazów, zatwierdzenie rozkazów
Etap pobierania i inicjowanie rozkazów (architektura superskalarna)
Pobieranie - rozkazy pobierane w paczkach i ładowane do kolejki, w wypadku rozkazów rozgałęzień przewiduje się ich wykonanie po ich wykryciu.
Inicjowanie i rozsyłanie - pobieranie i dekodowanie rozkazów z kolejki, sprawdza się czy występuje hazard danych - jeżeli tak to przemianowuje się rejestry, pobierania argumentów, przekierowanie do kolejki przed jednostkami funkcjonalnymi (stacji rezerwacji). Tutaj też się potencjalnie przemianował rejestry
wykonywanie rozkazów (architektura superskalarna)
warunek - skompletowanie argumentów rozkazu, kolejność dowolna (out-of-order, niekolejne wykonywanie rozkazów - może doprowadzić do antyzależności lub zależności wyjściowej), w wypadku rozgałęzień - spekulatywne wykonywanie rozkazów,
zatwierdzenie rozkazów (architektura superskalarna)
zapisywanie wyniku, ale już w kolejności zgodnej z programem, przy rozgałęzieniach trzeba uzyskać potwierdzenie ich poprawności, zatwierdzanie - zapis wyników do rejestrów lub pamięci po czym są usuwane, tylko rozkazy wykonane legalnie (prawidłowa spekulacja rozgałęzienia) są zapisywane, tutaj podejmuje się decyzję o obsłudze wyjątku
Funkcje buforów LOAD (architektura superskalarna)
przechowywanie składników adresu efektywnego, śledzenie niewykonanych rozkazów LOAD czekających na dostęp do pamięci, przechowywanie wyników rozkazów LOAD czekających na dostęp do CDB
Funkcje buforów STORE: (architektura superskalarna)
przechowywanie składników adresu efektywnego, przechowywanie docelowego adresu pamięci niewykonanych jeszcze rozkazów STORE, czekających na dane, które mają być
zapisane w pamięci, przechowywanie adresów i danych rozkazów STORE czekających
na dostęp do pamięci
Bufory LOAD i STORE (architektura superskalarna)
Bardzo podobne do stacji rezerwacji (takie obszar gdzie czekają rozkazy do przetworzenia)
Problemy przesyłu wyników przez CBD (architektura superskalarna)
Wymaga jednego taktu po wykonaniu operacji w jednostce funkcjonalnej, przesyłany jest wynik operacji oraz etykieta stacji rezerwacji, z której pochodził wykonywany rozkaz, założono, że linie przesyłu danych i etykiet są zdublowane, co pozwala przesłać wyniki dwóch rozkazów w jednym takcie
Bufor zmiany kolejności (ReOrder Buffer - ROB) (architektura superskalarna)
- Przechowuje kopie rozkazów, uporządkowane zgodnie z kolejnością wystąpienia w programie (in-order), od momentu zainicjowania rozkazu do momentu zatwierdzenia i usunięcia rozkazu z procesora.
- Umożliwia dołączenia do rozkazów wyników ich wykonania - wyniki te są przechowywane pomiędzy wykonaniem rozkazu a momentem zatwierdzenia rozkazu. W tym czasie ROB jest źródłem argumentów dla innych rozkazów, wyniki niezatwierdzonych rozkazów nie są bowiem jeszcze zapisane w rejestrach programowych.
- Jest podstawą zatwierdzania rozkazów – w kolejnym takcie zegara jest zatwierdzany rozkaz (rozkazy) zajmujący szczytową pozycję bufora ROB, jeśli został już wykonany. W trakcie zatwierdzania wynik rozkazu jest przepisywany do rejestru wynikowego (programowego).
Struktura: rozkaz, wynik, rejestr, gotowy, zajęcy, WS i WK
nazwa wariantu architektury superskalarnej gdzie jest długie słowo
Architektura procesorów o bardzo długim słowie rozkazowym - (VLIW - Very Long Instruction Word)
Szeregowanie rozkazów - tworzenia grup (VLIW)
- Podział rozkazów programu na grupy – brak zależności w grupie
- Możliwość równoległej realizacji rozkazów w ramach grupy
- Sekwencyjne wykonywanie grup
- Podział grupy na paczki („długie” rozkazy)
- Paczka = 3 rozkazy + szablon (3 x 41 + 5 = 128 bitów)
- Szablon – informacja o jednostkach funkcjonalnych, do których kierowane mają być rozkazy i ewentualna informacja o granicach grup w ramach paczki
Rozkazy uwarunkowane (VLIM)
Rozkazy uwarunkowanie - predykcja rozkazów. Uwzględnianie warunku w trakcie realizacji rozkazu.
Wielowątkowość
Cecha systemu operacyjnego umożliwiająca wykonywanie kilku wątków w ramach jednego procesu, cecha procesora oznaczająca możliwość jednoczesnego wykonywanie kilku wątków w ramach jednego procesora (rdzenia)
Warianty wielowątkowości
Realizacja kilku wątków w jednym procesorze (rdzeniu), przełączanie wątków przez system operacyjny, realizacja każdego wątku w oddzielnym rdzeniu, realizacja kilku wątków w jednym rdzeniu – procesor ze sprzętowym sterowaniem wielowątkowością
Cele współbieżnej realizacji wątków w jednym procesorze:
minimalizacja strat cykli powstałych w trakcie realizacji pojedynczego wątku w wyniku:
- chybionych odwołań do pamięci podręcznej,
- błędów w przewidywaniu rozgałęzień,
- zależności między argumentami kolejnych rozkazów
Rodzaje modeli sprzętowego sterowania wielowątkowością
wielowątkowość drobnoziarnista, wielowątkowość gruboziarnista, wielowątkowość jednoczesna (współbieżna)
Wielowątkowość drobnoziarnista (fine-grained multithreading)
przełączanie wątków po każdym takcie, wątek oczekujący jest pomijany
Właściwości: unikanie strat przy nawet krótkich opóźnieniach wątków, wymagane jest szybkie przełączanie wątków, opóźnienie realizacji wątków w pełni gotowych do wykonania,
w jednym takcie do jednostek funkcjonalnych wprowadzane są rozkazy tylko jednego wątku
Wielowątkowość gruboziarnista (coarse-grained multithreading)
właściwości: szybkie wykonanie wątków z dostępnymi danymi, strata czasu przy krótkich opóźnieniach potoku, wątek realizowany w kolejnych taktach do momentu wstrzymania wykonania rozkazu tego wątku (zwykle z powodu chybienia odwołania do PaP), w jednym takcie do jednostek funkcjonalnych wprowadzane są rozkazy tylko jednego wątku
wielowątkowość jednoczesna (współbieżna)
W jednym takcie mogą być inicjowane i wprowadzane do jednostek funkcjonalnych rozkazy różnych (wielu) wątków
Rywalizacja watków w dostępie do pamięci podręcznej:
• mniejsza wielkość PaP przypadająca na wątek
• Większe zużycie energii (w porównaniu z procesorami dwurdzeniowymi)
• Możliwość monitorowanie wykonania jednego wątku przez inny wątek (złośliwy), poprzez wpływ na współdzielone dane pamięci podręcznej - kradzież kluczy kryptograficznych
wymogi wielowątkowości:
- układy współdzielone – układy pracujące bez wyróżniania wątków
- układy dublowane (powielane) – każdy wątek (grupa wątków) wykorzystuje oddzielny układ
- układy partycjonowane – część układów (rejestrów, kolejek) przypisana oddzielnym wątkom (grupom wątków)
- powielenie zestawów rejestrów uniwersalnych (lub • powielenie tabel mapowania rejestrów)
- powielenie liczników rozkazów
- powielenie układów dostępu do pamięci podręcznej (tabel stron)
- powielenie sterowników przerwań
Równoległość na poziomie rozkazów
ILP – Instruction Level Parallelism (wykonywanie w danej chwili wielu rozkazów w jednym procesorze)
• potokowa organizacja procesora,
• architektura superskalarna z wieloma potokowymi jednostkami wykonawczymi,
• architektura VLIW ułatwiająca współbieżne wykonywanie rozkazów,
• sprzętowe sterowanie wielowątkowością.
Równoległość na poziomie procesorów (wykonywanie w danej chwili wielu rozkazów w wielu procesorach)
– Komputery wektorowe
– Komputery macierzowe
– Systemy wieloprocesorowe
– Klastry (systemy wielokomputerowe)
Kategorie (rodzaje) równoległości w aplikacjach
- Równoległość poziomu danych (DLP – Data Level Parallelism) – pojawia się kiedy istnieje wiele danych, które mogą być przetwarzane w tym samym czasie
- Równoległość poziomu zadań (TLP –Task Level Parallelism) – pojawia się kiedy są tworzone zadania, które mogą być wykonywane niezależnie i w większości równolegle
Klasyfikacja Flynna
Liczba strumieni rozkazów i liczba strumieni danych w systemie komputerowym
• SISD: Single Instruction, Single Data Stream
• SIMD: Single Instruction, Multiple Data Stream
• MISD: Multiple Instruction, Single Data Stream
• MIMD: Multiple Instruction, Multiple Data Stream
Drogi wykorzystania równoległości aplikacji w architekturze komputerów
- Przetwarzanie potokowe i superskalarne
- Rozkazy wektorowe w architekturach wektorowych, macierzowych, procesorach graficznych, rozszerzeniach SIMD
- Systemy wieloprocesorowe ze wspólną pamięcią
- Systemy wieloprocesorowe z pamięcią rozproszoną
Przyczyny straty czasu
hazard danych, hazardu sterowania, hazard zasobów, chybione odwołania do pamięci podręcznej( dla wielowątkowości)
Komputery wektorowe (cechy)
Wyróżnia - rozkazy wektorowe
Lokalizacja wektorów danych
- Pamięć operacyjna (STAR 100)
- Rejestry wektorowe (Cray -1)
Przyspieszenie
Przyspieszenie jest stosunkiem czasu wykonywania w komputerze klasycznym (szeregowo) do czasu wykonywania w komputerze wektorowym
Przepustowość
Przepustowość (moc obliczeniowa) jest stosunkiem ilości operacji zmiennoprzecinkowych do czasu ich wykonania.
Hardware
- rozkazy wektorowe
- duża liczba potokowych jednostek arytmetycznych (specjalizowanych)
- duża liczba rejestrów (nawet kilkaset tysięcy)
Software
- klasyczne języki: Fortran, C
- klasyczne algorytmy
- kompilatory wektoryzujace
Wykorzystanie równoległości poziomu danych w formie rozkazów wektorowych w różnych architekturach procesorów
- Komputery macierzowe
- Komputery wektorowe
- Rozszerzenia SIMD współczesnych procesorów superskalarnych
- Procesory graficzne
Dwa różne podejścia do sprzętowej realizacji rozkazów wektorowych
– Komputery (procesory) macierzowe
– Komputery wektorowe
Komputery macierzowe (co to)
Architektura komputerów macierzowych - model SIMD w dwóch wariantach:
SIMD - DM (z pamiecia rozproszona)
SIMD - SM (z pamiecia wspólna)
Elementy komputera macierzowego
•Jednostka sterująca - procesor wykonujący rozkazy sterujące i skalarne oraz inicjujący wykonanie rozkazów wektorowych w sieci elementów przetwarzających.
•Elementy przetwarzające (procesorowe) - jednostki arytmetyczno-logiczne wykonujące operacje elementarne rozkazów wektorowych.
•Sieć łącząca - łączy elementy przetwarzające między sobą lub z modułami pamięci operacyjnej; warianty:
- sieć statyczna: pierścień, gwiazda, krata, drzewo, hipersześcian
- sieć dynamiczna: jednostopniowa; wielostopniowa (wyróżnia połączenia blokujące i nieblokujące).
Podsumowanie
• Architektura SIMD
• Jednostka sterująca + jednostka macierzowa
• Rozkazy wektorowe - wykonywane synchronicznie w sieci (macierzy) EP
• Skomplikowana wymiana danych między EP
•Trudne programowanie - konieczność tworzenia nowych wersji algorytmów