Techniki zwiększania wydajności procesorów

czas /zadanie =(czas /takt) x (takty /rozkaz) x (rozkazy /zadanie) = Cx T x R

gdzie C: czas przypadający na takt zegarowy,

T: liczba taktów zegarowych na rozkaz,

R: liczba rozkazów na zadanie

Zwiększenie wydajności procesora może być osiągnięte przez

zmniejszenie dowolnego z tych czynników, przy czym iloczyn dwóch
pierwszych czyli C x T jest czasem trwania cyklu rozkazowego. Czynniki te
są od siebie zależne: zwiększenie częstotliwości generatora zegarowego
(zmniejszenie taktu) powoduje zmniejszenie liczby operacji elementarnych,
jakie mogą być wykonane w jednym takcie przy danej technologii i
architekturze. To z kolei powoduje zwiększenie liczby taktów dla realizacji
rozkazu. W klasycznych procesorach, CISC (Complex Instruction Set
Computer) czas trwania taktu jest dobierany tak, aby w okresie jego trwania
było możliwe wykonanie operacji elementarnej. Prostsze rozkazy, składające się
z mniejszej liczby operacji elementarnych będą wymagały mniejszej liczby
taktów, bardziej złożone – więcej.

Rozkazy:

prosty

złożony prosty

prosty

Liczba taktów na rozkaz: zmniejszenie liczby taktów zegarowych w

cyklu rozkazowym prowadzi na ogół do wydłużenia taktu zegarowego. Metodą,
pozwalającą na zmniejszenie średniej liczby taktów na rozkaz bez wydłużania
taktu zegarowego (czyli nie “więcej krótkich albo mniej długich”, ale mniej
krótkich) jest metoda strumieniowego wykonywania rozkazów, tzw. pipelining
processing.

Jeśli cały proces przetwarzania rozkazu podzielić na prostsze fazy, które

mogą być niezależnie wykonywane przez różne podzespoły, to wydajność
procesu się zwiększy. Istotą takiego sposobu przetwarzania jest obecność w
procesorze kilku rozkazów w różnych fazach przetwarzania, maksymalnie tylu,
ile jest niezależnych elementów przetwarzających.

Czas przetwarzania pojedynczego rozkazu nie zmienia się w porównaniu

z indywidualnym przetwarzaniem każdego rozkazu, ale “gotowe” rozkazy
pojawiają się na wyjściu z większą częstotliwością. Zwiększa się więc średnia
liczba przetwarzanych rozkazów w jednostce czasu.

Strategia przetwarzania potokowego

Rozpatrzymy prosty podział przetwarzania rozkazu na dwa etapy:

!"

pobranie rozkazu,

!"

dekodowanie rozkazu.

Potok przebiega na 2 niezależnych etapach (dwa stanowiska obsługi):

!"

pobranie i zbuforowanie rozkazu,

!"

wykonywanie rozkazu.

Schemat poszerzony:









Ograniczenia:

1. Czas wykonywania jest na ogół dłuższy niż czas pobierania.
2. Rozkaz skoku warunkowego powoduje, że adres następnego rozkazu

przewidzianego do pobrania jest nieznany. Wobec tego realizacja
etapu pobierania może nastąpić dopiero po otrzymaniu adresu
następnego rozkazu, który zostanie określony po zakończeniu etapu
wykonywania.

Strata czasu z drugiego powodu może być zmniejszona przez proste
zgadywanie. Gdy rozkaz rozgałęzienia warunkowego przechodzi z etapu
pobierania do etapu wykonywania, na etapie pobierania następuje
pobranie następnego rozkazu z pamięci (po rozkazie rozgałęzienia).
Jeśli nie nastąpi rozgałęzienie, czas nie jest stracony. Gdy jednak
rozgałęzienie nastąpi, pobrany rozkaz musi być usunięty, a pobrany
nowy.

Pobieranie

Wykonywanie

Pobieranie

Wykonywanie

Rozkaz

Wynik

Rozkaz

Wynik

Rozkaz

Rozkaz

Oczekiwanie

Oczekiwanie

Nowy adres

Rozkaz odrzucony

Kluczowym zagadnieniem w organizacji potokowego przetwarzania

