Algorytm Tomasulo

Algorytm Tomasulo to algorytm sprzętowy architektury komputerowej do dynamicznego szeregowania instrukcji, który umożliwia wykonywanie poza kolejnością i umożliwia bardziej efektywne wykorzystanie wielu jednostek wykonawczych. Został opracowany przez Roberta Tomasulo w IBM w 1967 roku i został po raz pierwszy zaimplementowany w jednostce zmiennoprzecinkowej IBM System/360 Model 91 .

Główne innowacje algorytmu Tomasulo obejmują sprzętową zmianę nazw rejestrów , stacje rezerwacji dla wszystkich jednostek wykonawczych oraz wspólną szynę danych (CDB), na której obliczone wartości są transmitowane do wszystkich stacji rezerwacji, które mogą ich potrzebować. Te zmiany pozwalają na ulepszone równoległe wykonywanie instrukcji, które w przeciwnym razie utknęłyby w martwym punkcie przy użyciu tablicy wyników lub innych wcześniejszych algorytmów.

Robert Tomasulo otrzymał nagrodę Eckert-Mauchly w 1997 roku za pracę nad algorytmem.

Koncepcje wdrożeniowe

Jednostka zmiennoprzecinkowa Tomasulo

Poniżej przedstawiono koncepcje niezbędne do implementacji algorytmu Tomasulo:

Wspólna magistrala danych

Wspólna magistrala danych (CDB) łączy stacje rezerwacyjne bezpośrednio z jednostkami funkcjonalnymi. Według Tomasulo „zachowuje pierwszeństwo, jednocześnie zachęcając do współbieżności”. Ma to dwa ważne skutki:

1. Jednostki funkcjonalne mogą uzyskać dostęp do wyniku dowolnej operacji bez angażowania rejestru zmiennoprzecinkowego, umożliwiając wielu jednostkom oczekującym na wynik, aby kontynuować bez czekania na rozwiązanie rywalizacji o dostęp do portów odczytu pliku rejestru.
2. Wykrywanie zagrożeń i wykonywanie kontroli są rozproszone. Stacje rezerwacji kontrolują, kiedy instrukcja może zostać wykonana, a nie pojedyncza dedykowana jednostka zagrożenia.

Kolejność instrukcji

Instrukcje są wydawane sekwencyjnie, dzięki czemu efekty sekwencji instrukcji, takie jak wyjątki wywoływane przez te instrukcje, występują w tej samej kolejności, w jakiej wystąpiłyby w przypadku procesora na zamówienie, niezależnie od faktu, że są one wykonywane poza kolejność (tj. niesekwencyjnie).

Zarejestruj zmianę nazwy

Algorytm Tomasulo wykorzystuje zmianę nazwy rejestru , aby poprawnie wykonać wykonanie poza kolejnością. Wszystkie rejestry stacji ogólnego przeznaczenia i stacji rezerwacji zawierają wartość rzeczywistą lub wartość zastępczą. Jeśli wartość rzeczywista jest niedostępna dla rejestru docelowego na etapie wydawania, początkowo używana jest wartość zastępcza. Wartość zastępcza to znacznik wskazujący, która stacja rezerwacji wygeneruje rzeczywistą wartość. Kiedy jednostka zakończy i wyemituje wynik na CDB, symbol zastępczy zostanie zastąpiony rzeczywistą wartością.

Każda jednostka funkcjonalna posiada jedno stanowisko rezerwacyjne. Stacje rezerwacyjne przechowują informacje potrzebne do wykonania pojedynczej instrukcji, w tym operację i operandy. Jednostka funkcjonalna rozpoczyna przetwarzanie, gdy jest wolna i kiedy wszystkie operandy źródłowe potrzebne do wykonania instrukcji są rzeczywiste.

Wyjątki

Praktycznie rzecz biorąc, mogą istnieć wyjątki, dla których nie ma wystarczających informacji o statusie wyjątku, w takim przypadku procesor może zgłosić wyjątek specjalny, zwany wyjątkiem „nieprecyzyjnym”. Nieprecyzyjne wyjątki nie mogą wystąpić w implementacjach w kolejności , ponieważ stan procesora jest zmieniany tylko w kolejności programu (patrz RISC Pipeline Exceptions ).

Programy, w których występują „dokładne” wyjątki, w przypadku których można określić konkretną instrukcję, która przyjęła wyjątek, mogą zostać ponownie uruchomione lub ponownie wykonane w punkcie wyjątku. Jednak te, które doświadczają „nieprecyzyjnych” wyjątków, generalnie nie mogą ponownie uruchomić ani ponownie wykonać, ponieważ system nie może określić konkretnej instrukcji, która przyjęła wyjątek.

Cykl życia instrukcji

Trzy etapy wymienione poniżej to etapy, przez które przechodzi każda instrukcja od momentu jej wydania do momentu zakończenia jej wykonania.

Zarejestruj legendę

