Tomasulo algoritam

Tomasulo algoritam je hardverski algoritam kojeg je 1967. razvio Robert Tomasulo u IBM. Ovaj algoritam omogućava sekvencijalne instrukcije koje bi inače bile zaustavljene zbog određenih zavisnosti. Prva implementacija je bila u jedinici pokretnog zareza u sistemu IBM Sistem/360 – Model 91.

Ovaj algoritam se razlikuje od scoreboarding-a zato što koristi preimenovanje registara. Tamo gde scoreboarding rešava opasnosti pisanja nakon pisanja, čitanja nakon pisanja i pisanja nakon čitanja stopiranjem, preimenovanje registara omogućava kontinuirano izdavanje instrukcija. Tomasulo algoritam takođe koristi zajednički bus podataka na kom su izračunate vrednosti prebačene svim stanicama rezervacije gde su potrebne. Ovo omogućava bolje paralelno izvršavanje instrukcija koje bi inače bile zaustavljene prilikom korišćenja scoreboarding-a.

Robert Tomasulo je dobio Ekert-Mučli nagradu 1997. za ovaj algoritam.

Koncepti implementacije

Sledeći koncepti su obavezni za implementaciju Tomasulo algoritma:

• Instrukcije se izdaju sekvencijalno tako da efekti sekvence instrukcija kao što su izuzeci podugnuti od strane ovih instrukcija se dešavaju u istom redu kao što bi i u normalnom procesoru, bez obzira na to što se izvršavaju vanredno.
• Svi obični i registri rezervacije stanice drže ili realnu ili virtuelnu vrednost. Ako re jealna vrednost nedostupna destinacijskom registru tokom faze izdavanja, virtuelna vrednost je koristi u početku. Funkcionalna jedinica koja računa realne vrednosti je postavljena za virtuelnu vrednost. Vrednosti virtuelnog registra su konvertovani u realne vrednosti čim funkcionalna jedinica završi svoje računanje.
• Funkcionalne jedinice koriste rezervacione stanice sa više slotova. Svaki slot sadrži informaciju koja je potrebna za izvršavanje jedne instrukcije, uključujući operaciju i operande. Funkcionalna jedinica počinje sa obradom kada je slobodna i kada su svi izvorni operandi potrebni za insturkciju realni.

Životni ciklus instrukcije

Slede faze kroz koje mora da prođe svaka instrukcija od vremena kad je izdata do završetka.

Faza 1: izdavanje

U ovoj fazi, instrukcije se izdaju za izvršavanje ako su svi operanci i rezervacione stanice spremne ili ako su zaustavljene. Registri su preimenovani u ovom koraku, eliminišući WAR i WAW opasnosti.

• Vrati sledeću instrukciju iz početka instrukcionog reda. Ako su operandi instrukcije trenutno u registrima, onda
  • Ako je odgovarajuća funkcionalna jedinica dostupna, izdaj instrukciju.
  • U suprotnom slučaju, zaustavi instrukciju dok stanica ili bafer ne budu slobodni.
• U suprotnom slučaju, možemo pretpostaviti da operandi nisu u registrima, zato koristimo virtuelne vrenosti. Funkcionalna jedinica mora izračunati realnu vrenost, kako bi čuvala funkcionalne jedinice koje će napravraviti operand.

Faza 2: izvršavanje

U ovoj fazi operandi instrukcije se iznose. Instrukcije se odlažu u ovom koraku dok svi njihovi operandi ne postanu dostupni, što eliminiše RAW opasnost. Tačnost programa je održana kroz efektivnu kalkulaciju adrese da bi se sprečile opasnosti kroz memoriju.

• Ako jedan ili više operanada nije dostupan sačekaj da operand postane dostupan.
• Kada su svi operandi dostupni, onda ako je instrukcije čitanje ili pisanje
  • izračunaj efektivnu adresu kada je bazni registar dostupan, i postavi ga u bafer za čuvanje i vađenje
    • Ako je instukcija uvezena, izvrši je čim memorijska jedinica postane dostupna
    • Ako nije, sačekaj da vrednost bude postavljena pre nego što je pošalješ u memorijsku jedinicu
• U suprotnom slučaju, instrukcija je ALU operacija i izvrši je na odgovarajućoj funkcionalnoj jedinici.

Faza 3: ispisivanje rezultata

U ovoj fazi, rezultati ALU operacija se ispisuju nazad u registre i operacije čuvanja se ispisuju nazad u memoriju.

• Ako je instrukcija bila ALU operacija
  • Ako je rezultat dostupan, napiši ga u CDB i odatle u registre i bilo koju rezervacionu stanicu koja čeka ovaj rezultat.
• U suprotnom slučaju, piši podatke u memoriju.

Literatura

• An Efficient Algorithm for Exploiting Multiple Arithmetic Units Arhivirano na sajtu Wayback Machine (19. jul 2013), IBM Journal of Research and Development, 11(1):25-33, January 1967.
• WebHASE: Tomasulo's Algorithm: HASE Java applet simulation of the Tomasulo's Algorithm Arhivirano na sajtu Wayback Machine (11. septembar 2013), Institute for Computing Systems Architecture, Edinburgh University.
• TOMASULO'S ALGORITHM FOR DYNAMIC SCHEDULING
• Computer Architecture: A Quantitative Approach, John L. Hennessy & David A. Patterson

Spoljašnje veze

• Dynamic Scheduling - Tomasulo's Algorithm Arhivirano na sajtu Wayback Machine (10. mart 2014)
• Web based Java demo of Tomasulo's algorithm