rozkazów jest podział cyklu rozkazowego na fazy. Minimalnie liczba faz
wynosi 4, a niekiedy jest ich kilkanaście !.

Fetch: faza pobrania rozkazów z PAO do wewnętrznego rejestru

rozkazów lub wewnętrznej kolejki rozkazów, umieszczonej w pamięci
cache instrukcji;

Decode: faza dekodowania rozkazów, w czasie której następuje

dekodowanie rozkazu i ustalane jest połączenie arytmometru z
rejestrami, zawierającymi argumenty. Niekiedy do tej fazy zalicza się
także pobranie argumentów z rejestrów uniwersalnych do rejestrów
roboczych arytmometru;

Execute: faza wykonania rozkazu. W przypadku rozkazów

arytmetyczno-logicznych, w arytmometrze wykonywana jest operacja,
ustalona na podstawie kodu rozkazu. W przypadku

rozkazów komunikacji z

pamięcią w fazie tej jest obliczany adres fizyczny argumentu. Niekiedy faza ta może
trwać więcej niż jeden takt zegarowy.

Write: faza zapisu wyniku. W przypadku rozkazu arytmetyczno-

logicznego wynik operacji zapisywany jest w docelowym rejestrze
uniwersalnym, dla rozkazów komunikacji z PAO realizowany jest cykl
odczytu / zapisu.

Proces przetwarzania potokowego będzie najbardziej efektywny, jeśli

wszystkie fazy będą miały taki sam czas trwania, który może być przyjęty jako
czas taktu zegarowego.

F D E W
F

D

E

W

F

D

E

W

Przetwarzanie sekwencyjne (skalarne) - w obserwowanym czasie zostaną
wykonane 3 rozkazy.

F

D

E

W

F

D

E

W

F

D

E

W

F

D

E

W

F

D

E

W

F

D

E

W

F

D

E

W

F

D

E

W

F

D

E

W

F

D

E

F

D

F

Przetwarzanie potokowe - w obserwowanym czasie wykonanych
zostanie 9 rozkazów, a 3 dalsze zostaną rozpoczęte. Proces
przetwarzania rozpoczyna się tu od momentu, gdy linia przetwarzania
była pusta. Początkowo nie wszystkie fazy są obciążone, stan ustalony
rozpoczyna się dopiero od wykonania rozkazu czwartego.
W stanie ustalonym w czasie jednego cyklu rozkazowego kończone
są 4 rozkazy !!!

Rozkaz 1

Takty zegara

Rozkaz 2

Oznacza to, że maksymalna efektywność przetwarzania potokowego
wzrasta z krotnością, równą liczbie faz. Średnia liczba taktów na rozkaz
wynosi wtedy jeden. Tak więc średni czas zakończenia rozkazu wynosi
wtedy 1 takt zegarowy !!!

Należy podkreślić, że wynik tez uzyskuje się przy dwóch bardzo
ważnych w rzeczywistych systemach założeniach:
1 - jednakowy czas trwania wszystkich faz równy jeden takt,
2 - brak konfliktów.

Przy zastosowaniu środków, wprowadzających nadmiarowości np. kilka
takich samych zasobów, część konfliktów zasobów można rozwiązać i
uzyskać średni prawdziwy wynik powyżej jednego zakończonego
rozkazu na jeden takt zegarowy.

W przetwarzaniu potokowym pojawiają się nowe problemy, nie
występujące przy przetwarzaniu indywidualnym:
elementy przetwarzające, pracujące na różnych warstwach (stage- etap,
okres, stadium), mogą odwoływać się do tych samych elementów
architektury komputera. Jeśli elementy te są zajęte, dana faza
przetwarzania musi zostać wstrzymana, co powoduje wydłużenie czasu
trwania fazy.

Dany element przetwarzający może rozpocząć swoją pracę

dopiero wtedy, gdy zakończył ją poprzednik, wobec tego wydłużenie faz
może się propagować na następne warstwy.

Wreszcie warunki pracy w potoku mogą być takie, że element