• Op - reprezentuje operację wykonywaną na operandach
• Qj, Qk - stacja rezerwacji, która wygeneruje odpowiedni operand źródłowy (0 oznacza, że ​​wartość jest w Vj, Vk)
• Vj, Vk - wartość operandów źródłowych
• A - używany do przechowywania informacji o adresie pamięci dla ładunku lub magazynu
• Zajęty - 1 jeśli zajęty, 0 jeśli nie zajęty
• Qi - (Only register unit) stacja rezerwacji, której wynik ma być zapisany w tym rejestrze (jeśli puste lub 0, żadne wartości nie są przeznaczone dla tego rejestru)

Etap 1: problem

Na etapie wydania wydawane są instrukcje do wykonania, jeśli wszystkie operandy i stacje rezerwacji są gotowe lub są zablokowane. Rejestry są zmieniane w tym kroku, eliminując zagrożenia WAR i WAW.

• Pobierz następną instrukcję z początku kolejki instrukcji. Jeśli operandy instrukcji znajdują się obecnie w rejestrach, to
  • Jeżeli dostępna jest pasująca jednostka funkcjonalna, należy wydać dyspozycję.
  • W przeciwnym razie, ponieważ nie ma dostępnej jednostki funkcjonalnej, wstrzymaj wykonanie instrukcji, aż zwolni się stacja lub bufor.
• W przeciwnym razie możemy założyć, że operandy nie znajdują się w rejestrach, a więc użyć wartości wirtualnych. Jednostka funkcjonalna musi obliczyć wartość rzeczywistą, aby śledzić jednostki funkcjonalne, które tworzą operand.

Pseudo kod

Stan instrukcji	Czekać, aż	Akcja lub księgowość
Wydanie	Stacja r pusta	0 0 if ( RejestrStat [ rs ]. Qi ¦ ) { RS [ r ]. Qj ← Stan rejestru [ rs ]. Qi } jeszcze { RS [ r ]. Vj ← Reg [ rs ]; RS [ r ]. Qj ← ; } if ( RejestrStat [ rt ]. Qi 0 0 ¦ ) { RS [ r ]. Qk ← Stan Rejestru [ rt ]. Qi ; } inny { RS [ r ]. Vk ← Reg. [ rt ]; RS [ r ]. Qk ← ; } RS [ r ]. zajęty ← tak ; RegisterStat [ rd ]. Qi ← R ;
Załaduj lub Zapisz	Bufor r pusty	0 0 if ( RejestrStat [ rs ]. Qi ¦ ) { RS [ r ]. Qj ← Stan rejestru [ rs ]. Qi ; } inny { RS [ r ]. Vj ← Reg [ rs ]; RS [ r ]. Qj ← ; } RS [ r ]. A ← imm ; RS [ r ]. zajęty ← tak ;
Tylko ładuj		ZarejestrujStat [ rt ]. Qi ← r ;
Tylko sklep		0 0 jeśli ( RejestrStat [ r ]. Qi ¦ ) { RS [ r ]. Qk ← Stan Rejestru [ rt ]. Qi ; } inny { RS [ r ]. Vk ← Reg. [ rt ]; RS [ r ]. Qk ← };

Przykład algorytmu Tomasulo

Etap 2: wykonaj

W fazie wykonywania wykonywane są instrukcje. Instrukcje są opóźniane na tym etapie, dopóki wszystkie ich operandy nie będą dostępne, co eliminuje zagrożenia RAW. Poprawność programu jest utrzymywana dzięki efektywnemu obliczaniu adresu, aby zapobiec zagrożeniom przez pamięć.

• Jeśli jeden lub więcej operandów nie jest jeszcze dostępnych, to: poczekaj, aż operand stanie się dostępny w CDB.
• Gdy wszystkie operandy są dostępne, to: jeśli instrukcja jest ładowaniem lub przechowywaniem
  • Oblicz efektywny adres, gdy rejestr bazowy jest dostępny, i umieść go w buforze ładowania/zapisywania
    • Jeśli instrukcja jest ładowana, to: wykonaj, gdy tylko jednostka pamięci będzie dostępna
    • W przeciwnym razie, jeśli instrukcja jest zapisem, to: poczekaj na zapisanie wartości przed wysłaniem jej do jednostki pamięci
• W przeciwnym razie instrukcja jest operacją jednostki arytmetyczno-logicznej (ALU), a następnie: wykonaj instrukcję w odpowiedniej jednostce funkcjonalnej

Pseudo kod

Stan instrukcji	Czekać, aż	Akcja lub księgowość
działanie FP	(RS[r].Qj = 0) i (RS[r].Qk = 0)	Oblicz wynik: operandy są w Vj i Vk
Załaduj/zapisz krok 1	RS[r].Qj = 0 & r jest głową kolejki magazynu danych	RS[r].A ← RS[r].Vj + RS[r].A;
Załaduj krok 2	Załaduj krok 1 zakończony	Odczyt z pamięci[RS[r].A]

Etap 3: napisz wynik

