Upravljački hazardi predstavljaju situacije koje se javljaju u pipeline procesorima prilikom izvršavanja instrukcija uslovnog skoka, kada treba zaustaviti pipeline određen broj signala takta dok se ne odluči da li će biti skok ili ne i time se dobije vrednost PC-ja sa koje treba očitati sledeću instrukciju. Broj perioda signala takta koji se mora sačekati da bi se utvrdila nova vrednost PC-ja se naziva branch delay.

1. Korektno izvršavanje instrukcija zaustavljanjem pipeline-a

U slučaju usvojenog procesora pipeline organizacije tek kada branch instrukcija stigne u stepen MEM se zna da li će biti skoka ili ne i koju vrednost signalom takta na kraju faze MEM treba upisati u registar PC. To je ili sračunata adresa instrukcije na koju se skače, koja se nalazi u registru EX/MEM.ALUOUT, ili adresa prve sledeće instrukcije iza instrukcije skoka, koja se nalazi u registru EX/MEM.NPC. Selekcija jedne od ove dve vrednosti se vrši signalom EX/MEM.cond. U opštem slučaju za svaku branch instrukciju treba sačekati njeno kompletiranje faze MEM, pa tek onda krenuti sa ubacivanjem novih instrukcija u stepen pipeline-a. To znači zaustavljanje pipeline-a za tri takta. Zbog toga kada branch instrukcija stigne u stepen MEM, u stepenima EX, ID i IF nema instrukcija. Signalom takta na kraju faze MEM branch instrukcije u registar PC se upisuje korektna adresa instrukcije sa kojom treba produžiti izvršavanje instrukcija posle branch instrukcije, pa se tek tada u stepen IF pipeline ubacuje nova instrukcija. Slika IV-1 prikazuje zaustavljanje pipeline-a za tri signala takta zbog upravljačkog hazarda.

U zavisnosti od toga da li se kao rezultat izvršavanja branch instrukcije u registar PC upisuje adresa instrukcije na koju se skače ili adresa prve sledeće instrukcije posle branch instrukcije, kaže se da je ili branch taken (skok napravljen) ili branch not taken (skok nije napravljen), respektivno.

Međutim ono što se stvarno dešava u pipeline-u izgleda nešto malo drugačije i dato je na slikama IV-2 i IV-3 za slučajeve kada je branch taken i branch not taken, respektivno. Za posmatrani procesor pipeline organizacije instrukcija iza branch instrukcije se očitava jer se za i-tu instrukciju otkriva da je branch tek kada dođe u stepen ID. Tada se očitana instrukcija zaustavlja dok se u stepenu MEM za instrukciju branch ne odluči da li je branch taken ili branch not taken. Ako je branch taken, očitana instrukcija u stepenu IF se ignoriše, jer je očitana sa pogrešne adrese, pa se ponovo očitava instrukcija sa adrese skoka (slika IV-2). Ako je branch not taken nema potrebe ponovo očitavati instrukciju jer je dobra instrukcija u stepenu IF, pa ona može da ide u stepen ID (slika IV-3). Kao rezultat toga u usvojenom procesoru pipeline organizacije kod branch instrukcija se gube ili tri takta, ako je branch taken, ili dva takta, ako je branch not taken.

instr. i (branch)	IF	ID	EX	MEM	WB
instr. i +  1 ili instr. sa adr. skoka		stall	stall	stall	IF	ID	EX	MEM	WB
instr. i +  2 ili instr. sa adr. skoka +  1			stall	stall	stall	IF	ID	EX	MEM	WB
instr. i +  3 ili instr. sa adr. skoka +  2				stall	stall	stall	IF	ID	EX	MEM
instr. i +  4 ili instr. sa adr. skoka +  3					stall	stall	stall	IF	ID	EX
instr. i +  5 ili instr. sa adr. skoka +  4						stall	stall	stall	IF	ID
instr. i +  6 ili instr. sa adr. skoka +  5							stall	stall	stall	IF

Slika IV-1 Situacija u pipeline-u kao posledica upravljačkog hazarda

instr. i (branch)	IF	ID	EX	MEM	WB
instr. sa adr. skoka		IF	stall	stall	IF	ID	EX	MEM	WB
instr. sa adr. skoka +  1			stall	stall	stall	IF	ID	EX	MEM	WB
instr. sa adr. skoka +  2				stall	stall	stall	IF	ID	EX	MEM
instr. sa adr. skoka +  3					stall	stall	stall	IF	ID	EX
instr. sa adr. skoka +  4						stall	stall	stall	IF	ID
instr. sa adr. skoka +  5							stall	stall	stall	IF