przetwarzający, który zakończył swoją pracę nad danym rozkazem może
rozpocząć przetwarzanie następnego dopiero wtedy, gdy następca
odbierze obsłużony obiekt. Wykonanie następnego rozkazu może też
zależeć od wyników rozkazu poprzedniego, który nie został jeszcze
zakończony. Zależność taka ma miejsce, gdy argumentem pewnego
rozkazu jest wynik rozkazu poprzedniego, lub gdy wykonanie
następnego rozkazu jest zależne od stanu flag, ustawionych w rozkazie
poprzednim - przypadek skoków warunkowych, od których zależy wybór
drogi wykonania programu.

Konflikty, występujące w czasie przetwarzania potokowego, które

w literaturze nosi również nazwę strumieniowego, muszą być
rozstrzygane jak najszybciej, a więc w sposób sprzętowy i można je
podzielić na 3 kategorie:

1. Konflikt zasobów: ten sam zasób (np. arytmometr, rejestr

uniwersalny, magistrala lub pamięć) jest wykorzystywany przez 2 lub
więcej fazy równocześnie. W co najmniej jednej z nich musi więc
wystąpić czas oczekiwania.

2. Konflikt danych: argumentem następnego rozkazu jest rezultat

poprzedniego, jeszcze nie zakończonego

3. Konflikt sterowania: rozkaz skoku warunkowego, zależny od

stanu wskaźników, ustawianych przez rozkaz poprzedni.

Można wyróżnić jeszcze czwarty rodzaj konfliktów, wynikający z faktu, że w trakcie

wykonania każdego rozkazu mogą powstać sytuacje wyjątkowe, uniemożliwiające poprawne
zakończenie rozkazu (np. błędy adresacji czy dzielenie przez zero). Sytuacje takie są zwykle
obsługiwane w procesorze za pomocą mechanizmu przerwań wewnętrznych, zwanych w
nomenklaturze Intela wyjątkami (exeptions). Dla zapewnienia prawidłowej obsługi takich
sytuacji, które są de facto wykonaniami niejawnych skoków do procedur obsługi wyjątków,
wszystkie rozkazy, znajdujące się w głównym strumieniu rozkazów przed rozkazem, który
spowodował wyjątek, muszą zostać zakończone.

Rozwiązywanie konfliktów

Konflikt zasobów: dwie lub więcej faz usiłuje skorzystać z tego samego
zasobu. Jeśli przyjąć podział rozkazu na 4 omówione wcześniej fazy, to konflikt
do arytmometru nie wystąpi nigdy, bowiem fazy Execute różnych rozkazów nie
nakładają się w czasie. Dostęp do rejestrów może być konfliktowy, gdyż w fazie
Execute pobierane są z nich argumenty, a w fazie Write są do nich zapisywane
wyniki.

Rozwiązaniem jest tzw. multiple port register file, czyli udostępnienie każdemu
rejestrowi niezależnych połączeń z każdą fazą. Wtedy konflikt miałby miejsce
tylko przy próbie użycia tego samego rejestru, ale to już zadanie kompilatorów
optymalizujących lub samodzielnej uważnej gospodarki rejestrami.

Najtrudniejsze do usunięcia są konflikty w dostępie do pamięci, gdyż kontakt z PAO zachodzi
w fazach Fetch i Write. W celu zmniejszenia częstotliwości występowania takich konfliktów
wyposaża się procesor w dodatkowy blok rejestrów, zwany kolejką pobierania wstępnego lub
prefetcherem, do której są pobierane na zapas rozkazy do wykonania w czasie, gdy pamięć nie
jest zajęta w fazie Write.

Oczywiście faza Write może nastąpić w sytuacji, gdy kolejka jest pusta i wtedy musi być
wprowadzony takt oczekiwania.

Całkowitą eliminację konfliktów w dostępie do pamięci można
uzyskać poprzez niezależne stworzenie dróg dostępu dla pobierania
rozkazów i osobno dla odczytu/ zapisu danych. Ponieważ zwykle
rozkazy są w segmencie kodu, a dane w segmencie danych, to konflikt
dostępu do tej samej komórki nie powinien wystąpić. Rozwiązanie to
wymaga zastosowanie specjalnego bloku pamięci, umożliwiającego
jednoczesny dostęp do dwóch różnych komórek - tzw. pamięć
dwuportowa.

Architektura z rozdzieloną pamięcią danych i rozkazów nazywa się
architekturą typu Harvard..

