II dio Mikroprocesor
2.12. Preklapanje instrukcija

2.12.2. Obrada uslovnog grananja
2.12.2.4. Predviđanje adrese grananja

Za predviđanje adrese na koju će se izvršiti grananje se najčešće koriste sljedeće tehnike:

• Statičko predviđanje, u kome se ne konsultuje istorija izvršavanja do trenutka nailaska na instrukciju grananja. Ovdje spadaju sljedeće tehnike:

– Rezultat predviđanja se nikada ne uzima u obzir, tj. predviđanje se i ne vrši. Ova tehnika pretpostavlja da se grananje neće desiti i nastavlja sa dohvatanjem instrukcija po redoslijedu pojavljivanja.
– Rezultat predviđanja se uvijek uzima u obzir. Obzirom da u programima uslovni skokovi uzimaju više od 50% vremena, a u slučaju jednakog utroška sistemskih resursa predčitanja instrukcija iz obe putanje, efikasnije je dohvatati instrukcije sa ciljne adrese na koju se vrši grananje.
– Predviđanje u zavisnosti od operacionog koda. Odluke o adresi sa koje se dohvata instrukcija se mogu donijeti na osnovu operacionog koda instrukcije. Pretpostavlja se da se grananje vrši za neke kodove instrukcija, a za druge ne. Uspješnost predviđanja ove strategije dostiže i do 75%.

• Dinamičko predviđanje, u kome rezultat predviđanja zavisi od prethodnih izvršavanja naredbi uslovnog grananja. Ovdje spadaju sljedeće tehnike:

– Korišćenje prekidača izvršen/nije izvršen. Uz svaku instrukciju uslovnog grananja se asocira jedan ili više bitova koji sadrže prethodnu istoriju instrukcije. Ovi bitovi se nazivaju prekidači izvršen/nije izvršen (eng. taken/not taken switch) jer na osnovu njihovog sadržaja procesor formira odluku o dohvatanju kada se sljedeći put javi instrukcija kojoj su pridruženi. Povezivanje između bitova i instrukcija se vrši u vrlo brzoj memoriji. Instrukcije i dodijeljeni im bitovi mogu biti u kešu, ili u posebnoj tabeli (npr. u asocijativnoj memoriji) gdje se čuva evidencija o prethodno izvršenim instrukcijama uslovnog grananja.

Ako je instrukciji dodijeljen jedan bit, na osnovu njega se može odrediti samo da li je pri posljednjem izvršavanju instrukcije bilo grananja ili ne. Mehanizam sa jednim bitom se koristi kada se grananje vrši skoro uvijek, npr. u slučaju petlji. Tada se greška u predviđanju javlja dva puta: prvi put pri ulasku u petlju i drugi put pri izlasku iz petlje.

Ako su instrukciji dodijeljena dva bita, tada se oni mogu koristiti za čuvanje kodova izvršavanja/uspješnosti predviđanja instrukcije. Jedan način odlučivanja na osnovu sadržaja dva bita se može predstaviti konačnim automatom prikazanim na slici 21. Ako je u posljednja dva izvršavanja instrukcije bila preduzeta ista akcija, predviđanje je da će se ta akcija desiti i u narednom izvršavanju. Ako je predviđanje pogrešno, ono se ne mijenja u narednom izvršavanju instrukcije. Ako je predviđanje ponovo pogrešno, tada se predviđa suprotni efekat izvršavanja. Na taj način algoritam zahtijeva dve uzastopne greške da bi se promijenila procjena o efektu izvršavanja. Posljedica ovoga je da se kod ciklusa javlja najviše jedno pogrešno predviđanje.

Slika 21: Dijagram stanja predviđanja grananja u instrukciji uslovnog skoka

– Upotreba tabele sa istorijom skokova. Kada se u prethodno opisanoj tehnici predvidi grananje, ne može se uvijek dohvatiti ciljna instrukcija jer njena adresa može da bude operand instrukcije koji može da se promijeni pri izvršavanju te instrukcije. U tom slučaju se najbolji efekti dobijaju kada se dohvatanje instrukcije inicijalizuje odmah po izračunavanju njene adrese. Da bi takvo dohvatanje bilo efikasno, koristi se mehanizam nazvan bafer sa ciljnim instrukcijama grananja (eng. branch target buffer, BTB), odnosno tabela sa istorijom skokova (eng. branch history table, BHT). BHT predstavlja malu količinu keš memorije koja se pridružuje koraku dohvatanja u vodu instrukcija. Svaki upis u tabeli se sastoji od 3 dijela: adrese tekuće instrukcije koja sadži grananje, adrese instrukcije na koju se vrši grananje i određenog broja kontrolnih bitova. Instrukcije se čuvaju u kešu i povezane su sa upisima u tabeli.

Kada se pri radu prepozna instrukcija iz BHT-a ciljna adresa se prosljeđuje logici za dohvatanje instrukcije koja zahtijeva dohvatanje ciljne instrukcije iz keša. U vrijeme dekodiranja grananja, izračunava se korektna adresa na koju se vrši grananje; izračunata adresa se koristi za ispitivanje korektnosti predviđene ciljne adrese. Ako je predviđena adresa korektna, ciljna instrukcija je već dohvaćena i njeno dekodiranje se vrši u narednom koraku. Ako ciljna adresa nije korektna, tada se dohvata instrukcija sa korektne adrese i ažuriraju pridruženi bitovi.

Bafer za petlje    <    Index    >    Odloženo grananje