Slika IV-2 Situacija u pipeline-u kao posledica upravljačkog hazarda za slučaj da je branch taken

instr. i (branch)	IF	ID	EX	MEM	WB
instr. i +  1		IF	stall	stall	ID	EX	MEM	WB
instr. i +  2			stall	stall	IF	ID	EX	MEM	WB
instr. i +  3				stall	stall	IF	ID	EX	MEM	WB
instr. i +  4					stall	stall	IF	ID	EX	MEM
instr. i +  5						stall	stall	IF	ID	EX
instr. i +  6							stall	stall	IF	ID

Slika IV-3 Situacija u pipeline-u kao posledica upravljačkog hazarda za slučaj da je branch
not taken

2. Izbor stepena u pipeline-u u kome se realizuje skok

Gubitak tri ili dva takta za svaki branch taken značajno utiče na usporavanje pipeline-a. Broj izgubljenih taktova u ovakvim situacijama se može smanjiti ako bi se utvrđivanje da li je za branch instrukciju branch taken ili branch not taken realizovalo u nekom od ranijih stepeni pipeline-a i ukoliko bi se sračunavanje adrese instrukcije na koju se skače, takođe, realizovalo u nekom od ranijih stepeni pipeline-a. U opštem slučaju poboljšanja su veća ukoliko je to urađeno što je moguće ranije u pipeline-u.

Utvrđivanje da li je za branch instrukciju branch taken ili branch not taken se realizuje na osnovu provere u jedinici Zero? stepena EX da li je sadržaj specificiranog registra nula ili ne. To može najranije da se realizuje u stepenu ID u kome se prvi put u registru IF/ID.IR pojavljuje očitana instrukcija i utvrđuje se da je reč o branch instrukciji. Pored toga u stepenu ID se iz registarskog fajla Registers čita registar koji koristi jedinica Zero?. Stoga bi ušteda jednog takta kod branch instrukcija bila postignuta ukoliko bi se jedinica Zero? prebacila iz stepena EX u stepen ID. Zajedno sa ovim u stepenu ID treba utvrditi adresu skoka. Ona se može utvrditi u stepenu ID u kome je pomeraj potreban za sračunavanje adrese skoka raspoloživ na izlazu jedinice Sign extend. Sračunavanje adrese skoka zahteva dodatni sabirač u stepenu ID, zbog toga što se jedinica ALU, koja je između ostalog bila korišćena za sračunavanje adrese skoka, nalazi u stepenu EX. Zbog ovoga pipeline organizaciju procesora sa slike 3-4 treba modifikovati na opisani način što dovodi do pipeline organizacije procesora kao što je dato na slici 3-22.

U pipeline organizaciji procesora sa slike 3-22 je u odnosu na pipeline organizaciju procesora sa slike 3-4 urađena još jedna stvar koja donosi uštedu za još jedan takt pri skokovima. U procesoru sa slike 3-4 izlazi jedinica Zero? i ALU se, najpre, na takt upisuju u pipeline registar EX/MEM, čime se branch instrukcija prebacuje u stepen MEM, pa se tek na sledeći takt vrši upis odgovarajuće vrednosti iz stepena MEM u registar PC. Da je to isto urađeno i za procesor sa slike 3-22, izlazi jedinica Zero? i Add iz stepena ID bi se, najpre, na takt upisivali u pipeline registar ID/EX, čime bi se branch instrukcija prebacila u stepen EX, pa bi se tek na sledeći takt izvršio upis odgovarajuće vrednosti iz stepena EX u registar PC. Time bi se postigla ušteda jednog takta. Umesto toga u procesoru sa slike 3-22 izlazi jedinica Zero? i Add iz stepena ID u kome se nalazi branch instrukcija se vode direktno u stepen IF, pa se odmah na prvi takt vrši upis odgovarajuće vrednosti u registar PC. Time se postiže ušteda još jednog takta. Saglasno tome sliku 3-5 sa operacijama koje se realizuju za pojedine stepene pipeline-a treba modifikovati u delovima koji se odnose na instrukcije skoka, što dovodi do slike IV-4.