Konflikt danych: występuje, gdy wykonywanie rozkazu musi być
wstrzymane z powodu niedostępności argumentu, będącego rezultatem
wcześniejszego, nie zakończonego jeszcze rozkazu. Rozważmy
przykład obliczania średniej arytmetycznej dwóch liczb, znajdujących się
w rejestrach r1 i r2:

add r1, r2 ;

r1 := r1 + r2

shr r1, 1 ;

r1 := r1 / 2

Jeżeli rozkazy te są wykonywane w trybie potokowym, to argument w r1
jest wymagany przez shr w czasie, gdy jest on dopiero obliczany w add:

F D E argument w

r1 obliczany

W argument
do r1
zapisywany

F

D

argument w

r1 potrzebny

E W

Poprawność działania procesora można uzyskać w tej sytuacji przez wstawienie taktów
oczekiwania za pomocą instrukcji pustej NOP, dzielącej oba rozważane rozkazy, ale
spowoduje to obniżenie wydajności. Gdyby można wykonać w tym czasie inny, użyteczny
rozkaz, nie powodujący konfliktów, spadek wydajności by nie wystąpił, ale często nie ma
takiej możliwości. W bardziej wyrafinowanych konstrukcjach stosuje się inne rozwiązanie
tego problemu, a mianowicie zmianę przez procesor kolejności wykonania rozkazów w
stosunku do tej, jaka była zapisana w programie (out of order execution). Jeśli mechanizm
kontroli gotowości argumentów wskaże, że oczekujący rozkaz nie może go otrzymać, jest on
wyłączany z głównego ciągu przetwarzania i oczekuje “z boku” na dostępność “swojego”
argumentu. Po zaistnieniu odpowiednich warunków jego wykonanie jest wznawiane. Pojawia
się tu jedna problem obsługi wyjątków powodowanych przez rozkazy znajdujące się poza
kolejnością, co wymaga stosowania mechanizmów synchronizacji programu.

Konflikt sterowania: prawidłowa realizacja rozkazów, zmieniających
kolejność pobierania rozkazów (jump, call, ret) stanowi najtrudniejszy
problem w przetwarzaniu potokowym. W czasie wykonywania rozkazu
skoku jest obliczony adres następnego rozkazu, który staje się dostępny
później, niż wymaga tego faza pobrania następnego rozkazu.

F D

po

zakończeniu
adres
docelowy jest
dostępny

E W

X X X szczelina

czasowa

F D

E

W

Aby zmniejszyć wpływ tego opóźnienia, adres skoku powinien być obliczany w fazie
dekodowania rozkazu skokowego. Można też stosować tzw. metodę skoku opóźnionego
(delayed branch), która polega na wykonaniu przed rozkazem skoku jednego rozkazu,
występującego w programie bezpośrednio za rozkazem skokowym.
Przy skokach warunkowych wprowadza się kilka kopii rejestru flag i jeśli zawartość
odpowiedniego rejestru warunku nie jest ustalona przed rozpoczęciem wykonywania skoku, to
wykonywana jest sprzętowa predykcja skuteczności skoku i zgodnie z tym przewidywaniem
pobierane są kolejne rozkazy do przetwarzania. Po zakończeniu cyklu rozkazowego rozkazu
skoku warunkowego następuje sprawdzenie zgodności warunku przewidywanego z
zaistniałym i jeśli zgodność istnieje, to przetwarzanie jest kontynuowane bez straty czasu.
W przypadku błędnej predykcji operacje we wszystkich fazach są kasowane i proces
przetwarzania potokowego wykonywany jest od początku - bardzo kosztowne czasowo
!!!

Postępowanie z rozgałęzieniami

!"

zwielokrotnienie strumienia,

!"

pobieranie docelowego rozkazu z wyprzedzaniem,

!"

bufor pętli,

!"

przewidywanie rozgałęzienia,

!"

opóźnione rozgałęzienie.

Zwielokrotnienie strumienia

Polega na powieleniu początkowych etapów potoku i umożliwieniu
równoczesnego pobrania obu rozkazów za pomocą dwóch strumieni.
Rozwiązanie to stwarza pewne problemy:
1. W przypadku zwielokrotnionego strumienia występują opóźnienia,

