Architektura Komputerów/Wykład 10: Redukcja opóźnień w procesorach superskalarnych i superpotokowych

From Studia Informatyczne


Grafika:ASK_M10_S01.png

Grafika:ASK_M10_S02.png

Grafika:ASK_M10_S03.png

O ile w procesorze jednopotokowym utrata pięciu cykli oznacza utratę czasu wykonania pięciu instrukcji, to w przypadku procesora superskalarnego opóźnienie wyrażone w „straconych” instrukcjach jest tyle razy większe, ile procesor ma potoków.

Duży proporcjonalny spadek wydajności procesorów superskalarnych wynikający z opóźnień powoduje konieczność minimalizacji tych opóźnień.


Grafika:ASK_M10_S04.png

Skoki stanowią znaczny odsetek instrukcji zawartych w programach. Można przyjąć, że ok. 10% wszystkich instrukcji wykonywanych przez procesor stanowią skoki. Architektury superpotokowe i superskalarne charakteryzują się dużymi opóźnieniami skoków, sięgającymi nawet kilkunastu cykli. Mnożąc liczbę cykli procesora przez liczbę instrukcji wykonywanych w każdym cyklu otrzymujemy wartości opóźnień, które po przeliczeniu na procentową utratę wydajności oznaczają, że procesor pracuje z wydajnością nie przekraczającej ¼ tego, czego oczekuje użytkownik.

Aby wydajność procesora była bliska wydajności teoretycznej, niezbędna jest implementacja mechanizmów przyspieszających.


Grafika:ASK_M10_S05.png

Mechanizmy redukcji opóźnień mają charakter heurystyczny. Oznacza to, że procesor próbuje „zgadywać” przebieg wykonania programu i na tej podstawie pobiera i wykonuje kolejne instrukcji. Procesor nie ma pewności, czy „zgadywanie” dało właściwy efekt aż do czasu wykonania instrukcji skoku. Wszystkie instrukcje wykonywane w tym czasie muszą być wykonywane w taki sposób, aby ich wyniki mogły zostać anulowane.

Taki sposób wykonania instrukcji nazywamy spekulatywnym. Współczesne procesory praktycznie przez cały czas pracują spekulatywnie.


Grafika:ASK_M10_S06.png

...


Grafika:ASK_M10_S07.png

...


Grafika:ASK_M10_S08.png

Przewidywanie skoków ma kilka aspektów. Możemy mówić o przewidywaniu wystąpienia instrukcji skoku w programie, przewidywaniu adresu docelowego skoku oraz o przewidywaniu, czy skok warunkowy będzie zrealizowany.


Grafika:ASK_M10_S09.png

...


Grafika:ASK_M10_S10.png

Wszystkie metody przewidywania skoków można podzielić na statyczne i dynamiczne. Metody statyczne, w przeciwieństwie do dynamicznych, nie wymagają gromadzenia przez procesor informacji o historii wykonania programu. Metody statyczne ograniczają się więc do przewidywania sposobu wykonania skoku warunkowego po jego zdekodowaniu przez procesor, kiedy już wiadomo, że instrukcja skoku wystąpiła oraz jaki jest adres docelowy skoku.

Metody dynamiczne polegają na kolekcjonowaniu przez procesor informacji o wykonaniu programu. Na tej podstawie można przewidywać wszystkie wymienione wcześniej aspekty skoków.


Grafika:ASK_M10_S11.png

Przy przewidywaniu statycznym przez kompilator lub programistę, instrukcje skoków warunkowych zostają a priori oznaczone jako prawdopodobne lub nieprawdopodobne. Na tej podstawie procesor będzie podejmował decyzję o sposobie spekulatywnego wykonania skoku po jego zdekodowaniu, a przed właściwym deterministycznym wykonaniem. Taki sposób przewidywania wymaga odmiennego kodowania instrukcji skoków prawdopodobnych i nieprawdopodobnych. Mechanizm taki posiadały m.in. procesory rodziny Alpha AXP i Intel 960. Podobny mechanizm, korzystający z tzw. prefiksów instrukcji, wprowadzono w architekturze Pentium 4.

Przewidywanie przez procesor polega na określaniu prawdopodobieństwa na podstawie kierunku skoku. Korzysta się tu ze szczególnej własności programów.


Grafika:ASK_M10_S12.png

Przewidywanie dynamiczne wymaga umieszczenia w procesorze bloków służących do gromadzenia informacji o wykonaniu skoków.

