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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

ASK M10 S01.png

ASK M10 S02.png

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ń.


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.


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.


ASK M10 S06.png

...


ASK M10 S07.png

...


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.


ASK M10 S09.png

...


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.


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.


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.


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.


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.


ASK M10 S15.png

...


ASK M10 S16.png

...


ASK M10 S17.png

...


ASK M10 S18.png

...


ASK M10 S19.png

...


ASK M10 S20.png

...


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.


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.


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).


ASK M10 S24.png

...


ASK M10 S25.png

...


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.


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.


ASK M10 S28.png

...


ASK M10 S29.png

...


ASK M10 S30.png

...


ASK M10 S31.png

...


ASK M10 S32.png

...


ASK M10 S33.png

...


ASK M10 S34.png

...