Branch Predictor: gshare & 2-Bit Saturating Counters

Dlaczego Przewidywanie Gałęzi Istnieje

Procesory z rurkami (Pipelined CPUs) dzielą wykonanie instrukcji na etapy, takie jak pobieranie, dekodowanie, wykonywanie i zapisywanie, tak aby wiele instrukcji było w locie jednocześnie, każda na innym etapie. To jest nakładanie się, które pozwala chipowi wydawać instrukcję prawie co cykl zamiast czekać, aż jedna z nich zostanie całkowicie zakończona przed rozpoczęciem następnej. Problem polega na tym, że gałęzie warunkowe nie ujawniają swojego wyniku do stosunkowo późnego etapu w rurce, często na etapie wykonywania, podczas gdy etap pobierania musi wiedzieć natychmiast, która instrukcja powinna być pobrana następną. Bez żadnej przewidywalności rura musiałaby całkowicie zawiesić się w każdym przypadku gałęzi do momentu rozwiązania warunku, co na rurze 15-20 etapowej mogłoby zmarnować dużą część całkowitego czasu wykonania, ponieważ gałęzie występują mniej więcej co pięć do siedmiu instrukcji w typowym kodzie. Przewidywanie gałęzi przekształca to zawieszenie w zakład: zgadnij kierunek, kontynuuj pobieranie i wykonywanie spekulatywnie i zapłacisz karę tylko wtedy, gdy się pomylisz. Ponieważ większość gałędzi jest wysoce obciążona, krawędzie pętli są zawsze brana, a wiele warunków if preferuje jeden wynik konsekwentnie, dobrze zaprojektowany przewidywacz może być prawidłowy ponad 90% czasu na rzeczywistych obciążeniach, przekształcając to, co byłoby poważnym wąskim gardłem, w drobny problem. Ta pojedyncza idea, bardziej niż prawie jakakolwiek inna technika mikroarchitektoniczna, jest odpowiedzialna za procesory wieligigahertzowe, głęboko rurkowe i o wysokiej wydajności instrukcji (IPC), których używamy dzisiaj.

The 2-Bit Saturating Counter

The simplest useful predictor state is a single bit per branch: taken or not-taken, updated to match the last outcome. But a single bit flips its prediction after just one anomaly, which hurts loops that are taken every iteration except the last one, since the final exit mispredicts and then the very next entry into the loop also mispredicts because the bit flipped. The fix, proposed in early predictor research and still used as a building block today, is the 2-bit saturating counter, a small state machine with four states typically labeled strongly-not-taken, weakly-not-taken, weakly-taken, and strongly-taken. Each correct taken prediction pushes the counter toward strongly-taken, and each correct not-taken prediction pushes it toward strongly-not-taken, but the counter saturates at the extremes rather than wrapping around. Crucially, a single mispredicting outcome only moves the counter one step, from strongly-taken to weakly-taken for instance, rather than flipping the prediction outright. This means a loop that is taken 99 times and not-taken once will only mispredict on that one anomalous iteration, then immediately return to predicting taken correctly, rather than mispredicting twice as a naive 1-bit scheme would. In the simulation, watch the counter value climb and fall as the loop executes, and notice how it takes two consecutive wrong outcomes in the same new direction before the prediction itself actually changes.

Od prostych liczników do gshare

Tabela 2-bitowych liczników, indeksowana wyłącznie adresem gałęzi, zwana predyktorem bimodalnym, działa dobrze dla gałęzi, których zachowanie jest w przybliżeniu stałe, ale nie może uchwycić korelacji między gałęziami. Wiele rzeczywistych gałęzi zależy od kontekstu: wynik instrukcji if może zależeć od tego, czy poprzednia, inna gałąź została podjęta kilka instrukcji wcześniej. Predyktor gshare, wprowadzony przez Scotta McFarlinga w 1993 roku, przechwytuje dokładnie tę korelację tanio. Utrzymuje globalny rejestr historii, przesuwający się wzór bitowy rejestrujący, czy każda z ostatnich N gałęzi gdziekolwiek w programie została podjęta lub nie, i łączy ten stan z własnym adresem programu gałęzi za pomocą operacji XOR, aby wygenerować indeks do tabeli liczników. Ponieważ indeks teraz zależy zarówno od tożsamości gałęzi, jak i niedawnego globalnego wzorca wyników gałęzi, gshare może rozróżnić tę samą gałąź pojawiającą się w różnych kontekstach behawioralnych, skutecznie dając jej znacznie większą, bardziej wyspecjalizowaną zbiór liczników bez konieczności posiadania osobnej tabeli dla każdej gałęzi. XOR haszowanie również pomaga rozpraszać różne gałęzie na całym stole, aby zmniejszyć destrukcyjne aliasing, gdzie dwie niezwiązane gałęzie kolidują w tej samej liczniku i niszczą prognozy innych. Ten globalny-history podejście było dużym skokiem ponad czysto schematy gałęziowe i bezpośrednio wpłynęło na predyktory turniejowe i TAGE używane w dzisiejszych wysokowydajnych procesorach.