wynikające z rywalizacji o dostęp do rejestrów i pamięci;

2. Mogą pojawić się następne rozkazy rozgałęzienia, zanim zostanie

rozstrzygnięte dane rozgałęzienie. Każdy taki rozkaz wymaga
dodatkowego strumienia.

Przykład maszyn w dwoma i większą liczbą strumieni:
IBM 370/168, IBM 3033.


Pobieranie docelowego rozkazu z wyprzedzaniem
Gdy rozpoznany jest rozkaz rozgałęzienia warunkowego, następuje
wyprzedzające pobranie rozkazu docelowego razem z rozkazem
następującym po rozgałęzieniu. Rozkaz docelowy jest następnie
zachowywany, aż do czasu wykonania rozgałęzienia.

Rozwiązanie to zastosowano w IBM 360/91

Bufor pętli

Bufor pętli jest małą, bardzo szybką pamięcią związaną z etapem
pobierania rozkazów potoku. Zawiera on n ostatnio pobranych
rozkazów. Jeśli ma nastąpić rozgałęzienie, sprawdza się najpierw, czy
cel rozgałęzienia znajduje się wewnątrz bufora. Jeśli tak, to pobierany
jest rozkaz z bufora.















Trzy podstawowe zalety bufora pętli:
1. Dzięki pobieraniu z wyprzedzeniem bufor pętli zawiera rozkazy

następujące kolejno po adresie bieżącego rozkazu.

2. Jeśli następuje rozgałęzienie do rozkazu znajdującego się o kilka

pozycji dalej od adresu rozkazu rozgałęzienia, to rozkaz docelowy
będzie już znajdował się w buforze. Szczególnie użyteczne dla
sekwencji IF-THEN oraz IF-THEN-ELSE.

3. Jeżeli bufor zmieści wszystkie rozkazy składające się na pętlę, to

rozkazy te musza być pobrane tylko raz, przy pierwszej iteracji.

Bufor pętli jest w zasadzie podobny do dedykowanej rozkazom pamięci
podręcznej. Różnica polega na tym, że bufor pętli zawiera tylko
sekwencje rozkazów i jest o wiele mniejszy.

Przykłady zastosowania: maszyny CDC (Star 660, 7600) oraz CRAY-1.

Adres rozgałęzienia

Bufor pętli

(256 bajtów)

Porównanie najbardziej znaczących bitów
adresu w celu stwierdzenia trafienia

8

Rozkaz, który ma być
dekodowany w przypadku
trafienia

Przewidywanie rozgałęzienia
Strategie statyczne:
- przewidywanie zawsze następującego rozgałęzienia,
- przewidywanie nigdy nie następującego rozgałęzienia,
- przewidywanie za pomocą kodu operacji.

Strategie dynamiczne:
- przełącznik nastąpiło /nie nastąpiło,
- tablica historii rozgałęzień.

Tablica historii rozgałęzień jest małą pamięcią podręczną, powiązaną z
etapem pobierania rozkazu w potoku. Każdy zapis w tablicy składa się z
trzech elementów:
- adresu rozkazu rozgałęzienia,
- pewnej liczby bitów historii,
- informacji o rozkazie docelowym (adres rozkazu lub sam rozkaz).

Adres

rozkazu

rozgałęzienia

Adres

celu

Stan

.
.
.

.
.
.

.
.
.

Wy

bó

r

IPFAR

Następny
adres
w kolejności

Pamięć

Układy logiczne

BHT

*

Skieruj ponownie

Aktualizuj stan

Dodaj nowy

zapis

E

Czy są granice zwiększania wydajności poprzez wydzielenie
większej liczby faz wykonania rozkazu?

1. Na każdym etapie potoku występuje pewien narzut związany z

przenoszeniem danych z bufora do bufora oraz z wykonywaniem
różnych działań przygotowawczych.

2. Liczba układów logicznych wymaganych do zapobiegania

konfliktom rejestrów i pamięci oraz do optymalizacji potoku
wzrasta znacząco wraz z liczba faz (etapów). Może to prowadzić
do sytuacji, gdy układy logiczne sterujące przejściami między
etapami są bardziej złożone niż układy sterujące wykonaniem
etapów.