Algorytm Tomasulo: Wykonanie Poza Porządkiem Programu i Renamowanie Rejestrów

Problem: Zależności, które Nie Istnieją W Praktyce

Zależności danych między instrukcjami mają trzy formy, i tylko jedna z nich jest prawdziwą, niewyeliminowalną zależnością danych. Zjawisko read-after-write (RAW), gdzie instrukcja potrzebuje wartości, której poprzednia instrukcja jeszcze nie wygenerowała, to prawdziwa zależność, którą należy szanować w każdym razie. Ale zjawiska write-after-write (WAW) i write-after-read (WAR) są artefaktami skończonej liczby nazw rejestrów architektonicznych powtarzanych po przeprogramowaniu, nie prawdziwymi przepływami danych. Jeśli instrukcja 1 pisze do rejestru R1, instrukcja 2 czyta z R1, a instrukcja 3 później ponownie pisała do R1 z całkowicie niespokredloną wartością, maszyna wykonująca instrukcje poza porządkiem i przyjmująca na siłę te zależności ryzyko miało by polegać na tym, że instrukcja 3 nadpisze R1 przed tym, jak instrukcja 2 odczyta pierwotną wartość, lub wyniki zostaną zapisane w niewłaściwej kolejności i zostanie on R1 z przerdzawiałą wartością. Te zależności nazywamy fałszywymi, dokładnie dlatego, że nie przekazują żadnej rzeczywistej informacji między instrukcjami, istnieją tylko dlatego, że kompilator wykorzystał wszystkie nazwy rejestrów i ponownie użył R1 do czegoś nowego. Dary procesory akceptowały te spowolnienia wynikające z tego lub wymagali inteligentnego kompilatora, który pomijał je poprzez wybór innych rejestrów. Odkrycie Tomasulo polegało na tym, że sam sprzęt mógłby eliminować te fałszywe zależności dynamicznie, podczas wykonania, bez konieczności, aby kompilator był nawet świadomy tego, dając każdemu nowemu zapisowi do rejestru nowy wewnętrzny etykietę zamiast ponownego wykorzystywania ustalonego fizycznego slotu.

Stacje Rezerwacji: Bufory do Momentu Gotowości

W sercu projektu Tomasulo znajduje się stacje rezerwacji, małe bufora powiązane z każdym jednostką funkcjonalną, taką jak dodawacze lub mnożniki, które przechowują wykazane instrukcje oraz ich wartości operandów. Jeśli wartość nie jest jeszcze dostępna, bufor przechowuje etykietę instrukcji w trakcie wykonania, która z czasem powinna ją produceć. Gdy instrukcja jest wykazana, zostaje przypisana do wolnej stacji rezerwacji odpowiedniej jednostki funkcjonalnej; jeśli oba operandy są już dostępne w pliku rejestrów lub przesłane z instrukcji niedawno wykonanej, to są one natychmiast skopiowane. W przeciwnym razie stacja rezerwacji przechowuje etykietę producenta instrukcji zamiast wartości. Kluczowe jest to, że wykazanie nie blokuje oczekiwania na operandy; instrukcja po prostu siedzi w swojej stacji rezerwacji i wykonanie może zacząć się w chwili, gdy wszystkie jej etykietowane operandy rzeczywiście dotrą, bez względu na to, co mówi oprogramowana kolejność. To dokładnie jak niezależne instrukcje są wykonywane poza oprogramowaną kolejnością: instrukcja, której operandy są już gotowe, może zacząć się wykonywać nawet podczas gdy wcześniejsza, nadal wykazana instrukcja czeka na wartość produkcji wolną. Stacje rezerwacji efektywnie rozłączają pytanie o moment pobrania i dekodowania instrukcji z tym, kiedy rzeczywiście potrzebują one wszystkiego, co potrzebne do działania, przekształcając oprogramowaną kolejność w luźną sugestię dla etapu wykonania, a nie w wymagane warunki.

Renamowanie rejestrów poprzez etykiety

Algorytm Tomasulo realizuje renamowanie rejestrów bez osobnego, jasno zdefiniowanego pliku fizycznego rejestrów jak w późniejszych projektach, takich jak MIPS R10000; zamiast tego używa prostej, ale mocnej techniki rachunkowej. Tabela stanu rejestrów śledzi dla każdego architektonicznego rejestru, który stacjonariusz rezervacji (jeśli istnieje) obecnie przechowuje instrukcję, która wygeneruje jego kolejną wartość. Gdy instrukcja zapisująca do rejestra R1 jest wysłana, tabela stanu rejestrów jest natychmiastaktualizowana, aby wskazywać na etykietę stacjonarza rezervacji tej instrukcji, co oznacza, że każda późniejsza instrukcja czytająca R1 przed zakończeniem zapisu automatycznie wybiera poprawną, najnowszą etykietę producenta zamiast starej wartości. Ta jedna technika rozwiązuje zagadnienia WAW i WAR za darmo: ponieważ każda zapis jest przypisana nowa etykieta zamiast nadpisania ustalonego lokalizacji fizycznej, późniejsze zapisy do tego samego architektonicznego rejestru stają się tylko inne etykiety, a wcześniejsze odczyty, które już zdobyły poprzednią etykietę, nie są wpływowane na to, co się stanie z tym rejestrzem dalej. W efekcie mała, ustalona liczba architektonicznie widocznych rejestrów jest dynamicznie mapowana na znacznie większą, implikacyjną przestrzeń etykietowych wartości, jedną dla każdego w trakcie instrukcji zapisującej rejestry, co dokładnie to, co dzisiaj robi renamowanie rejestrów z dużymi plikami fizycznymi. Genialność oryginalnego rozwiązania Tomasulo polega na tym, że osiągnął tę zachowawczą funkcję jako emergent property stacjonarzy rezervacji opartych na etykietach, a nie wymagając dodatkowego sprzętu renamowania.