Koszt Nieprawidłowego Rozpoznania

Nieprawidłowe rozpoznanie nie jest darmowe, a jego koszt rośnie wprost z głębokości i szerokości potoku. Kiedy gałąź ostatecznie rozwiązuje się w fazie wykonywania i różni się od wcześniejszego przewidywania, wszystkie instrukcje pobrane i częściowo wykonane błędną ścieżką muszą zostać zmiażdżone, ich efekty odrzucone przed możliwością modyfikacji stanu architektonicznego, a przód musi zacząć ponownie pobierać z prawidłowego adresu docelowego. Opóźnienie przed rozpoczęciem przepływu użytecznych instrukcji przez potok nazywane jest karą za nieprawidłowe rozpoznanie i na nowoczesnych wielordzeniowych rdzeniach często wynosi od 10 do 20 cykli, czasami więcej w przypadku bardzo głębokich potoków. Jeśli gałąź myli przewidywanie nawet 5% czasu i występuje co sześć instrukcji, średni koszt cykli na instrukcję z powodu nieprawidłowych rozpoznania może dorównać kosztowi opóźnień pamięci. Dlatego projektanci układów scalonych inwestują ogromne budżety tranzystorów, często więcej obszaru krzemowego niż jednostki arytmetyczne, w coraz bardziej zaawansowane przewidywania: przewidywania oparte na perceptronach, TAGE z wieloma długościami historii i przewidywania pętli, które wykrywają stałe liczby iteracji bezpośrednio. Symulacja wizualizuje tę karę wyraźnie, pokazując, jak potokowe etapy są opróżniane i uzupełniane po błędnym zgadywaniu, dzięki czemu abstrakcyjna liczba cykli staje się widocznym zatorami, które można obserwować.

Dlaczego oprogramowanie odczuwa różnicę

Predykcja rozgałęzienia jest niewidoczna w sensie, że nigdy nie zmienia poprawnego działania programu, tylko jego prędkość, ale ten efekt prędkości jest wystarczająco duży, aby ukształtować sposób pisania kodu świadomego wydajności. Sortowanie już posortowanej tablicy jest słynnie szybsze niż sortowanie losowej tablicy częściowo dlatego, że operacje porównawcze rozgałęzienia stają się bardzo przewidywalne po uporządkowaniu danych. Zastąpienie nieprzewidywalnego rozgałęzienia kodem bez rozgałęzień, używając arytmetyki bitowej lub instrukcji conditional-move do obliczenia obu wyników i wyboru między nimi, może być prawdziwą techniką optymalizacji właśnie dlatego, że eliminuje całkowicie zablokowania potoku. Kompilatory również wykorzystują profilowane optymalizacje, aby ułożyć kod tak, aby częsta ścieżka rozgałęzienia przechodziła prosto przez pamięć w sobie, co dobrze współgra z przewidywaniem, upraszczając wzorzec pobierania. Interpreterzy i maszyny wirtualne cierpią szczególnie źle na błędy przewidywania rozgałęzień w swoich pętlach dystrybucji, ponieważ centralny instrukcja skoku w interpreterze bajtów jest zasadniczo gigantycznym, trudnym do przewidzenia pośrednim rozgałęzieniem, co jest jednym z powodów istnienia technik takich jak kompilacja w czasie wykonywania i dystrybucja wielowątkowa. Nawet silniki zapytań baz danych i kodeki wideo są dostrajane z uwzględnieniem przewidywalności rozgałęzień. Kiedy można zobaczyć, jak to pokazuje symulacja, że błąd przewidywania odrzuca rzeczywiste zakończoną pracę i zatrzymuje cały potok na ponad kilkadziesiąt cykli, powtarzająca się rada o pisaniu przewidywalnych rozgałęzień przestaje być legendą i staje się bezpośrednią, mechaniczną konsekwencją tego, jak sprzęt faktycznie wykonuje Twój kod.

Często zadawane pytania

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Branch Predictor: gshare & 2-Bit Saturating Counters i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.