Tłumaczenie slajdów z wykładu

Michał Kucharski

Architektura Systemów Komputerowych

2011

Wykład 9

Schemat Tomasulo

-Algorytm bazujący na reservation station

-Reservation station pobiera i buforuje argument dopóki jest dostępny, eliminując potrzebę pobrania argumentu z rejestru

-Użycie resertavion station powoduje dwie ważne cechy:

1. Kontrola wykrycia i wykonania hazardu jest rozdzielona:

Informacja trzymana w reservation station w każdej funkcjonalnej jednostce decyduje kiedy instrukcja może rozpocząć wykonanie w danej jednostce

2. Wynik jest kierowany bezpośrednio do jednostki funkcjonalnej z reservation stations gdzie są buforowane (omijanie?)

The algorithm based on the idea of reservation station

¾The reservation station fetches and buffers an operand

as soon as it is available, eliminating the need to get the

operand from a register.

ľThe use of reservation station leads to two important

properties:

- First, hazard detection and execution control are distributed -

the information held in the reservation station at each

functional unit determine when an instruction can begin

execution at that unit,

- Second, results are passed directly to functional units from the

reservation stations where they are buffered (bypassing)

Podstawowa struktura jednostki zmiennoprzecinkowej MIPS

Trzy etapy wykonania instrukcji

Issue (emisja/wyjście/zagadnienie) - pobiera instrukcje z „głowy” (head) instrukcji kolejki FIFO,

Jeśli łączenie reservation station jest puste, wydaje instrukcje na miejsce z wartością argumentu, elimiminując WAW i WAW.

Execute(wykonanie)- Jeśli jeden lub więcej operandów nie jest (już/jeszcze) dostępny, monitoruje wspólne dane szyny, czekając aż zostanie wyliczony. Kiedy argument staje się dostępny, jest umieszczany w odpowiadającym reservation station.

Kiedy wszystkie argumenty są dostępne , operacja może zostać zrealizowana (RAW hazard pominięty).

Drukowanie wyniku- kiedy wynik jest dostępny, drukowany jest na CDB (wspólna szyna danych- Common Data Bus) i stamtąd do rejestrów i wszystkich pozostałych reservation station czekających na nie.

Store także drukuje dane do pamięci. Kiedy adres i wartość są dostępne, wysyłane są do jednostki pamięci i Store jest uzupełniony.

Issue - get instruction from the head of the instruction

queue (FIFO), if there is a matching reservation station that

is empty, issue the instruction to the station with the

operand value, if they are currently in the register (this

step renames registers, eliminating WAW and WAW).

ľ Execute - If one or more of the operands is not yet

available, monitor the common data bus while waiting for it

to be computed. When an operand becomes available, it is

placed into the corresponding reservation station. When

all operands are available, the operation is can be

executed (RAW hazard avoided).

ľ Write result - when the result is available, write it on the

CDB (Common Data Bus) and from there into the registers

and into any reservation station waiting for this result.

Stores also write data to memory. When both the address

and data value are available, they sent to the memory unit

and the store is completes.

Dane przechowywane w reservation station

-Op- operacja wykonywana na źródle argumentów S1 i S2

-Qj,Qk- wartość zero wskazuje, że źródło argumentu jest już gotowe w Vj lub Vk, lub jest niekonieczne

-Vj,Vk- wartość źródła argumentów, tylko jedno z pól V lub Q jest właściwy dla każdego argumentu, dla LOADS, pole Vk jest używane do przechowywania domiaru (nadmiaru? =offset)

-A- używane do przechowywania informacji dla adresu pamięci obliczeniowej (memory address calculation) (load i store), na wstępie środkowe pole jest przechowywane, po adresie obliczeniowym, adres efektywny

- Busy- wskazuje, że reservation station i jego towarzyszące jednoski funkcjonalne są zajęte;

Numer reservation station zawierającej operacje, których wynik powinien być przechowywany w rejestrach jest zapisany w rejestrze w polu Qi

Op - the operation to perform on source operands S1 and S2,

Qj, Qk - a value of zero indicates that the source operand is

already available in Vj or Vk, or is unnecessary,

Vj,Vk - the value of source operands, only one of the V field or

the Q field is valid for each operand, for loads, the Vk field is used

to hold the offset field,

¾ A - used to hold information for the memory address calculation

(load and store), initially, the intermediate field is stored, after

address calculation, the effective address,

¾ Busy - indicates that this reservation station and its

accompanying functional unit is occupied,

¾ The number of reservation station that contains the operation

whose result should be stored in the register is save in register Qi

field,

Jak to działa?

Rozważmy następujący przykład:

Załóżmy następujący czas oczekiwania: load - 1, add- 2, mult- 10, div- 40 cykli zegara

Stan wykonania podczas, gdy pierwszy load jest już wykonany

Stan reservation stations

Zalety schematu Tomasulo

- Logiczny podział wykrycia hazardu- jeśli wiele instrukcji czeka na pojedynczy wynik i każda instrukcja ma już swój argument, wtedy instrukcja może być zwolniona symultanicznie poprzez broadcast na CDB

- Eliminacja wstrzymań dla WAW i WAW hazardów poprzez zmianę nazw rejestrów używając reservation station i poprzez proces przechowywania (store) argumentów w reservation station tak długo jak są dostępne

The distribution of the hazard detection logic - if

multiple instructions are waiting on a single

result, and each instruction already has its other

operand, then the instruction can be released

simultaneously by the broadcast on the CDB

(Common Data Bus).

• The elimination of stalls for WAW and WAR

hazards by renaming registers using reservation

station, and by the process of storing operands

into the reservation station as soon as they are

available

Status wykonania kiedy multiple jest gotowy do drukowania wyniku

Stan reservation stations

Przykład oparty na pętli

Rozważmy następujący przykład:

Załóżmy, że przewidujemy, że skoki są wykonane, więc użycie reservation station pozwoli wielokrotne wykonanie poza pętlą aby wykonać się od razu

Let's assume that we predict that branches are taken, then

using reservation station will allow multiple execution of

above loop to proceed at once (?)

Wszystkie instrukcje następujących po sobie dwóch iteracji są wykonane

All instructions of two successive iterations are issued

Dwie aktywne iteracje z pętli z nieukończoną instrukcją

---