Komunikator danych wspólne i wykonanie poza porządkiem programu

Po zakończeniu wykonywania instrukcji, jej wynik musi dotrzeć do każdego stanowiska rezervacji i wpisu statusu rejestrów czekających na niego, potencjalnie wielu konsumentów jednocześnie. Algorytm Tomasulo rozwiązuje to za pomocą komunikatora danych wspólne (CDB), który jest busiem nadawczym przesyłającym wynik zakończonego instrukcji oznaczonego jego identyfikatorem do wszystkich jednostek funkcjonalnych i pliku rejestrów w jednym cyklu. Każde stanowisko rezervacji ciągle porównuje tagi czekające na niego z tym, który obecnie pojawia się na CDB; dowolne dopasowanie powoduje natychmiastowe zapisanie wartości nadanej przez komunikator do swojej własnej pętli operandów, co może sprawić, że stanowisko rezervacji jest gotowe do wykonania w bardzo następnym cyklu. Ponieważ wyniki są nadawane w porządku rzeczywistym zakończenia instrukcji, a nie w porządku wysłanych, instrukcje zakończają się stricte poza porządkiem programu, a szybka i niezależna dodawanie może nadawać swoje wyniki przed znacznie wcześniejszym mnożeniem nawet nie zakończyło. To jest bezpośrednim przysługą całego systemu: instrukcje wykonują się i zakończają jedynie na podstawie dostępności danych, a nie porządku programu, więc operacja o długim czasie opóźnienia już nie blokuje niespokojnego pracy za jego plecami. CDB wprowadza własny ograniczenie strukturalne, ponieważ w najprostszych projektach tylko jeden wynik może być nadawany w jednym cyklu, co jest powodem, dla którego współskalowe procesory moderniczne rozszerzają idea do wielu paralelnych busów wynikowych lub sieci przekierowywania zamiast wspólnego busa.

Od IBM 360/91 do Każdego Modyfikacji Czasu Współczesnych CPU

Robert Tomasulo zaprojektował ten schemat, aby umożliwić IBM System/360 Model 91owi, który miał jednostkę liczb zmiennoprzecinkowych z mnożnikiem i dzielnikami o znacznie różniących się opóźnieniach, kontynuować operacje niezależne zamiast czekać za najwolniejszą jednostką. W ciągu około dwudziestu lat ta myśl pozostawała w granicach akademickiej ciekawości poza specjalizowanymi superkomputerami, aż do początku lat 90., kiedy stała się podstawą prawie wszystkich głównych mikroarchitektur wykonywania poza porządkiem programu: Pentium Pro Intel'a wprowadził unifikowany stacjonar rezervacji i bufor ponownego uporządkowania bezpośrednio zaprzysadniony przez podejście Tomasulo, a jego potomstwo rozszerza się do każdej kolejnej generacji procesorów Intel Core. AMD, jądro wydajne ARM'a oraz własne linię POWER IBM'a używają obecnie struktur koncepcyjnie równoważnych, zazwyczaj w parze ze osobnym bufor ponownego uporządkowania, który śledzi porządek programu, aby wyniki, nawet wyliczone poza porządkiem, były komittowane do stanu architektonicznego (zakwalifikowanych) w poprawnym porządku, co jest kluczowe dla dokładnych wyjątków i iluzji wykonania sekwencyjnego, na które zależy poprawność oprogramowania. Współczesne implementacje używają jasnych dużych fizycznych plików rejestrów oraz tablic renamowania zamiast oryginalnej metody dopasowywania etykiet przez nadanie tagu CDB, ponieważ bus wspólnotowy nadawania nie skali do dziesiątek instrukcji jednocześnie w trakcie wykonywania na współczesnych chipach. Język koncepcyjny jest bezpośredni i niepodważalny. Gdy używasz dowolnego współczesnego wysokiego wydajnościowego procesora, od telefonu komórkowego do serwera centra danych, instrukcje prawie na pewno są planowane przez sprzęt pochodziły z projektu zaprojektowanego do przyspieszenia matematyki zmiennoprzecinkowej na maszynie głównym z 1967 roku.

Często zadawane pytania

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Tomasulo's Algorithm: Out-of-Order Execution & Register Renaming i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.