Treba zapaziti da će jedinica Zero? u svim instrukcijama, sem u branch instrukciji, na svom izlazu davati vrednost nula. Time se na takt u registar PC upiše vrednost registra PC uvećana za 4, čime se obezbeđuje sekvencijalno očitavanje instrukcija. Isto važi i za branch instrukciju ako je na izlazu jedinice Zero? nula. Treba napomenuti da se tada, s obzirom da je to slučaj branch not taken, na isti signal takta iz stepena IF u stepen ID prebacuje korektno očitana instrukcija i da nema zaustavljanja pipeline-a. Ukoliko za branch instrukciju u stepenu ID jedinica Zero? da na izlazu vrednost jedan, na takt u registar PC se upisuje adresa instrukcije na koju se skače. S obzirom da je to slučaj branch taken, u stepenu ID se nalazi očitana nekorektna instrukcija, pa se na isti takt u stepen ID ubacuje instrukcija bez dejstva. Efekat ovoga je zaustavljanje pipeline-a za jedan takt.

U modifikovanoj pipeline organizaciji procesora sa slike 3-22, skok se realizuje u fazi ID, tako da branch instrukcija ne koristi stepene EX, MEM i WB. Za dati procesor pri branch instrukcijama gubi se jedan takt ako je branch taken, a nema gubitka taktova ako je branch not taken.

 



Slika 3.22 Zastoji zbog hazarda skoka mogu se smanjiti premeštanjem instrukcija izračunavanja uslova i adrese skoka u ID fazu pipeline-a

 Rešenje da se skok realizuje u stepenu ID pipeline-a na način prikazan na slici 3-4 umesto u stepenu MEM na način prikazan na slici 3-22 ima i dobre i loše strane. Dobre strane ovog rešenja su prikazane u prethodnom tekstu i svode se na redukovanje broja taktova za koliko treba pri instrukciji skoka zaustaviti pipeline sa tri ili dva takta na jedan ili nula taktova.

Ovim se redukuju upravljački hazardi i smanjuje broj taktova za koje zbog njih treba zastaviti pipeline ali se javljaju novi hazardi podataka. Ima situacija kada je jedino rešenje za eliminaciju novonastalih hazarda podataka zaustavljanje pipeline-a. Dve situacije koje mogu da izazovu hazarde podataka u zbog toga zaustavljanje pipeline-a date su u daljem tekstu.

Prva situacija se javlja pri izvršavanju sledeće sekvence instrukcija:

add R1, R2, R3

beqz R1, 50

U slučaju pipeline organizacije procesora sa slike 3-4 situacija u pipeline-u je prikazana na slici III-11. Rezultat instrukcije add koji treba da se upiše u registar R1 je potreban instrukciji beqz. Prosleđivanjem rezultata jedinice ALU iz stepena MEM na ulaz jedinice Zero? izbegnuto je zaustavljanje pipeline-a.

U slučaju modifikovane pipeline organizacije procesora sa slike 3-22, situacija je prikazana na slici IV-5. Instrukcija beqz koja se nalazi u stepenu ID pipeline-a ne može da se kompletira u taktu 3, već mora da se zaustavi pipeline jedan takt. Ova instrukcija se tek u taktu 4 prosleđivanjem rezultata jedinice ALU iz registra EX/MEM.ALUOUT na ulaz jedinice Zero? može kompletirati.