Na etapie zapisu wyniku wyniki operacji ALU są zapisywane z powrotem do rejestrów, a operacje zapisywania są zapisywane z powrotem do pamięci.

• Jeżeli instrukcja była operacją ALU
  • Jeżeli wynik jest dostępny to: zapisz go na CDB a stamtąd do rejestrów i ewentualnych stacji rezerwacyjnych oczekujących na ten wynik
• W przeciwnym razie, jeśli instrukcja była zapisem, to: zapisz dane do pamięci podczas tego kroku

Pseudo kod

Stan instrukcji	Czekać, aż	Akcja lub księgowość
Działanie lub obciążenie FP	Wykonanie kompletne w r & CDB dostępne	0 ∀ x ( if ( Stan Rejestru [ x ]. Qi = r ) { regs [ x ] ← wynik ; Stan Rejestru [ x ]. Qi = }); ∀ x ( gdyby ( RS [ x ]. Qj = r ) { RS [ x ]. Vj ← wynik ; 0 0 RS [ x ]. Qj ← ; }); ∀ x ( gdyby ( RS [ x ]. Qk = r ) { RS [ x ]. Vk ← wynik ; RS [ x ]. Qk ← ; }); RS [ r ]. zajęty ← nie ;
Sklep	Wykonanie zakończone przy r & RS[r].Qk = 0	Pamięć [ RS [ r ]. ZA ] ← RS [ r ]. Vk ; RS [ r ]. zajęty ← nie ;

Udoskonalenia algorytmu

Koncepcje stacji rezerwacji, zmiany nazw rejestrów i wspólnej magistrali danych w algorytmie Tomasulo stanowią znaczący postęp w projektowaniu komputerów o wysokiej wydajności.

Stacje rezerwacji przejmują odpowiedzialność za oczekiwanie na operandy w obecności zależności danych i innych niespójności, takich jak zmienny czas dostępu do pamięci i prędkości obwodu, uwalniając w ten sposób jednostki funkcjonalne. To ulepszenie przezwycięża długie opóźnienia zmiennoprzecinkowe i dostęp do pamięci. W szczególności algorytm jest bardziej tolerancyjny na braki w pamięci podręcznej. Dodatkowo programiści są zwolnieni z konieczności implementowania zoptymalizowanego kodu. Jest to wynikiem współpracy wspólnej magistrali danych i stacji rezerwacji w celu zachowania zależności oraz zachęcania do współbieżności.

Dzięki śledzeniu operandów instrukcji w stacjach rezerwacji i sprzętowej zmianie nazw rejestrów, algorytm minimalizuje ryzyko odczytu po zapisie (RAW) i eliminuje zagrożenia związane z architekturą komputera typu zapis po zapisie (WAW) i zapis po odczycie (WAR) . Poprawia to wydajność, zmniejszając stratę czasu, który w innym przypadku byłby potrzebny na stragany.

Równie ważnym ulepszeniem algorytmu jest to, że projekt nie ogranicza się do określonej struktury rurociągu. To ulepszenie pozwala na szersze zastosowanie algorytmu przez procesory wielu problemów. Dodatkowo, algorytm można łatwo rozszerzyć, aby umożliwić spekulacje branżowe.

Aplikacje i dziedzictwo

Algorytm Tomasulo, poza IBM, był nieużywany przez kilka lat po jego implementacji w architekturze System/360 Model 91. Jednak w latach 90. nastąpił ogromny wzrost wykorzystania z 3 powodów:

1. Gdy pamięci podręczne stały się powszechne, zdolność algorytmu Tomasulo do utrzymania współbieżności podczas nieprzewidywalnych czasów ładowania spowodowanych chybieniami w pamięci podręcznej stała się cenna w procesorach.
2. Dynamiczne planowanie i spekulacje branżowe, które umożliwia algorytm, pomogły w wydajności, ponieważ procesory wydawały coraz więcej instrukcji.
3. Rozprzestrzenianie się oprogramowania na rynek masowy oznaczało, że programiści nie chcieli kompilować dla określonej struktury potoku. Algorytm może działać z dowolną architekturą potoku, dlatego oprogramowanie wymaga kilku modyfikacji specyficznych dla architektury.

Wiele nowoczesnych procesorów implementuje schematy dynamicznego planowania, które są pochodną oryginalnego algorytmu Tomasulo, w tym popularne układy Intel x86-64 .

Zobacz też

• Bufor ponownego zamówienia (ROB)
• Równoległość na poziomie instrukcji (ILP)

Dalsza lektura

• Savard, John JG (2018) [2014]. „Wykonanie potokowe i poza kolejnością” . czworokąt . Zarchiwizowane od oryginału w dniu 03.07.2018 . Źródło 2018-07-16 .

Linki zewnętrzne

• Planowanie dynamiczne - algorytm Tomasulo w Wayback Machine (archiwum z 25 grudnia 2017 r.)
• HASE Symulacja apletu Java algorytmu Tomasulo