Główną strukturą jet tu bufor docelowy skoków, gromadzący informacje o wystąpieniach skoków i ich adresach docelowych.

Sam bufor docelowy służy do przewidywania wystąpienia skoku przed jego pobraniem i zdekodowaniem oraz do określenia adresu docelowego takiego skoku.


Grafika:ASK_M10_S13.png

Bufor docelowy bez dodatkowych mechanizmów sprzętowych przewiduje skoki wyłącznie jako bezwarunkowe. Samo przewidywanie opiera się na spełnieniu przez wykonywany program kilku założeń. W przypadku niespełnienia wymienionych założeń, przewidywanie się nie powiedzie.


Grafika:ASK_M10_S14.png

Z przytoczonych wcześniej założeń wynika, że bufor docelowy nie może przewidywać skoków o zmiennym adresie docelowym, ani nie radzi sobie z przewidywaniem skoków warunkowych wykonywanych w różny sposób.

Ponieważ powroty z procedur są jednymi z najczęściej wykonywanych instrukcji, procesor powinien być wyposażony w inny mechanizm umożliwiający ich przewidywanie.


Grafika:ASK_M10_S15.png

...


Grafika:ASK_M10_S16.png

...


Grafika:ASK_M10_S17.png

...


Grafika:ASK_M10_S18.png

...


Grafika:ASK_M10_S19.png

...


Grafika:ASK_M10_S20.png

...


Grafika:ASK_M10_S21.png

Podczas ostatniej iteracji pętli zagnieżdżonej predyktor przewiduje zamknięcie pętli, i jest to oczywiście przewidywanie błędne. Przy wyjściu z pętli predyktor myli się. Po wyjściu z pętli predyktor dwustanowy ustawia przewidywanie skoku zamykającego pętle na NT(PNT). Przy powtórnym wejściu w pętlę predyktor przewiduje opuszczenie pętli, podczas, gdy pętla się zamyka. Po błędzie predyktora następuje zmiana stanu na T(PT). Predyktor myli się więc przy pierwszym i ostatnim obiegu pętli.

W zastosowaniu do skoku wykonywanego naprzemiennie predyktor myli się w każdym wykonaniu.


Grafika:ASK_M10_S22.png

Predyktor czterostanowy działa jak dwubitowy licznik rewersyjny z nasyceniem. W stanach ST i WT mamy przewidywanie PT, a w stanach WNT i SNT PNT.


Grafika:ASK_M10_S23.png

Po serii obiegów pętli predyktor skoku zamykającego pętlę jest w stanie SNT. Przy wyjściu z pętli predyktor błędnie przewiduje zamknięcie, po czym przechodzi w stan WT. Przy następnym wejściu w pętlę predyktor poprawnie przewiduje zamknięcie.

Skok naprzemienny jest przewidywany zawsze tak samo, czyli predyktor myli się w co drugim wykonaniu. Dzieje się tak dzięki temu, że początkowo predyktor ustawie się w stan ST (ew. SNT), po czym oscyluje pomiędzy ST i WT (lub SNT i WNT).


Grafika:ASK_M10_S24.png

...


Grafika:ASK_M10_S25.png

...


Grafika:ASK_M10_S26.png

W schemacie gLocal adres instrukcji skoku wybiera rejestr historii związany z danym skokiem. Zawartość rejestru historii i adres skoku są argumentami funkcji mieszającej, której wartość wybiera jeden z dwu- lub czterostanowych predyktorów.

Jako funkcji mieszającej najczęściej używa się operacji XOR.

Predyktor udziela odpowiedzi na pytanie o prawdopodobieństwo skoku na bazie poprzednich wykonań tego skoku.


Grafika:ASK_M10_S27.png

W schemacie gShare historia wykonań wszystkich skoków przechowywane jest w jednym rejestrze. Zawartość rejestru historii i adres skoku są argumentami funkcji mieszającej, której wartość wybiera jeden z dwu- lub czterostanowych predyktorów.

Predyktor udziela odpowiedzi na pytanie o prawdopodobieństwo skoku na bazie poprzednich wykonań wszystkich ostatnio wykonywanych skoków.


Grafika:ASK_M10_S28.png

...


Grafika:ASK_M10_S29.png

...


Grafika:ASK_M10_S30.png

...


Grafika:ASK_M10_S31.png

...


Grafika:ASK_M10_S32.png

...


Grafika:ASK_M10_S33.png

...


Grafika:ASK_M10_S34.png

...