Stepen	instrukcija
IF	IF/ID.IR ¬ Mem[PC]; IF/ID.NPC, PC ¬ (if (((IF/ID.IR0…5 eql beql) and (Regs(IF/ID.IR6…10 eql 0)) or ((IF/ID.IR0…5 eql bneq) and (Regs(IF/ID.IR6…10 neq 0))) then {NPC + ((IF/ID.IR16)16 ## IF/ID.IR16…31)} else {PC + 4});
ID	ID/EX.A ¬ Regs[IF/ID.IR6…10]; ID/EX.B ¬ Regs[IF/ID.IR11…15]; ID/EX.IR ¬ IF/ID.IR; ID/EX.Imm ¬ (IF/ID.IR16)16 ## IF/ID.IR16…31;
EX	ALU instrukcije EX/MEM.IR ¬ ID/EX.IR; EX/MEM.ALUOUT ¬ ID/EX.A func ID/EX.B; ili EX/MEM.ALUOUT ¬ ID/EX.A func ID/EX.Imm;
	load/store instrukcije EX/MEM.IR ¬ ID/EX.IR; EX/MEM.ALUOUT ¬ ID/EX.A + ID/EX.Imm; EX/MEM.B ¬ ID/EX.B;
MEM	ALU instrukcije MEM/WB.IR ¬ EX/MEM.IR; MEM/WB.ALUOUT ¬ EX/MEM.ALUOUT;
	load/store instrukcije MEM/WB.IR ¬ EX/MEM.IR; MEM/WB.LMD ¬ Mem[EX/MEM.ALUOUT] ili Mem[EX/MEM.ALUOUT] ¬ EX/MEM.B;
WB	ALU instrukcije Regs[MEM/WB.IR16…20] ¬ MEM/WB.ALUOUT; ili Regs[MEM/WB.IR11…15] ¬ MEM/WB.ALUOUT;
	store instrukcija Regs[MEM/WB.IR11…15] ¬ MEM/WB.LMD;

Slika IV-4. Operacije koje se izvršavaju u stepenima pipeline-a modifikovanog procesora



Slika IV-5. Situacija u pipeline-u pri korišćenju hardvera za prosleđivanje rezultata jedinice ALU na ulaz jedinice Zero?

Druga još gora situacija se javlja pri izvršavanju sledeće sekvence instrukcija:

lw R1, 0(R2)

beqz R1, 50

U slučaju pipeline organizacije procesora sa slike 3-4 situacija u pipeline-u je prikazana na slici III-12. Rezultat izvršavanja instrukcije lw koji treba da se upiše u registar R1 je potreban instrukciji beqz. Uz prosleđivanje rezultata jedinice Data memory iz stepena WB na ulaz jedinice Zero? instrukcija beqz je zaustavljena u pipeline-u samo jedan takt.

U slučaju modifikovane pipeline organizacije procesora sa slike 3-22, situacija u pipeline-u je prikazana na slici IV-6. Instrukcija beqz koja se nalazi u stepenu ID pipeline-a ne može da se kompletira ne samo u taktu 3, već ni u taktu 4. Ova instrukcija se tek u taktu 5 prosleđivanjem rezultata jedinice Data memory iz registra MEM/WB.LMD na ulaz jedinice Zero može kompletirati.



Slika IV-6. Situacija u pipeline-u pri korišćenju hardvera za prosleđivanje rezultata jedinice Data memory na ulaz jedinice Zero?

Iz ovoga se vidi da ukoliko se odluka o skoku donosi u nekom od kasnijih stepeni pipeline-a povećavaju se negativni efekti upravljačkog hazarda. Ukoliko se odluka o skoku donosi u nekom od ranijih stepeni pipeline-a javljaju se negativni efekti hazarda podataka. Pri projektovanju treba naći kompromis između ovih kontradiktornih zahteva.

3. Smanjivanje posledica zbog skokova u pipeline-u

Ima više metoda za smanjivanje posledica koje mogu da nastanu u pipeline-u zbog skokova. Tim metodama se pravi predviđanje kako će se program ponašati kod instrukcija skoka. Na osnovu toga se kao prva instrukcija posle instrukcije skoka očitava ili instrukcija sa adrese skoka ili prva sledeća instrukcija. Metode predviđanja se svrstavaju u statičke i dinamičke. U slučaju statičkih metoda predviđanje za svaki skok je uvek isto za vreme kompletnog izvršavanja programa. U slučaju dinamičkih metoda predviđanje se menja u toku izvršavanja programa, na osnovu prethodnog ponašanja programa.

1. Statičko predviđanje

U ovom poglavlju se razmatraju četiri statičke metode ponašanja pri skokovima u pipeline-u: zaustavljanje, predviđanje nema skoka (not taken), predviđanje ima skoka (taken) i zakašnjen skok (delayed branch). Prve tri metode su hardverske, dok je četvrta metoda softverska.

1. Zaustavljanje

Najjednostavnija metoda ponašanja pri skoku je zaustavljanje pipeline-a čime se očitavanje prve sledeće instrukcije iza instrukcije skoka zaustavlja onoliko perioda signala takta koliko je potrebno da se utvrdi sledeća vrednost PC-ja. Ova metoda je primamljiva jer je veoma jednostavna za realizaciju. Situacija u pipeline-u za procesor sa slike 3-4 u slučaju korišćenja ove metode data je na slikama IV-1, IV-2 i IV-3.

2. Predviđanje nema skoka (not taken)

Moguća metoda ponašanja pri skoku je da se uvek predvidi da neće biti skoka. Kod ove metode hardver produžava sa očitavanjem i izvršavanjem instrukcija iza instrukcije skoka kao da skoka neće biti, pri čemu se mora voditi računa o tome da instrukcije iza instrukcije skoka ne smeju da menjaju stanje u procesoru sve dok ishod instrukcije skoka nije poznat. U slučaju da nema skoka produžava se sa izvršavanjem očitanih instrukcija, jer se u pipeline-u nalaze korektne instrukcije. U slučaju da ima skoka treba zaustaviti pipeline i isprati ga (flush) od pogrešnih instrukcija. To se postiže restartovanjem pipeline-a od koraka IF instrukcije na koju se skočilo. U slučaju modifikovanog procesora pipeline organizacije (slika 3-22), stanje u pipeline-u za tehniku predviđanja nema skoka u slučaju kada nije bilo skoka dato je na slici IV-7, a za slučaj kada je bilo skoka na slici IV-8.

Odluka o skoku se za modifikovani procesor pipeline organizacije donosi u stepenu ID. Ako nema skoka u stepenu IF je korektna instrukcija pa se izvršavanje produžava (slika IV-7). Ako ima skoka u stepenu IF je pogrešna instrukcija, pa se korak IF ponavlja, ali sada za instrukciju na koju se skočilo (slika IV-8). Da je odlučivanje o skoku ostalo u stepenu MEM, onda bi se u slučaju kada nema skoka ubacivala dva a u slučaju kada ima skoka tri idle perioda takta (slike IV-2 i IV-3).

	1	2	3	4	5	6	7	8	9
instr. i (branch not taken)	IF	ID	EX	MEM	WB
instr. i +  1		IF	ID	EX	MEM	WB
instr. i +  2			IF	ID	EX	MEM	WB
instr. i +  3				IF	ID	EX	MEM	WB
instr. i +  4					IF	ID	EX	MEM	WB

Slika IV-7 Stanje u pipeline-u za tehniku predviđanja nema skoka ako nije bilo skoka

	1	2	3	4	5	6	7	8	9
instr. i (branch taken)	IF	ID	EX	MEM	WB
instr. i + 1		IF	idle	idle	idle	idle
instr. sa adr. skoka			IF	ID	EX	MEM	WB
instr. sa adr. skoka + 1				IF	ID	EX	MEM	WB
instr. sa adr. skoka + 2					IF	ID	EX	MEM	WB

Slika IV-8 Stanje u pipeline-u za tehniku predviđanja nema skoka ako je bilo skoka

3. Predviđanje ima skoka (taken)

Moguća metoda ponašanja pri skoku je da se uvek predvidi da će biti skoka. Kod ove metode čim se dekoduje instrukcija skoka i sračuna adresa skoka, predviđa se da će biti skok, pa se počinje sa očitavanjem i izvršavanjem instrukcija od instrukcije na koju se predviđa da će se skočiti. Kada se utvrdi da li je zaista skok napravljen ili ne izvršavanje se produžava dvojako. Ako je skok napravljen u pipeline-u su korektne instrukcije, pa treba produžiti sa očitavanjem i izvršavanjem instrukcija. Ako skok nije napravljen, treba očistiti pipeline od instrukcija iza instrukcije skoka, jer su pogrešne, i krenuti sa korakom IF prve instrukcije iza instrukcije skoka.

U slučaju modifikovanog procesora pipeline organizacije (slika 3-22) ova metoda nema smisla, jer se u stepenu ID dekoduje instrukcija skoka, utvrđuje adresa skoka i odlučuje da li treba napraviti skok ili ne. Ova metoda nema smisla ni kod prvobitne varijante razmatranog procesora pipeline organizacije (slika 3-4). Kod nje se u stepenu ID dekoduje instrukcija skoka, a adresa skoka utvrđuje u stepenu MEM. Međutim, u istom stepenu se i odlučuje da li ima ili nema skoka, pa opet ova metoda predviđanja nema smisla.

Ova metoda bi imala smisla ukoliko bi se, na primer, u stepenu ID ne samo dekodovala instrukcija skoka, već i utvrđivala adresa skoka, a tek u stepenu MEM odlučivalo da li ima ili nema skoka. U slučaju takvog procesora pipeline organizacije, stanje u pipeline-u za tehniku predviđanja ima skoka u slučaju kada je bilo skoka dato je na slici IV-9, a za slučaj kada nije bilo skoka na slici IV-10. U oba slučaja se u stepenu ID utvrđuje da je reč o instrukciji skoka i sračunava se adresa skoka. Za to vreme u stepenu IF se čita instrukcija koja je fizički u programu iza nje. S obzirom da je uvek predviđanje da će biti skok, instrukcija koja se čita u stepenu IF ne odgovara predviđanju. Stoga se na takt iz stepena ID u registar PC stepena IF upisuje adresa instrukcije na koju se skače, a instrukcija očitana u stepenu IF kod prebacivanja, na isti takt, u stepen ID pretvara u instrukciju bez dejstva. U oba slučaja je situacija u pipeline-u ista do kompletiranja faze MEM instrukcije skoka, uz izgubljen jedan takt. Posle toga situacija u pipeline-u se razlikuje za slučajeve kada je bilo skoka (slika IV-9) i kada nije bilo skoka (slika IV-10). U slučaju da je bilo skoka, pošto je u predviđanje bilo da ima skoka, u pipeline-u su korektne instrukcije, pa se produžava sa sekvencijalnim očitavanjem instrukcija bez dodatnih gubitaka taktova. U slučaju da nije bilo skoka, u stepenu EX je instrukcija bez dejstva, a u stepenima ID i IF pogrešne instrukcije. Stoga se i instrukcije u stepenima ID i IF pretvaraju u instrukcije bez dejstva, i time čisti (flush) pipeline od instrukcija koje se nalaze počevši od adrese skoka, čime se gube još dva takta. Iz stepena MEM se u registar PC u stepenu IF upisuje adresa prve sledeće instrukcije iza instrukcije skoka koja je not taken i u taktu 5 se u stepenu IF vrši njeno očitavanje.

instr. i (branch taken)	IF	ID	EX	MEM	idle
instr. i +  1		IF	idle	idle	idle	idle
instr. sa adr. skoka			IF	ID	EX	MEM	WB
instr. sa adr. skoka +  1				IF	ID	EX	MEM	WB
instr. sa adr. skoka +  2					IF	ID	EX	MEM	WB

Slika IV-9. Stanje u pipeline-u za tehniku predviđanja ima skoka ako je bilo skoka

Instr. i (branch not taken)	IF	ID	EX	MEM	idle
Instr. i +  1		IF	idle	idle	idle	idle
Instr. sa adr. skoka			IF	ID	idle	idle	idle
Instr. sa adr. skoka +  1				IF	idle	idle	idle	idle
Instr. i +  1					IF	ID	EX	MEM	WB
Instr. i +  2						IF	ID	EX	MEM	WB

Slika IV-10. Stanje u pipeline-u za tehniku predviđanja ima skoka ako nije bilo skoka

Efekat tehnike predviđanja ima skoka za slučaj procesora pipeline organizacije kod koga bi se u stepenu ID dekodovala instrukcija skoka i utvrđivala adresa skoka, a u stepenu MEM odlučivalo o skoku, je jedan izgubljen takt ako ima skoka i tri izgubljena takta ako nema skoka.

4. Zakašnjen skok (delayed branch)

Kod nekih procesora negativni efekti upravljačkog hazarda se ublažavaju ili eliminišu korišćenjem softverske metode zakašnjeni skok (delayed branch). Kod ove metode se tokom prevođenja iza instrukcije skoka stavlja onoliko instrukcija koliko bi perioda signala takta trebalo zaustaviti pipeline dok se ne donese odluka o tome koja će se sledeća instrukcija iza instrukcije skoka izvršavati. To moraju da budu instrukcije koje treba izvršiti bez obzira na to da li je kao rezultat izvršenja instrukcije skoka skok napravljen ili ne. Ova metoda, slično kao i tehnika zakašnjenog punjenja (delayed load), zahteva da u vreme prevođenja prevodilac nađe instrukcije koje može da smesti iza instrukcije skoka. U slučaju modifikovakog procesora pipeline organizacije (slika 3-22) odlučivanje o skoku se realizuje u stepenu ID, pa bi zaustavljanje pipeline-a bilo jedna ili nijedna perioda signala takta. Stoga bi pri korišćenju ove metode trebalo ubaciti jednu instrukciju. U slučaju nemodifikovanog procesora pipeline organizacije (slika 3-4) odlučivanje o skoku bi se realizovalo u stepenu MEM, pa bi zaustavljanje pipeline-a bilo tri ili dve periode signala takta. Stoga bi bi pri korišćenju ove metode trebalo ubaciti tri instrukcije.

Jedan primer sekvence instrukcija bez i sa primenom ove tehnike dat je na slici IV-11.

Slika IV-11 Zakašnjen skok jedne periode signala takta sa nezavisnom instrukcijom

Ovo je najjednostavniji slučaj kada postoji nezavisna instrukcija čije izvršavanje ne utiče na uslovni skok. Instrukciju add, stoga, može prevodilac prebaciti iza instrukcije beqz. Ona treba uvek da se izvršava i izvršavaće se bez zaustavljanja pipeline-a zbog instrukcije skoka beqz bez obzira da li će biti skoka ili ne.

Slika 3.28 Popunjavanje branch-delay slotova

1. Dinamičko predviđanje

Dinamičko predviđanje skokova zahteva postojanje posebnog hardvera koji će dinamički predviđati da li će skok biti napravljen ili ne. Za razliku od hardverskih tehnika koje to rade statički, uvek predviđajući da će skok biti napravljen (taken) ili da neće biti napravljen (not taken), hardver za dinamičko predviđanje skokova menja svoje predviđanje u toku samog izvršavanja programa.

Razmotriće se nekoliko vrsta tehnika. One se razlikuju po složenosti, po stepenu pipeline-a gde treba da bude smešten dodatni hardver i po efikasnosti.

Najjednostavnija tehnika je tehnika sa baferom predviđanja (branch prediction buffer). Ona podrazumeva postojanje male memorije u koju se ulazi na osnovu nekoliko najmlađih bitova adrese instrukcije skoka. Memorija u svakoj lokaciji sadrži samo jedan bit koji se naziva bit predviđanja i koji vrednostima 1 i 0 određuje da li je pri poslednjem izvršavanju instrukcije skoka na toj adresi skok napravljen ili ne. Ako je vrednost 1 očitavanje i izvršavanje instrukcije se produžava sa adrese skoka. U suprotnom slučaju produžava se sekvencijalno. Ako se kasnije u stepenu pipeline-a u kome se odlučuje da li treba napraviti skok ili ne utvrdi da je predviđanje bilo pogrešno, sve instrukcije u pipeline-u iza instrukcije skoka se ispiraju i kreće se sa očitavanjem korektne instrukcije. Pritom se bit predviđanja u memoriji invertuje.

Korišćenje bafera predviđanja je moguće u stepenu pipeline-a u kome se dekoduje instrukcija, jer se na osnovu toga što je dekodovana instrukcija skoka utvrđuje da treba ići u bafer predviđanja. U slučaju razmatranog procesora pipeline organizacije to je stepen ID. Potrebno je, dalje, da može da se u tom istom stepenu formira adresa skoka, da bi se, u slučaju predviđenog skoka, na sledeći takt produžilo sa izvršavanjem programa od instrukcije na koju se skače. U slučaju modifikovanog procesora pipeline organizacije adresa skoka se, takođe, zna u stepenu ID. Međutin, primena ove tehnike kod njega nema smisla, jer se u stepenu ID i zna da li skok treba napraviti ili ne.

Ova tehnika bi imala smisla ukoliko bi se odluka o skoku donosila u nekom kasnijem stepenu pipeline-a, na primer MEM, a instrukcija dekodovala i adresa skoka utvrđivala u nekom ranijem stepenu, na primer ID. Tada bi se na osnovu predikcije u stepenu ID produžilo sa očitavanjem instrukcija. U stepenu MEM se utvrđuje za instrukciju skoka da li skoka ima ili ne, pa se na osnovu toga i utvrđuje da li je predikcija bila dobra ili ne, i da li treba praviti korekciju očitanih instrukcija iza instrukcije skoka ili ne, i da li treba invertovati bit predikcije ili ne.

Treba zapaziti da je, zbog toga što se u bafer predviđanja ulazi na osnovu nekoliko najmlađih bitova adrese instrukcije skoka, moguće da različite instrukcije skoka, ukoliko se nalaze na adresama koje imaju iste najmlađe bitove koji se koriste za ulaz u bafer predviđanja, koriste isti bit predviđanja. Može se desiti da se predviđanje za neku instrukciju skoka donosi na osnovu vrednosti bita predviđanja koji je postavila neka druga instrukcija skoka. Ovo bi, međutim, trebalo dosta retko da se javlja.

Ova tehnika predikcije je jednostavna za realizaciju. Ona, međutim, ima nedostatak u petljama gde se skok, sem kada se izlazi iz petlje, stalno pravi. Iako se ovde skok samo jedanput ne pravi, ova tehnika će dva puta pogrešno predvideti. Kod prvog prolaska kroz petlju kada se prođe kroz instrukciju skoka pogrešno će se predvideti da neće biti skoka a napraviće se skok i postaviće se bit predviđanja. Kod svakog sledećeg prolaska postavljen bit predviđanja korektno će predvideti skok. Kod poslednjeg prolaska kroz petlju predvideće se pogrešno skok, jer se tada izlazi iz petlje, i invertovaće se bit predviđanja. Kod novog ulaska u petlju, i to kod prvog prolaska, ponovo će biti predviđanje da neće biti skoka. Da bi se ovakve situacije efikasnije rešavale veoma često se koristi šema predviđanja sa 2 umesto sa 1 bitom. Ažuriranje dvobitne vrednosti i korišćenje tih vrednosti za predikciju su dati na slici IV-12.

Sa slike se vidi da će se posle dva ili više napravljenih skokova (taken) snažno preporučivati (predict taken—strong) da se sledeći put napravi skok. Posle prvog nenapravljenog skoka (not taken) još uvek će se ali nešto slabije (predict taken—weak) preporučivati da se sledeći put napravi skok. Posle dva uzastopna nenapravljena skoka (not taken) sledeći put će se snažno preporučivati (predict not taken—strong) da se sledeći put ne pravi skok. Posle prvog napravljenog skoka još uvek će se ali slabije preporučivati (predict not taken—weak) da se sledeći put ne pravi skok. Posle dva uzastopna napravljena skoka ponovo će se snažno preporučivati (predict taken—strong) da se sledeći put pravi skok.

Korišćenje bafera predviđanja sa 2 bita, trenutak ažuriranja bafera, situacije koje mogu da nastanu u pipeline-u i način njihovog rešavanja su isti kao i kod bafera predviđanja sa 1 bitom.

Nedostatak tehnika predviđanja sa baferom predviđanja je da se odlučivanje na osnovu bafera predviđanja može realizovati tek kada se utvrdi da je reč o instrukciji grananja. To je moguće uraditi tek u stepenu pipeline-a u kome se dekoduje instrukcija. Ako je stepen dekodovanja instrukcije prvi stepen (ID) iza stepena čitanja instrukcije (IF) onda se sa očitavanjem predviđene instrukcije posle instrukcije skoka uvek kasni jednu periodu signala takta.

Da bi se ovo izbeglo potrebno je još dok se instrukcija skoka čita u stepenu IF utvrditi da li se čita instrukcija skoka, napraviti predviđanje da li će se skok realizovati ili ne, i ako je predviđanje da će se skok realizovatim utvrditi adresu skoka. Time će biti omogućeno da se na isti takt, kojim se očitana instrukcija skoka prebacuje iz stepena IF u stepen ID u kome se tek vrši njeno dekodovanje, krene u stepenu IF sa očitavanjem instrukcije sa adrese prema predviđenom ishodu skoka.

Za realizaciju ovoga se koristi keš za predikciju skokova (slika IV-13). U slučaju asocijativne realizacije keša u asocijativnom delu se čuvaju adrese za koje se zna da su na njima poznate instrukcije skokova. U odgovarajućem ulazu RAM dela nalazi se predviđena vrednost za PC sa koje treba očitati sledeću instrukciju i informacija da li je to adresa za skok koji se predviđa da se realizuje ili ne realizuje.

1. Ako se nalazi to znači da je instrukcija koja se čita instrukcija skoka koja je već bila izvršavana, pa za nju postoji predviđanje da li će biti skoka ili ne. Treba očitati predviđenu adresu sledeće instrukcije iz RAM dela keša zajedno sa informacijom o tipu predviđanja za instrukciju skoka. Očitana adresa instrukcije zajedno sa informacijom o tipu predviđanja za skok se šalje na takt u stepen ID, a u IF počinje čitanje sa predviđene adrese.
2. Ako se ne nalazi to znači ili da nije reč o instrukciji skoka ili je reč o instrukciji skoka koja do sada nije izvršavana.

1. ažurirati keš memoriju,
2. videti da li su instrukcije iza te instrukcije dobre.

• ako nema tog ulaza—unošenje kompletnih informacija,
• ako ima tog ulaza—ažuriranje bitova za predviđanje i možda predviđene vrednosti za PC ako dođe do promene predviđanja.

Videti da li su instrukcije iza te instrukcije dobre zahteva:

• ako za tu instrukciju nije bilo ulaza u keš memoriji pa nije bilo predviđanja:

• skok napravljen—ispire se,
• skok nije napravljen—u redu;

• ako je za tu instrukciju bio ulaz u keš memoriji pa je bilo predviđanja:

• pogrešno predviđeno—ispire se,
• dobro predviđeno—u redu.

Slika IV-13 Keš za predikciju skokova asocijativne realizacije

Slika 3-42 Protočna obrada sa tri dodatne FP jedinice

Slika 3-44 Protočna obrada koja podržava protočnu obradu više FP instrukcija