1.
Przewidywanie rozgałęzienia sprzętu komputerowego.
-najprostszym dynamicznym schematem przewidywania rozgałęzienia jest bufor przewidywania rozgałęzienia lub tabela historii rozgałęzienia.
- bufor przewidywania rozgałęzienia jest to mała pamięć, która zawiera element mówiący o tym, czy rozgałęzienie została ostatnio wykonane/podjęte (?) czy nie.
- przewidywanie jest to wskazówka, którą przyjmuje się za własciwą i pobieranie rozpoczyna się w przewidywanym kierunku. Jeżeli wskazówka okaże się błędna, element przewidywania jest odwrócony i powrotem zmagazynowany/przechowywany.
- ten prosty 1-bitowy schemat przewidywania ma niedociągnięcia w działaniu/wydajności.
2.
2-bitowy schemat przewidywanie rozgałęzienia.
Taken- wykonane/podjęte
Not-taken - nie wykonane/podjęte
Predict taken- przewidywanie wykonane/podjęte
3.
Korelacja wskaźnika/ zapowiedzi (chodzi o ten element przewidujący)
Zapoznaj się z następującym fragmentem kodu:
DSUBUI R3,R1,#2
BNEZ R3,L1 (b1)
DADD R1,R0,R0
If(aa==2) aa = 0; L1: DSUBUI R3,R2,#2
If(bb==2) bb = 0; BNEZ R3,L2 (b2)
If(aa!=bb) DADD R2,R0,R0
{ L2: DSUBU R3,R1,R2
BEQZ R3,L3 (b3)
Jeżeli oba rozgałęzienia b1 i b2 nie ostały wykonane/podjęte, wtedy b3 będzie wykonane- Korelacja wskaźnika/ zapowiedzi (2-poziomowe wskaźniki/zapowiedzi)
4.
Przykład
Weź pod uwagę następny fragment kodu:
(popatrz na slajd…)
Initial value of d - wartość początkowa d
Value of d before b2 - wartość d przed b2
Possible execution sequences -możliwe sekwencje wykonania
5.
Wynik dla 1-bitowego wskaźnika/zapowiedzi zainicjowanego do nie-wykonania / nie-podjęcia.
(patrz tabelka na slajdzie)
NT- nie wykonane
T-wykonane
Wszyskie rozgałęzienia są nieprawidłowo przewidziane, jednak widzimy, że jeżeli b1 nie jest wykonane, wtedy b2 nie będzie wykonane; wykorzystajmy tę obserwację.
6.
Wskaźnik/zapowiedź z 1-bitowymi/ (1-elementowymi) korelacjami
Prediction bit- bit wskaźnika/zapowiedzi (albo element wskaźnika/zapowiedzi)
Prediction if last branch not taken- wskaźnik/zapowiedź jeżeli ostatnie rozgałęzienie nie jest wykonane
Prediction if last branch taken -wskaźnik/zapowiedź jeżeli ostatnie rozgałęzienie jest wykonane
Meaning of the taken/not taken prediction bits - znaczenie bitów/elementów wykonanych I niewykonanych wskaźników/zapowiedzi
The action of the 1-bit predictor with 1-bit of correlation - Akcja 1-bitowego (1-elementowego) wskaźnika/ zapowiedzi z 1-elementową (1-bitową) korelacją
7.
(N,N) wskaźniki/zapowiedzi
- wskaźnik/zapowiedź z ostatniego przykładu nazywany jest wskaźnikiem (1,1) ponieważ wykorzystuje zachowanie ostatniego rozgałęzienia wybierając z pary 1-bitowych (1-elementowych) wskaźników rozgałęzienia.
- Generalnie, wskaźnik (m,n) wykorzystuje zachowanie ostatnich rozgałęzień m wybierając ze wskaźnika rozgałęzienia 2m, a każdy z nich jest wskaźnikiem n-bitowym (n-elementowym) dla pojedyńczego rozgałęzienia.
- Globalna historia najbardziej ostatnich rozgałęzień m może być zapisana w rejestrze zmian/przesunięć m- bitowych (m-elementowych), gdzie każdy bit (element) rejestruje czy rozgałęzienie zostało wykonane czy nie.
8.
Bufor wskaźnika rozgałęzienia (2,2) wykorzystuje 2-bitową (2-elementową) globalną historię.
9.
Wskaźniki rozgrywek/turnieju (??)
- Wskaźniki rozgrywek/turnieju wykorzystują wielokrotne wskaźniki, zwykle jeden jest na podstawie globalnej informacji, a drugi na podstawie lokalnej informacji, łącząc je za pomocą selektora (wybieraka)- wielopoziomowych wskaźników rozgałęzienia.
- wielopoziomowy wskaźnik rozgałęzienia wykorzystuje wiele poziomów tabel przewidywania rozgałęzienia wraz z algorytmem wyboru pośród wielokrtnych/licznych/zbiorowych wskaźników
- Wskaźniki rozgrywek/turnieju wykorzystują najczęściej 2itwy (2-elementowy) nasycony licznik na każde rozgałęzienie wybierając pośród 2 różnych wskaźników
-zdolność wyboru pomiędzy wskaźnikami opartymi wyłącznie na lokalnej informacji i tymi opartymi na pobieraniu globalnych informacji dla każdego rozgałęzienia jest bardzo istotna w typie całkowitym testu wydajności/punktu odniesienia (?)
10.
Diagram stanu przejścia dla wskaźnika rozgałęzienia rozgrywek/turnieju (?)
11.
liczba/tempo nieprawidłowego przewidywania dla 3 różnych wskaźników na SPEC89
conditional branch misprediction rate- warunkowe tempo nieprawidłowego przewidywania rozgałęzeinia
local 2-bit predictors- lokolne 2-elementowe wskaźniki
correlating predictors- skorelowane wskaźniki
tournament redictors- wskaźniki rozgrywek
12.
Instrukcja dostarczania wyokiej wydajności
przewidywania rozgałęzienia nie sa obecnie wystarczająco dobre
-musimy wiedzieć z jakiego adresu pobierać do zakończenia IF ( to znaczy, że musimy wiedzieć, czy asyet-undecoded (asyst-niekodowana) instrukcja jest rozgałęzieniem i jeżeli tak, to jaki powinien być następny PC)
- schowek pamięci przewidywania rozgałęzienia, który przechowuje przewidywane adresy dla następnej instrukcji po tym, jak rozgałęzienie jest nazwane buforem celu rozgałęzienia (schowkiem pamięci celu rozgałęzienia)
- dla klasycznej, 5 stopniowego łańcucha, dostęp do buforu przewidywania rozgałęzienia ma miejsce podczas cyklu ID, tak że na końcu ID znamy adres celowy rozgałęzienia, adres niespełniony i przewidywanie.
13.
Bufor docelowego rozgałęzienia
Number of entries In branch target bufer- liczba wejść w buforze docelowego rozgałęzienia
PC of instruction to fetch- instrukcja PC do pobrania
Look up- sprawdź, zobacz
Predicted PC- przewidywany PC
Instruction is not predicted to be brach- instrukcja nie jest przewidziana,żeby była rozgałżenieniem
Then, the instruction is brunch and predicted PC should be used as the next PC - wtedy instrukcja jest rozgałęzieniem I przewidywany PC powinien byc użyty/wykorzystany jako następny PC
14.
Kroki użycia buferu docelowego rozgałęzienia
Send PC to memory and branch-target Buffet - wyślij PC do pamięci i bufor docelowego rozgałęzienia
Is instruction a taken Branch ? - czy instrukcja jest wykonanym rozgałęzieniem?
Enter branch instruction address and next PC into
branch-target Buffet- wpisz adres instrukcji rozgałęzienia i następnego PC do buffetu docelowego rozgałęzienia
Entry found in branch-target buffer ?- czy znaleziono wejście w buferze docelowego rozgałęzienia?
Send out predicted PC - wyślij przewidywany PC
Mispredicted branch, kill fetched instruction; restart fetch at other target; delete entry from target buffer - nieprawidłowo przewidziane rozgałęzienie, zabij pobraną intrukcję; zrestartuj pobranie na innym celu; wykasuj wejście z buforu docelowego
Branch correctly Predicated; continue Execution with no stalls - rozgałęzienie przewidziane prawidłowo; kontynuuj wykonanie bez opóźnienia
15.
Kary za nieprawidłowe przewidywania
Instruction in Buffer- instrukcja w bufrze
Prediction - przewidywanie
Actual branch - faktyczne/właściwe rozgałęzienie
Penalty cycles- cykle kar
16.
Przykład
Ustal całkowitą karę rozgałęzienia dla bufora docelowego rozgałęzienia przyjmując następujące tempo/stosunek/proporcję uderzenia prawidłowego przewidywania:
ÛÜ prawdÅ‚owe przewidywanie to 90 % (instrukcja w buforze)
ÛÜ stosunek/proporcja uderzenia w buforze wynosi 90 % (przewidywane rozgaÅ‚Ä™zienia wykonane)
Załóż że 60% rozgałęzień jest wykonanych
Kara rozgałęzienia = kara, kiedy rozgałęzienie przewidywane wykonane i niewykonane (1)+ kara, kiedy rozgałęzienie jest wykonane, ale nie jest w buforze(2)
prawdopodobieństwo (1) = procent tosunku/proporcji uderzenia bufora* procent nieprawidłowy
przewidywania = 90 % * 10 % = 0.09
prawdopodobieństwo (2) = procent rozgałęzienia nie w bufrze * procent rozgałęzienia wykananego = 10 % * 60 % = 0.06
kara całkowita = (0.09 + 0.06) * 2 = 0.3
17.
Jednostki/rozdziały pobierania zintegrowanej instrukcji
ÛÜ przewidywanie zintegrowanego rozgaÅ‚Ä™zienia - wskaźnik/zapowiedź rozgaÅ‚Ä™zienia staje siÄ™ częściÄ… jednostki/rozdziaÅ‚u instrukcji pobierania i stale przewiduje rozgaÅ‚Ä™zienia
ÛÜ wstÄ™pne pobieranie instrukcji - jednostka/ rozdziaÅ‚ autonomicznie zarzÄ…dza wstÄ™pym poberaniem instrukcji, integrujÄ…c to z przewidywaniem rozgaÅ‚Ä™zienia.
ÛÜ dostÄ™p do pamiÄ™ci instrukcji i buforowania - pobieranie licznych/wielokrotnych instrukcji może wymagać dostÄ™pu do wielu schowków, użyta jednostka/rozdziaÅ‚ wstÄ™pnego pobierania stara siÄ™ ukryć koszt przekraczania bloków schowków. Również dostarcza buforowanie, istotnie dziaÅ‚ajÄ…c jak jednostka/rozdziaÅ‚ na żądanie, żeby dostarczyć instrukcje do etapu wydania/wyniku/rezultatu jaki jest potrzebny i w potrzebnej iloÅ›ci.
18.
Wskaźniki/ zapowiedzi adresu zwrotnego
- dla przewidywania niebezpośrednich skoków, potrzebne SA inne techniki ( skoki, dla których adresy, adresy docelowe zmieniają się w trakcie działania)
- większość niebezpośrednich skoków pochodzi ze zwrotów procedury (ponad 85%).
- użycie buforu dcelowego rozgałęzienia nie jest Dorym rozwiązaniem w tym przypadku
- zamiast tego, proponuje się concept małego buforu zwrotnego adresu działającego jak stos.
(przypiski:
» stos (w programowaniu, specjalny typ struktury danych, z którego poszczególne elementy usuwane są w odwrotnym porządku niż były wprowadzane) (kat.: informatyka)
» stos (w sieci, krótkie określenie dla grupy protokołów takich jak TCP/IP) (kat.: informatyka)
» stos (miejsce w pamięci służące do czasowego przechowywania wartości zmiennych) (kat.: informatyka)
- jeżeli ten bufor jest wystarczająco duży, idealnie przewidzi zwroty
19.
nieomylność/prawidłowość przewidywania dla buforu adresu zwrotnego działającego jak stos.
Misprediction rate- stosunek nieprawidłowego przewidywania
Nuber of entries In the return stack- liczna wejść w stos zwrotów
20.
Wnioski
- schematy przewidywania rozgałęzienia są ograniczone przez prawidłowość/ niemylność przewidywania i przez kary za nieprawidłowe przewidywania
-typowy schemat przewidywania osiąga nieomylnośc w zakresie 80 % do 95 %.
- kara za nieprawidłowe przewidywanie może być zmniejszona poprzez pobieranie zarówno z kierunków przewidywanych i nieprzewidywalnych, jednak pobieranie z dwóch ścieżek wymaga, aby system pamięci był 2-portowy, miał schowek z przeplotem (» pamięć z przeplotem (pamięć podzielona na wiele modułów, które mogą być wykorzystywane jednocześnie)), albo pobierać z jednej ścieżki a później z drugiej