Katedra za elektroniku

Elektrotehnički fakultet
Univerzitet u Banjoj Luci

Uvod u arhitekturu računara kroz RISC-V

instrukcijski set

Slaven Smiljanić, dipl. inž. el.

Odabrana poglavlja iz arhitekture računarskih sistema

doc. dr Aleksandar Pajkanović

Ocjena:
 Sadržaj

Predgovor 2

1 Osnovni pojmovi arhitekture računara 3

1.1 Instrukcijski set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.1 Osobine instrukcijskog seta . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Protočna obrada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2.1 Mjerenje performansi procesora - CPI . . . . . . . . . . . . . . . . 8
1.2.2 Hazardi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2.3 Tehnika prosljeđivanja . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.3 Memorijska hijerarhija . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.3.1 Keš memorija . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2 RISC-V instrukcijski set 16

2.1 Organizacija instrukcijskog seta . . . . . . . . . . . . . . . . . . . . . . . . 16

3 Chisel jezik za opis hardvera 18

4 Sodor 19
4.1 Chipyard . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
4.1.1 Instalacija i konfiguracija . . . . . . . . . . . . . . . . . . . . . . . . 19
4.2 Simulacija na Sodor jezgrima . . . . . . . . . . . . . . . . . . . . . . . . . 21
4.2.1 Ispitivanje raspodjele tipova instrukcija pomoću jednostepenog pro-
cesora . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
4.2.2 Ispitivanje CPI pomoću jednostepenog procesora . . . . . . . . . . 23
4.2.3 Ispitivanje CPI pomoću petostepenog procesora . . . . . . . . . . . 26
4.2.4 Procjena potencijalne modifikacije petostepenog procesora . . . . . 28
4.2.5 Zadatak . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

5 Rocket Chip 31
5.1 Struktura . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
5.2 Pripremanje potrebnih datoteka . . . . . . . . . . . . . . . . . . . . . . . . 32
5.3 Simulacija na Rocket jezgrima . . . . . . . . . . . . . . . . . . . . . . . . . 33
5.3.1 Zadatak: Cache blocking mehanizam . . . . . . . . . . . . . . . . . 35
5.3.2 Ispitivanje uticaja načina asocijativnosti na performanse keš memorije 35

1
 Predgovor

Ovaj tekst je namijenjen studentima koji tek ulaze u svijet arhitekture računara, te za
cilj ima da na relativno jednostavan način objasni osnovne koncepte i termine iz ove
oblasti. Za ispunjenje ovog cilja, kreće se od definisanja osnovnih pojmova, te se za-
tim kroz RISC-V instrukcijski set i analize nekoliko njegovih realizacija, utvrđuju znanja
arhitekture računara i otvaraju vrata ka daljem istraživanju RISC-V instrukcijskog seta.

Prvo poglavlje ima za cilj da čitaoca upozna sa osnovnim konceptima arhitekture

računara, poput instrukcije i instrukcijskog seta, tipova instrukcijskih setova, te razlika
između njih. Ovo je neophodan korak kako bi se, sa jedne strane, čitalac upoznao sa ovim
konceptima, a sa druge, kako bi bio jasniji značaj RISC-V instrukcijskog seta. Osim po-
jma instrukcijskog seta, opisan je i koncept protočne obrade (eng. pipeline) i memorijske
hijerarhije.

Drugo poglavlje ukratko opisuje karakteristike RISC-V instrukcijskog seta.

Treće poglavlje se bavi Chisel programskim jezikom, kojim su pisana jezgra koja se
kasnije razmatraju.

U četvrtom poglavlju se, pomoću RISC-V realizacije jezgrima pod nazivom Sodor
demonstriraju koncepti protočne obrade, te se analiziraju kakve efekte na performanse
procesora imaju inženjerske odluke donesene kod projektovanja sistema protočne obrade.

U petom poglavlju se izučava koncept memorijske hijerarhije kroz eksperimente na keš

memoriji Rocket jezgra.

2
Poglavlje 1

Osnovni pojmovi arhitekture računara

1.1 Instrukcijski set

Pod pojmom instrukcijskog seta (eng. instruction set architecture - ISA) smatramo pro-
gramerski vidljiv interfejs ka hardveru računarskog sistema, odnosno alat koji je dat pro-
grameru da bi procesoru davao naredbe - instrukcije. Instrukcijski set jeste granica između
softvera i hardvera računarskog sistema. Shodno tome, nivo instrukcijskog seta je najniži
nivo apstrakcije kod razvoja softvera.

Dva najbitnija pristupa u razvoju arhitekture računara kroz istoriju su RISC i CISC.
CISC (eng. Complex Instruction Set Computer ) je termin koji se odnosi na arhitek-
turu koja ima veoma veliki broj instrukcija, specijalizovanih za tačno određene zadatke.
Najveći dio ovih instrukcija se rijetko koristi. Sa druge strane je RISC (eng. Reduced In-
struction Set Computer ), koji ima mnogo manji broj instrukcija, i to onih koje se nejčešće
koriste. CISC je stariji pristup projektovanju računara, nastao u vrijeme kada je bilo od
velikog značaja imati malu veličinu programa i mali broj pristupa memoriji.
Danas su dominantna dva različita instrukcijska seta: x86, koji je predstavnik CISC
arhitekture i ARM, predstavnik RISC arhitekture.

Instrukcijski set dobija svoje fizičko otjelotvorenje hardverskom realizacijom. Pod

realizacijom se podrazumijeva organizacija i hardver. Organizacija ili mikroarhitektura se
odnosi na odluke koje se donose na hardverski višem nivou apstrakcije, kao što su izbor
i organizacija memorije, načini interakcije sa periferijama i slično. Niži nivo apstrakcije
kod realizacije jeste hardver, odnosno odluke donesene na nivou elektronike, kao što su
izbor tehnologije integrisanih kola i načini pakovanja u kućišta i slično. Isti instrukcijski
set se može implementirati na više različitih načina, što znači da te implementacije imaju
različitu mikroarhitekturu. Primjer su x86 implementacije kompanija AMD i Intel.

1.1.1 Osobine instrukcijskog seta

Klasa
Osnovnu diferencijaciju instrukcijskih setova moguće je napraviti prema tipu interne mem-
orije. Mogućnosti u ovom kontekstu su stek, akumulator i set registara. Rani računari
su koristili stek i akumulator. Na slici 1.1 je prikazan način rada sa stekom. Kod ovog
pristupa, svi operandi su na steku, pa nema potrebe za njihovim eksplicitnim navođenjem,
što je jedna od prednosti. To znači da se, recimo instrukcija oduzimanja, SUB, izvodi tako

3
 Slika 1.1: Stek arhitektura

da se ne specifikuju operandi koje je potrebno oduzeti, niti se specifikuje gdje je potrebno

sačuvati rezultat. Svi podaci se čuvaju na steku, pa se tako prilikom oduzimanja prvo
uzmu dva podataka sa lokacije na koju pokazuje TOS1 , pa se nakon oduzimanja rezultat
opet smješta u stek.

Svi računari počevši od 1980-ih godina koriste registre opšte namjene. Arhitekture
sa registrima opšte namjene se dijele u dvije klase, jedna koja memoriji može pristupiti
svakom instrukcijom, te druga koja memoriji pristupa samo pomoću load i store instruk-
cija. Shodno tome, ove arhitekture se nazivaju register-memory arhitektura, odnosno
load-store (tj. register-register ) arhitektura. Jedini „živi" predstavnik register-memory
arhitekture jeste x86 instrukcijski set. Sa druge strane, load-store klase su sve arhitekture
novijeg datuma, a najznačajniji prestavnici su ARM, PowerPC i RISC-V.
Razlozi zbog kojih je load-store preferirana arhitektura su sljedeći:

• registri su brži od memorije,

• kompajler je efikasniji ako se koriste registri,
• registri se mogu koristiti da čuvaju varijable, čime se program ubrzava u odnosu na
čuvanje varijabli u memoriji.

Sa druge strane, nedostaci load-store arhitektura su veći programi, s obzirom da se mem-

oriji pristupa pomoću posebnih instrukcija, što dalje vodi ka većem ukupnom broju in-
strukcija u programu, što nije slučaj kod register-memory arhitektura.

1
TOS(eng. Top Of Stack ) je pokazivač na vrh steka. Koristi se i oznaka SP (eng. Stack Pointer ).
Ova adresa se čuva u registru.

4
Adresiranje memorije
Nezavisno od toga da li se radi o load-store ili nekoj drugoj arhitekturi, moraju se definisati
načini interpretacije i specifikacije memorijskih adresa.
Interpretacija memorijske adrese odgovara na pitanje kojem objektu u memoriji se pris-
tupa na osnovu specifikovane adrese i njene dužine. U okviru svih instrukcijskih setova
moguće je pristupiti mamoriji na nivou bajta, tj. memorija je bajt-adresabilna. Takođe,
omogućen je pristup i podacima od 2 bajta, 4bajta ili 8 bajtova.

Prva bitna karakteristika kod interpretacije i pristupa memoriji jeste raspored bajtova
u okviru većeg objekta. Tako se razlikuju Little Endian i Big Endian konvencije. Little
Endian konvencija niže (eng. least significant) bajtove čuva prije viših bajtova, dok je
kod Big Endian konvencije redoslijed obrnut(primjer: kada pišemo broj 0x123456, pišemo
ga u Big Endian konvenciji - to je „normalan" način na koji pišemo).

Druga karakteristika, tzv. poravnanje, se tiče pristupa objektima većih od jednog ba-
jta. Formalno, objekat veličine s bajta, na adresi A, je poravnan ukoliko važi A mod s
= 0. To znači da se bajtovi mogu čuvati na svakoj memorijskoj adresi, dvobajtni podaci
(eng. half-words) na parnim adresama, riječi (eng. words) na adresama djeljivim sa 4 i
duple riječi (eng. double-words) samo na adresama djeljivim sa 8.

Način adresiranja jeste način na koji instrukcije specifikuju memorijske adrese. Postoji
više načina adresiranja:
• registarsko - koristi se kada se potrebni podatak nalazi u registru,
• neposredno - koristi se za konstante,
• registarsko indirektno i, njemu slično, adresiranje sa pomjerajem - koriste se kada je
adresa podatka u registru, a sam podatak u memoriji,
• apsolutno ili direktno - navodi se adresa podatka, a koristi se kada se pristupa
statičkim varijablama,
• memorijsko indirektno,
• adresiranje sa autoinkrementom,
• adresiranje sa autodekrementom.

Operacije
U okviru svih današnjih arhitektura su podržane sljedeće operacije:
• aritmetičko-logičke operacije
• operacije za prenos podataka
• operacije za kontrolu tôka
• floating-point operacije
Uprkos postojanju instrukcija različitih klasa i svrhe, najčešće izvršavane instrukcije nekog
instrukcijskog seta su one najjednostavnije, kao što su učitavanja iz memorije(load ),
uslovna grananja, poređenja, sabiranja itd.

Instrukcije za kontrolu toka

5
Instrukcije za kontrolu tôka moraju biti obavezno podržane u okviru instrukcijskog seta.
Pod kontrolom tôka se podrazumijevaju skokovi (eng. jumps), tj. situacije u kojima je
promjena tôka programa bezuslovna, te grananja (eng. branches), kada je promjena tôka
programa uslovna. Osim ova dva, promjene tôka programa predstavljaju i pozivi proce-
dura, kao i povratak iz procedura na lokaciju sa koje je procedura pozvana. Mjerenja
pokazuju da su daleko najčešće instrukcije grananja.

Kôdovanje instrukcija
Pod pojmom kôdovanja instrukcija se podrazumijeva način na koji se instrukcija zapisuje
u binarnom obliku. Ova reprezentacija utiče i na veličinu programa i na implementaciju
procesora, koji mora biti u stanju da brzo dekoduje instrukciju kako bi došao do operacije
i operanada. Operacija se u okviru instrukcije specifikuje u dijelu koji se naziva opera-
cioni kôd (eng. opcode). Generalno postoje dva načina za kôdovanje instrukcija: fiksna
dužina instrukcija, što znači da svaka instrukcija ima isti broj bita, bez obzira na to što
bi potencijalno neke instrukcije zauzimale manje bita od tog fiksnog broja, i promjenjiva
dužina, koja omogućava kôdovanje instrukcija stvarnom dužinom, tj. stvarnim brojem
bita. Shodno tome, arhitekture koje preferiraju bolje performanse u odnosu na veličinu
kôda će izabrati fiksnu dužinu instrukcija, dok će arhitekture kojima je bitnija veličina
kôda izabrati varijabilnnu dužinu instrukcija.

U većini arhitektura, način navođenja instrukcija je takav da se odredišni registar

navodi prvi, a zatim se navode operandi, kao na sljedećem primjeru RISC-V instrukcije
sabiranja:

add x4, x5, x1

U ovom slučaju, vrši se sabiranje vrijednosti koje se nalaze u registrima x5 i x1, te se

rezultat smješta u registar x4.

1.2 Protočna obrada

Protočna obrada (eng. pipelining) je realizaciona tehnika kod koje se više instrukcija
preklapa prilikom izvršavanja, koristeći paralelizam između radnji koje je potrebno sprovesti
prilikom izvršavanja instrukcije.
Ideja je preuzeta iz klasične pokretne trake u fabrici. Ako se posmatra pokretna traka
koja pakuje proizvode u kutije i na kutije lijepi etikete, može se primijetiti da svaki dio
trake, svaka radna stanica, istovremeno obavlja neki zadatak, ali na različitim jedinicama
proizvodima, dok jedna jedinica prolazi kroz sve radne stanice na traci. Na sličan način
funkcioniše i protočna obrada u računaru, odnosno svaki dio sistema protočne obrade
izvršava dio instrukcije. Svaki od ovih koraka se naziva pipe stage. Ovi segmenti su
vezani tako da čine „cijev", pa instrukcija ulazi na jednom kraju „cijevi" (eng. pipe -
cijev), a izlazi na drugom.

Svaka instrukcija se može realizovati u najviše pet takt ciklusa2 , i to:

• Instruction fetch cycle - IF

2
Moguća je implementacija i sa manjim brojem takt ciklusa. Tako postoje realizacije sa dva i sa tri
ciklusa, ali ovdje se razmatra petostepena realizacija, koja je uobičajena.

6
 Slika 1.2: Klasični petostepeni sistem protočne obrade

Adresa instrukcije se trenutno nalazi u PC registru, pa se instrukcija dohvata (eng.

fetch - dohvatiti) sa ove adrese. Osim toga, na vrijednost u PC registru se dodaje
4, tj. adresa sljedeće instrukcije.
• Instruction decode / register fetch cycle - ID
U ovoj fazi se dekodira instrukcija i čitaju se odgovarajući registri. Ove dvije op-
eracije se kod RISC-V odvijaju paralelno, jer su izvorni i destinacijski registri uvijek
na fiksnoj poziciji.
• Execution/effective address cycle - EX
Nad operandima koji su pripremljeni u prethodnoj fazi, ALU izvodi operaciju speci-
fikovani opcode dijelom instrukcije. Takođe, ukoliko se instrukcijom čita podatak iz
memorije, efektivna adresa podatka se priprema u ovoj fazi.
• Memory access - MEM
Ako je trenutna instrukcija load, čita se memorija sa efektivne adrese izračunate u
prethodnoj fazi. Ako je instrukcija store, na efektivnu adresu se upisuje podatak.
• Write-back cycle - WB
U registarski fajl3 se upisuje rezultat, ukoliko se operacija vršila nad registrima ili
ako je u pitanju load instrukcija.

Ukoliko se ne bi koristio princip protočne obrade, svaka instrukcija bi čekala na pot-

puno izvršenje prethodne instrukcije. U primjeru sa trakom u fabrici, to bi značilo da
bi se u jednom momentu radilo samo na jednoj jedinici proizvoda. Implikacije u kontek-
stu poslovanja fabrike u ovom slučaju su brojne. Fabrika ima mnogo manji throughput,
odnosno mnogo manji obim proizvodnje, jer je broj proizvoda koje napravi na dnevnom
nivou manji. Dalje, jedan radnik na traci ostaje da čeka dok svi radnici ne završe svoje
zadatke. To znači da radnik većinu radnog vremena ne radi koristan posao, te ga fabrika
uzalud plaća. Primijetno je da je fabrika u ovom slučaju neefikasna i da negativno posluje.
Isto važi i za procesor. Cilj dizajnera bi trebalo da je potpuno iskorištenje procesorskog
vremena. To znači da se ne smije dopustiti da bilo koji dio ne radi koristan posao većinu
svog vremena.
Ukoliko se, pri petostepenoj realizaciji instrukcija, nova instrukcija startuje na svaki
takt impuls, dobija se osnovni RISC pipeline, kao na slici 1.2. Svaka od prethodno opisanih
faza izvršavanja postaje pipe stage, odnosno dio sistema protočne obrade. Ovaj meha-
nizam ne sadrži samo to, odnosno nije tako jednostavan iz razloga što je neophodan i
3
Registri procesora se organizuju u strukturu koju nazivamo registarski fajl. Adekvatan naziv je i skup
registara.

7
način za prevenciju potencijalnih problema koji se mogu javiti ako se isti data path 4 is-
tovremeno koristi za izvršavanje dvije ili više operacija. Npr. nije moguće da ALU izvrši
i izračunavanje efektivne adrese i sabiranje podataka istovremeno. S obzirom na to, mora
se implementirati i kontrola pipeline-a.
Tehnika protočne obrade povećava broj izvršenih instrukcija u jedinici vremena, ali
ne smanjuje vrijeme izvršavanja pojedinih instrukcija. Upravo suprotno, ova tehnika
i povećava vrijeme izvršavanja instrukcije zbog overhead -a koji postoji zbog kontrole
pipeline-a. Povećanje broja izvršenih instrukcija u jedinici vremena (eng. instruction
throughput) zapravo znači da se program izvršava brže, iako se niti jedna instrukcija ne
izvršava brže.

1.2.1 Mjerenje performansi procesora - CPI

Bitan parametar za karakterizaciju performansi procesora je CPI - Cycles Per Instruction,
odnosno broj takt ciklusa po instrukciji. Ovaj parametar se računa kao količnik broja
ciklusa potrebnih za izvršavanje programa i broja instrukcija u programu:
Broj takt ciklusa programa
CP I = (1.1)
Broj instrukcija programa
Takođe, nekada je korisno izračunati broj takt ciklusa programa na sljedeći način:
n
X
CP Uciklusi = ICi × CP Ii (1.2)
i=1

gdje ICi govori koliko puta se instrukcija i izvršila u programu, a CP Ii predstavlja pros-
ječan broj takt impulsa po instrukciji za instrukciju i.
Ukupan CPI se u ovom slučaju računa kao
Pn
i=1 ICi × CP Ii
CP I = (1.3)
Broj instrukcija
Primjer 1: Posmatra se procesor na kojem su izvršena sljedeća mjerenja:

• Frekvencija FP operacija5 : 25%

• Prosječan CPI FP operacija: 4.0

• Prosječan CPI ostalih instrukcija: 1.33

• Frekvencija FSQRT6 instrukcije: 2%

• CPI FSQRT instrukcije: 20

4
Skup funkcionalnih jedinica koje obavljaju obradu podatka. Ovaj skup čine ALU, skup registara, te
magistrale koje ih povezuju.
5
FP (eng. Floating Point) su operacije u pokretnom zarezu.
6
FSQRT instrukcija računa kvadratni korijen podatka iz rs1 registra i rezultat smješta u rd registar.
RISC-V ISA Specification (https://riscv.org/wp-content/uploads/2017/05/riscv-spec-v2.2.pdf), strana
50.

8
Postoje dvije alternative: smanjiti CPI FSQRT instrukcije na 2 ili smanjiti prosječni CPI
svih FP operacija na 2.5. Potrebno je uporediti ova dva dizajna u kontekstu CPI.

Rješenje: U obije dizajnerske alternative se mijenja samo CPI. Originalni CPI se

pronalazi na sljedeći način:
n
X ICi
CP Iukupno, orig = CP Ii × ( )
broj instrukcija
i=1
(1.4)
= (4 × 25%) + (1.33 × 75%)
= 2.0
Prva alternativa je smanjenje CPI za FSQRT na 2. Novi CPI možemo dobiti na
sljedeći način:
CP Iukupno, noviF SQRT = CP Iorig − 2% × (CP IstariF SQRT − CP InoviF SQRT )
= 2.0 − 2% × (20 − 2) (1.5)
= 1.64
Druga alternativa je smanjenje prosječnog CPI za sve FP operacije na 2.5. Novi CPI
možemo dobiti na sljedeći način:
CP Iukupno, noviF P = (75% × 1.33) + (25% × 2.5)
(1.6)
= 1.625
Primjer 2: Posmatra se procesor sa frekvencijom od 4GHz, koji koristi 4 ciklusa
za ALU operacije i grananja, te 5 ciklusa za pristup memoriji. Pretpostavka je da su
relativne frekvencije ovih operacija 40% (ALU operacije), 20% (grananja) i 40% (pristup
memoriji). Osim toga, pretpostavka je i da će postojati 0.1ns overhead -a ako se doda
protočna obrada. Potrebno je odrediti koliko ubrzanje se dobija dodavanjem mehanizma
protočne obrade.

Rješenje: Potrebno je odrediti koliko je prosječno vrijeme izvršavanja instrukcije na

ovom procesoru. Ovaj podatak se dobija tako što se period takt signala pomnoži pros-
ječnim brojem takt impulsa po instrukciji (eng. Average CPI ). Prosječni CPI se dobija
množenjem relativnih frekvencija operacija sa brojem ciklusa koje te operacije zahtije-
vaju. U ovom slučaju je prosječni CPI jednak 4.4(60%*4 + 40%*5). To daje prosječno
vrijeme izvršavanja instrukcije od 2.2ns. Ukoliko bi se u ovom procesoru koristila tehnika
protočne obrade, prosječno vrijeme izvršavanja instrukcije bi bilo jednako periodu takt
signala na koji se dodaje overhead koji unosi protočna obrada, što ukupno iznosi 0.6ns.
S obzirom na to, zaključuje se da je dobijeno ubrzanje jednako 3.7, odnosno procesor koji
koristi pipeline je brži 3.7 puta.

1.2.2 Hazardi
Problemi u funkcionisanju mehanizma protočne obrade se javljaju kada su instrukcije u
sistemu protočne obrade međusobno zavisne. Ove situacije dovode do tzv. hazarda, koji
sprječavaju sljedeću instrukciju u sekvenci instrukcija da se izvrši u njenom predviđenom
takt ciklusu. S obzirom na to, ubrzanje koje bi se dobilo realizacijim mehanizma protočne
obrade se umanjuje. Postoje tri klase hazarda:

9
 • Strukturalni hazardi nastaju ukoliko više instrukcija koristi neki hardverski resurs
istovremeno. Ovaj tip hazarda ne utiče mnogo na performanse, te je relativno
rijedak.
• Hazardi podataka nastaju kada instrukcija zavisi od rezultata prethodne instrukcije.
• Kontrolni hazardi nastaju usljed postojanja instrukcija grananja i drugih instrukcija
koje mijenjaju programski brojač(PC).
U kontekstu ovog teksta, bitni su hazardi podataka, koji nastaju kada mehanizam pro-
točne obrade efektivno promijeni redoslijed čitanja i upisa registara koje sadrže operande,
pa je redoslijed različit u odnosu na stvarni, tj. sekvencijalno izvršavanje instrukcija.
Kako je kod pojave hazarda bitan redoslijed izvršavanja instrukcija, bitna je i sljedeća
podjela procesora:
• in-order procesori su klasični procesori, koji instrukcije izvršavaju sekvencijalno.
Ovi procesori su u fokusu ovog teksta. Primjer in-order procesora je Rocket RISC-
V procesor.

• out-of-order procesori ne moraju nužno izvršavati instrukcije sekvencijalno - ukoliko

ne postoji zavisnost, vrši se preraspodjela instrukcija tako da se izvršava instrukcija
koji ne mora biti sljedeća po programskom redoslijedu, pa se program brže izvršava.
Do preraspodjele dolazi ako neka instrukcija čeka na dostavljanje podatka iz memo-
rije i slično. Primjer out-of-order procesora je BOOM RISC-V procesor. Ovaj tekst
se ne bavi out-of-order izvršavanjem.
Neka se instrukcija i pojavljuje prije instrukcije j i neka obije koriste registar x. Razlikuju
se tri tipa hazarda koji mogu nastati u ovoj situaciji:
• RAW (Read After Write) je najčešći tip hazarda podataka, koji nastaje kada in-
strukcija j pročita vrijednost registra x prije nego što instrukcija i upiše rezultat.
To znači da instrukcija j dobija pogrešnu vrijednost.
• WAR (Write After Read ) nastaje kada instrukcija i pročita vrijednost registra x
nakon što instrukcija j upiše vrijednost u x. Ova situacija je nemoguća u klasičnom
petostepenom mehanizmu protočne obrade, ali se može desiti kod primjene tehnike
preraspodjele instrukcija, što nije u fokusu ovog teksta.
• WAW (Write After Write) tip hazarda, takođe nemoguć u klasičnom petostepenom
mehanizmu protočne obrade, nastaje kada instrukcija i upiše vrijednost u registar
x nakon instrukcije j. To znači da će registar x u ostatku programa imati pogrešnu
vrijednost.

1.2.3 Tehnika prosljeđivanja

Ukoliko prilikom izvršavanja dođe do hazarda, moraju se poduzeti koraci koji će obezbi-
jediti integritet podataka u nastavku programa. Naivno rješenje bi bilo da se zaustavi
izvršavanje svih instrukcija koje zavise od rezultata neke prethodne instrukcije sve dok se
ona ne završi (eng. stall 7 ). Problem sa ovim rješenjem jeste što je broj zavisnosti između
instrukcija ogroman, te bi zaustavljanje mehanizma protočne obrade bilo prečesto, što bi
uništilo ubrzanje koje se može dobiti.

7
Umjesto pojma stall često se koristi i izraz bubble.

10
 Rješenje koje je bolje i koje se uobičajeno koristi jeste tzv. tehnika prosljeđivanja (eng.
forwarding ili bypassing).

Hazardi nastaju u trenucima kada više instrukcija vrši čitanje ili upis u registarski
fajl. Registarski fajl se upisuje u prvoj polovini takt impulsa, a čita u drugoj. Ukoliko
instrukcija i izvršava operaciju čiji će rezultat biti upisan u registar x, taj rezultat se neće
upisati sve do pete, tj. WB faze instrukcije i. Ako sljedeća instrukcija u sistemu protočne
obrade treba da pročita vrijednost registra x, ona bi morala da čeka završetak prethodne
instrukcije, tj. instrukcije koja vrši upis, što bi bilo čekanje dužine tri takt ciklusa. Ovaj
problem je prisutan u sljedećem primjeru:

add x4, x5, x1

sub x2, x4, x3

Problem se javlja kod registra x4, u koji upisuje instrukcija add, a čita instrukcija sub.
Ovdje bi instrukcija sub morala da čeka tri takt ciklusa, što bi uzrokovalo da sve os-
tale instrukcije u sistemu čekaju. Rješenje koje nudi tehnika prosljeđivanja jeste da se
ne čeka na WB fazu kritične instrukcije, već da se njen rezultat proslijedi direktno na
mjesto gdje je potreban sljedećoj instrukciji. To se realizuje dodavanjem dijela hardvera
koji će da prepozna zavisnosti među instrukcijama sistemu protočne obrade. ALU će da
generiše dati rezultat u EX fazi add instrukcije, pa nema potrebe da se čeka na njegovo
upisivanje u x4 registar u WB fazi. Dodatni dio hardvera će jednostavno da uzme rezul-
tat sa izlaza ALU jedinice i vrati ga na mjesto čitanja x4 registra od strane sub instrukcije.

Tehnika prosljeđivanja ne uklanja stopiranje sistema u potpunosti, tj. postoje hazardi

koji se ne mogu otkloniti ovom tehnikom, što je slučaj kod load instrukcije. Kao što je
napomenuto ranije, kod ove instrukcije se efektivna adresa računa u EX fazi, a memoriji
se pristupa u MEM fazi, što znači da je rezultat dostupan tek nakon ove faze. To implicira
čekanje (tj. stall ) od jednog takt ciklusa.

1.3 Memorijska hijerarhija

Značajan dio računarskog sistema, koji omogućava trajno ili privremeno čuvanje instruk-
cija i podataka jeste memorija. Idealno bi bilo da memorija bude beskonačnog kapaciteta
i brzine, tako da je svaki podatak dostupan istog trenutnka kada je i potreban, te da je
moguće čuvanje beskonačno mnogo podataka. To naravno nije moguće, te se ovakvom
ponašanju, makar u kontekstu brzine, teži približiti različitim tehnikama. Za realizaciju
memorije se koristi koncept hijerarhije, tj. konstruiše se sistem sačinjen od više nivoa
memorije, različite brzine i kapaciteta. To omogućava stvaranje iluzije memorije beskon-
ačne brzine iz ugla programera.
Za lakše razumijevanje ovog koncepta, posmatra se sljedeća analogija8 . Student ima
zadatak da napiše seminarski rad o istorijskom razvoju računara, a dostupna mu je
isključivo biblioteka. Student sjedi za stolom u biblioteci, gdje je donio nekoliko knjiga na
ovu temu, te pokušava da pronađe sve neophodne računare koje će opisati u svom radu,
a koji su bitni u kontekstu istorijskog razvoja računara. Nakon pretrage po knjigama
koje je izdvojio, student shvata da nedostaje opis još jednog bitnog računara, te odlazi
do dijela biblioteke gdje su smještene knjige na ovu temu, te pronalazi još jednu knjigu,
8
Primjer iz knjige Comupter Organization and Design: RISC-V Edition, Patterson, Hennessy

11
koju takođe dodaje na sto. Kada je skupio sve relevantne knjige, velika je vjerovatnoća
da se sve što je potrebno da opiše nalazi u knjigama na stolu, te da neće biti potrebe da
ponovo odlazi do police po novu knjigu. Činjenica da ima sve bitne knjige na stolu, tj. u
blizini, znači da će uštedjeti vrijeme potrebno za odlazak po knjigu i njeno vraćanje na
policu, što bi bilo neophodno ako bi pregledao samo po jednu knjigu.
Ova ideja je prisutna i u realizaciji memorije u računaru. Studentu definitivno nisu
potrebne sve knjige iz biblioteke. S obzirom na to da je njegova tema fokusirana na neku
određenu oblast, njemu su potrebne samo knjige iz te oblasti, dok je mala vjerovatnoća
da će mu trebati neke druge. Isto važi i u računaru, tj. program ne zahtijeva pristup
podacima sa istom vjerovatnoćom. U suprotnom bi bilo nemoguće učiniti pristup memoriji
brzim, isto kao što bi i studentu bilo nemoguće da sve knjige iz biblioteke donese na sto i
još uvijek brzo pronađe relevantne informacije.
Prethodno opisani mehanizam se naziva princip lokalnosti. Ovaj princip govori da
programi pristupaju relativno malom dijelu svog adresnog prostora u jednom vremenskom
trenutku, kao i što je student pristupao samo malom dijelu knjiga u biblioteci.
Postoje dva tipa lokalnosti:

• vremenska lokalnost govori da, ako je neki podatak referenciran, velika je vjerovat-
noća da će uskoro biti referenciran ponovo. Analogno tome, ako student donese kn-
jigu na sto da bi pronašao neki podatak, velika je vjerovatnoća da će mu ta knjiga
ponovo trebati.
• prostorna lokalnost govori da će podaci čije su adrese blizu podatka koje je up-
ravo referenciran biti uskoro referencirani sa velikom vjerovatnoćom. U primjeru sa
studentom je ovo tačno jer biblioteke stavljaju knjige iste tematike na jednu policu,
upravo kako bi iskoristile prostornu lokalnost.

Kako bi se lokalnost maksimalno iskoristila, memorija se realizuje kao memorijska

hijerarhija, koja se sastoji od više nivoa memorije različitih kapaciteta i brzina. Brže
memorije su skuplje i manjeg kapaciteta, i obrnuto, sporije memorije su jeftinije i većeg
kapaciteta. Slika 1.3 prikazuje način konstrukcije memorijske hijerarhije, tako da su brže
memorije bliže procesoru.

Slika 1.3: Memorijska hijerarhija

12
 Na ovaj način korisnik, odnosno programer, ima iluziju memorije kapaciteta najvećeg
nivoa u hijerarhiji, kojoj se može pristupiti brzinom najbrže memorije u hijerarhiji.

1.3.1 Keš memorija

U primjeru sa studentom, sto na kojem su knjige služi kao tzv. keš (eng. cache 9 ). Keš je
naziv za memoriju koja se nalazi između procesora i RAM-a10 i služi kao bafer u kojem se
čuvaju skoro referencirani podaci ili podaci koji imaju veliku vjerovatnoću referenciranja
u budućnosti. Keš memorija je nastala šezdesetih godina, te se koristi i danas u svim
modernim procesorima. Keš predstavlja jedan od pokušaja da se prevaziđe razlika u
performansama procesora i memorije11 . S obzirom na to da je brzina rasta frekvencije
procesora tokom godina mnogo veća od brzine razvoja memorijskih sistema, pojavljuje
se znatna razlika u performansama ova dva sistema, koja na kraju utiče na smanjenje
ukupnih performansi računara. Kao i kod svih kompleksnih sistema, performanse definiše
najslabija karika u lancu, te je razvoj samo jednog dijela cijelog sistema uzaludan ako
ostatak sistema ne može da prati taj razvoj.
Keš memorija je podijeljena u nivoe. Za današnje računare je tipično postojanje tri
nivoa keš memorije, tj. L1, L2 i L3 keš. L1 keš je podijeljen na L1D i L1I keš, za podatke
i instrukcije, respektivno. Na slici 1.4 je prikazano na koji način se keš memorija uklapa
u memorijsku hijerarhiju u personalnom računaru (ovo ne važi za mobilne uređaje, jer
oni nemaju L3 keš). Takođe su prikazane i veličine i brzine pristupa pojedinim vrstama
memorije.

Slika 1.4: Keš memorija u memorijskoj hijerarhiji

Činjenica da se referencirani podatak nalazi u keš memoriji se označava kao keš pogodak
(eng. cache hit). U suprotnom, dešava se keš promašaj (eng. cache miss). Logično, cilj
je smanjiti broj promašaja na što manju vrijednost, jer što više referenciranih podataka
procesor može naći u keš memoriji, to će manje vremena potrošiti na dostavljanje tog
9
Od francuske riječi cacher - sakriti
10
RAM (eng. Random Access Memory je memorija kod koje je vrijeme pristupa bilo kojoj adresi isto.
Koristi se i naziv glavna memorija. Postavlja se pitanje zašto se cijela memorija računara ne realizuje
kao RAM. Sa jedne strane, RAM je volatile tip memorije, što znači da gubi svoj sadržaj prestankom
napajanja, te je stoga neupotrebljiv za stalno, permanentno čuvanje podataka. Sa druge strane, RAM
ne može zamijeniti keš memoriju, s obzirom da se realizuje u DRAM tehnologiji, koja je daleko sporija
od SRAM tehnologije, kojom se realizuje keš.
11
Razlike u brzinama memorije i procesora su u računarskoj terminologiji nazvane memory bottleneck.
Ovaj pojam je u računarstvu prisutan još od nastanka fon Nojmanove arhitekture.

13
podatka, s obzirom da su sve vrste memorije koje su u hijerarhiji niže od keš memorije
mnogo sporije. Dakle, prilikom čitanja ili upisa na neku adresu u glavnoj memoriji, proce-
sor provjerava da li se podatak sa te lokacije već nalazi u kešu. Ako je to slučaj, u pitanju je
pogodak, te procesor čita ili upisuje podatak u keš, a ne u mnogo sporiju glavnu memoriju.

Prenos podataka između keš i RAM memorije se realizuje u blokovima fiksne dužine,
koji se nazivaju keš linije ili keš blokovi. Kada se jedna keš linija prekopira iz RAM-a
u keš, kreira se keš unos (eng. cache entry), koji sadrži podatak i tag, tj. adresu tog
podatka u RAM-u. Ukoliko se desi promašaj prilikom referenciranja nekog podatka, tj.
ako se taj podatak ne nalazi u keš memoriji, on će se kopirati iz RAM-a u keš memoriju.
Istovremeno je potrebno i brisanje nekog bloka, ako je keš popunjen. Izbor bloka koji
se briše je problem koji se rješava heurističkim metodama, te ne postoji jedna ispravna
tehnika. Najčešće se koristi tzv. LRU (eng. Least Recently Used ) tehnika, po kojoj se za
brisanje bira blok koji je najrjeđe referenciran.
Prilikom upisa podatka u keš, neophodno je obezbijediti mehanizam koji će u određenom
trenutku da kopira upisani podatak nazad u RAM. Postoje dvije tehnike, tj. dvije vrste
keš memorije u pogledu načina ažuriranja podataka u glavnoj memoriji:

1. write-through keš, kod kojeg svaki upis inicira kopiranje u RAM, tj. odmah nakon
upisa u keš, taj podatak se kopira u RAM.
2. write-back keš, kod kojeg se kopiranje podatka u RAM ne dešava odmah nakon
upisa u keš. Ažuriranje RAM-a, tj. kopiranje podatka iz keša se dešava tek onda
kada je datu keš liniju potrebno izbaciti iz keš memorije.

Osim toga, prilikom upisa bloka neki tipovi keš memorije postavljaju restrikcije u smislu
dozvoljenih lokacija na koje se taj blok može sačuvati u kešu. U ovom kontekstu razliku-
jemo tri vrste keš memorije:

1. direktno mapirani keš određeni blok može sačuvati samo na jednu lokaciju, određenu
kao ostatak pri dijeljenju adrese bloka sa brojem mjesta u kešu, što znači da se više
adresa mapira na jednu lokaciju u keš memoriji.
2. potpuno asocijativan keš može sačuvati blok na bilo kojoj lokaciji u kešu.
3. grupno asocijativan keš (eng. set associative) određeni blok može sačuvati na neko-
liko lokacija, određenih kao ostatak pri dijeljenju adrese bloka i broja grupa u kešu.
Broj lokacija na koje se podatak može sačuvati je parametar keš memorije. Ako se
jedan podatak može sačuvati na N lokacija, onda se kaže da je keš memorija N -way
asocijativna.

Slika 1.5 prikazuje asocijativnost keš memorije. Blok sa adresom 12 se iz RAM-a

smješta u keš memoriju. Kod direktno mapiranog keša, blok 12 se može smjestiti samo na
lokaciju 4, jer je 12 mod 8 = 4. Kog grupno asocijativnog keša, blok 12 se može smjestiti
na bilo koju lokaciju unutar grupe 0, jer je 12 mod 4 = 0. Potpuno asocijativan keš može
smjestiti blok na bilo koju lokaciju.

14
Slika 1.5: Asocijativnost keš memorije

15
Poglavlje 2

RISC-V instrukcijski set

Jedan relativno nov instrukcijski set, koji je pogodan za demonstraciju osnovnih, ali i
naprednih koncepata arhitekture računara je RISC-V1 instrukcijski set. Nastao je na
Berkliju 2010. godine, kao proizvod potrebe i inicijative da se dođe do arhitekture koja bi
studentima i profesorima koristila u nastavi na predmetima vezanim za arhitekturu raču-
nara. Autori ove arhitekture su, između ostalih, i David Patterson i Krste Asanović. Jedna
od glavnih karakteristika je jednostavnost. Prilikom dizajna su u obzir uzeta iskustva i
dobre strane prethodnih RISC arhitektura, te su ispravljene greške uočene u tim arhitek-
turama. Uprkos tome, RISC-V je uporedivih performansi sa ostalim modernim arhitektu-
rama, u pogledu efikasnosti, potrošnje i gustine kôda2 . Arhitektura je otvorenog kôda (eng.
open-source), što je doprinijelo ubrzanom prihvatanju ove arhitekture i van obrazovnih
institucija, u industriji. Činjenica da nije potrebno plaćati licence za korištenje (odnosno,
kaže se da je RISC-V royalty free) igra veoma bitnu ulogu u ovladavanju tržištem.

2.1 Organizacija instrukcijskog seta

RISC-V instrukcijski set ima nekoliko podskupova, koji se međusobno razlikuju po obimu,
tj. broju instrukcija, te mogućnostima. To omogućava da se ne implementira cijeli set
instrukcija, već samo dio koji je neophodan za ciljne aplikacije datog procesora.
Nomenklatura različitih RISC-V podskupova ima sljedeći bazirana je na formatu
RVNE, gdje N specifikuje širinu adresnog prostora i može biti 32, 64 ili 128, dok E
predstavlja ekstenziju datog podskupa, koja mu bliže određuje mogućnosti.
Postoji 4 osnovna skupa instrukcija:

• RV32I
• RV32E
• RV64I
• RV128I

RV32I je 32-bitni ISA sa cjelobrojnim operacijama. RV32E je redukovana verzija RV32I,

namijenjena ugrađenim sistemima, koja ima 16 umjesto 32 registra.

1
RISC-V (eng. Reduced Instruction Set Computer - V ), izgovara se kao „risk fajv" - „V" u imenu
predstavlja broj pet, kao petu iteraciju RISC arhitekture.
2
Gustina kôda predstavlja količinu memorije koju program zauzima, tj. koliko instrukcija je potrebno
da se izvrši određena operacija.

16
 Osim osnovnog skupa, standardom su definisane i ekstenzije:

• M: matematičke instrukcije
• A: atomične operacije
• F: operacije u pokretnom zarezu
• D: operacije u pokretnom zarezu, dvostruke preciznosti

Osim toga, postoji i G (General purpose) ekstenzija, koja nije nova ekstenzija, već pred-
stavlja sve prethodne ekstenzije zajedno, tako da je RV64G isto što i RV64IMAFD3 .
U nastavku ovog teksta biće govora o RV32I podskupu. RV32I predstavlja 32-bitni cjelo-
brojni ISA. Definisana su 32 registra, od x0 do x31, pri čemu je x0 uvijek 04 , što ostavlja 31
registar, širine 32 bita, za čuvanje varijabli. Osim ovih, programeru je vidljiv i programski
brojač.

3
Linux operativni sistem za uspješno butanje zahtijeva da procesor implementira RV64G odnosno
RV64IMAFD.
4
Ispostavlja se da ovo pojednostavljuje pojedine instrukcije.

17
Poglavlje 3

Chisel jezik za opis hardvera

Jezgra koja se razmatraju u ovom tekstu su realizovana pomoću Chisel jezika za opis hard-
vera. U pitanju je jezik otvorenog kôda zasnovan na Scala1 programskom jeziku. Chisel
se koristi za opis digitalnih kola na RTL (eng. Register-transfer level ) nivou apstrakcije.
Razlika između Chisel-a i ostalih jezika za opis hardvera je u tome što Chisel preuzima sve
dobre strane Scala programskog jezika, kao što su objektno-orjentisana paradigma, inter-
fejsi, parametrizacija i slično. Još jedna razlika je u tome što Chisel kôd ne ulazi direktno
u sintetizator, već se pretvara u Verilog, koji se onda može sintetizovati ili proslijediti
nekom simulatoru. Motivacija iza nastanka Chisel jezika je težnja da se podigne nivo ap-
strakcije digitalnog dizajna, kako bi bio dostupan većem broju ljudi. Kao i jezgra koja će
se razmatrati kasnije, i Chisel je nastao na Berkliju, te se postepeno prihvata i u industriji.

Chisel projekat sadrži Scala izvorni kod i build.sbt fajl kojim se definišu verzije
kompajlera, jezika, te se specifikuju dodaci specifični Chisel jeziku koje će pokupiti Scala
kompajler. Za kompajliranje se uobičajeno koristi sbt. Osnova Chisel projekta data
je na adresi https://github.com/freechipsproject/chisel-template. Način rada koji će se
koristiti u ovom tekstu je takav da se Chisel kôd pretvara u Verilog, koji se zajedno sa C++
testovima prosljeđuje simulatoru pod nazivom Verilator. Verilator je softver otvorenog
kôda koji Verilog pretvara u C++ model koji je moguće testirati.

1
Scala je programski jezik veoma sličan Javi, s tim što podržava i objektno-orjentisano i funkcionalno
programiranje. Scala je primarno nastala kao baza za domenski specifične jezike, kakav je upravo Chisel.

18
Poglavlje 4

Sodor

U ovom poglavlju se razmatraju Sodor RISC-V jezgra. Sodor je skup procesorskih jez-
gara koje demonstriraju koncepte protočne obrade pomoću RISC-V instrukcijskog seta.
Jezgra su implementirana u Chisel jeziku za opis hardvera. Osim implementacije jezgara,
dostupni su i benchmark 1 programi koji daju uvid u performanse procesora, te skripte za
analizu izlaznih fajlova, kako bi se došlo do dubljeg uvida u instrukcije pojedinih bench-
mark -a.

Sodor je projekat koji je uključen u Chipyard frejmvork kao podmodul, te se do

izvornih fajlova može doći iz preko Chipyard -a.

4.1 Chipyard
Chipyard je skup alata koji služe za dizajn i evaluaciju sistema na čipu (eng. SoC ).
S obzirom da je instalacija i podešavanje zamoran posao sklon greškama, od velikog je
značaja imati već podešen frejmvork koji bi pružio sve neophodne open-source alate koji
se koriste prilikom dizajna i testiranja čipova. Chipyard upravo to i donosi. Na ovaj način
je moguće doći do alata za kros-kompajliranje, simulaciju i verifikaciju bez potrebe da se
oni pojedinačno instaliraju i konfigurišu. S obzirom na to, Chipyard je defakto standard
u oblasti rada na razvoju sistema na čipu baziranih na RISC-V instrukcijskom setu.

4.1.1 Instalacija i konfiguracija

Budući da se radi o open-source projektu, instalacija se vrši kloniranjem odgovarajućeg
repozitorijuma.

git clone https://github.com/ucb-bar/chipyard.git

Nakon toga, potrebno je instalirati i odgovarajuće pakete od kojih zavisi Chipyard fre-
jmvork. Najjednostavnije je kopirati Listing 4.1 u .sh fajl i izvršiti tu skriptu.

1
Najbliži prevod bi bio „reper". Benchmark je, u ovom kontekstu, program koji služi kao uporedno
mjerilo performansi različith procesora. Takođe, ovaj program treba da oslikava neki tip aplikacija, kako
bi se znalo ponašanje procesora u slučaju izvršavanja aplikacija tog tipa.

19
1 # !/ bin / bash
2
3 set - ex
4
5 sudo apt - get install -y build - essential bison flex
6 sudo apt - get install -y libgmp - dev libmpfr - dev libmpc - dev zlib1g - dev vim
git default - jdk default - jre
7 # install sbt : https :// www . scala - sbt . org / release / docs / Installing - sbt - on -
Linux . html
8 echo " deb https :// dl . bintray . com / sbt / debian / " | sudo tee -a / etc / apt /
sources . list . d / sbt . list
9 curl - sL " https :// keyserver . ubuntu . com / pks / lookup ? op = get & search =0
x 2 E E 0 E A 6 4 E 4 0 A 8 9 B 8 4 B 2 D F 7 3 4 9 9 E 8 2 A 7 5 6 4 2 A C 8 2 3 " | sudo apt - key add
10 sudo apt - get update
11 sudo apt - get install -y sbt
12 sudo apt - get install -y texinfo gengetopt
13 sudo apt - get install -y libexpat1 - dev libusb - dev libncurses5 - dev cmake
14 # deps for poky
15 sudo apt - get install -y python3 .6 patch diffstat texi2html texinfo
subversion chrpath git wget
16 # deps for qemu
17 sudo apt - get install -y libgtk -3 - dev gettext
18 # deps for firemarshal
19 sudo apt - get install -y python3 - pip python3 .6 - dev rsync libguestfs - tools
expat ctags
20 # install DTC
21 sudo apt - get install -y device - tree - compiler
22
23 # install verilator
24 git clone http :// git . veripool . org / git / verilator
25 cd verilator
26 git checkout v4 .034
27 autoconf && ./ configure && make - j$ ( nproc ) && sudo make install
Listing 4.1: Skripta za instalaciju paketa
Ovako kloniran repozitorijum još uvijek ne sadrži Sodor jezgra. Potrebno je izvršiti skriptu
koja će klonirati i Sodor repozitorijum.

./scripts/init-submodules-no-riscv-tools.sh

Sada su sva Sodor jezgra dostupna na sljedećoj relativnoj putanji:

/chipyard/generators/riscv-sodor/src/main/scala

Unutar ovog direktorijuma nalazi se pet Sodor jezgara:

rv32_1stage
rv32_2stage
rv32_3stage
rv32_5stage
rv32_ucode

Sva jezgra implementiraju osnovni RISC-V instrukcijski set RV32I.

20
 Osim izvornog koda jezgara, potrebni su i gorepomenuti alati za kros-kompajliranje2
programa. Za instalaciju ovih alata potrebno je izvršiti sljedeću komandu, prethodno se
pozicionirajući u Chipyard direktorijum:

./scripts/build-toolchains.sh riscv-tools

Pokretanjem ove komande, počinje kloniranje nekoliko repozitorijuma koji sadrže različite
RISC-V alate, a izvršavanje može trajati duže od 20 minuta. Nakon ove komande, a i na
početku svake sesije rada sa Chipyard -om, potrebno je poktrenuti sljedeću komandu, radi
dodavanja alata u $PATH varijablu:

source ./env.sh

Opciono, radi lakšeg pristupa benchmark programima i skriptama, moguće je izvršiti

sljedeće komande u Chipyard direktorijumu:

BMARKS=$PWD/generators/riscv-sodor/riscv-bmarks
SCRIPTS=$PWD/generators/riscv-sodor/scripts

4.2 Simulacija na Sodor jezgrima

Prije same simulacije programa na jezgrima, jezgra je potrebno kompajlirati. Za kom-
pajliranje najjednostavnijeg Sodor jezgra (rv32_1stage), potrebno je pokrenuti sljedeću
komandu:

cd sims/verilator
make CONFIG=Sodor1StageConfig

Prilikom pokretanja ove komande, moguće je da će se desiti greška u vezi sa maksimal-

nom RAM memorijom dodijaljenoj Java virtuelnoj mašini. Obično je podrazumijevana
vrijednost 1 do 2GB, što nije dovoljno. Ovaj podatak je moguće provjeriti na sljedeći
način:

java -XshowSettings:vm

Verifikovano je da komanda prolazi sa 4GB, pa je za dodjelu memorije JVM-u potrebno

izvršiti sljedeće:

sudo nano /etc/profile

Na početak fajla dodati sljedeću liniju:

export _JAVA_OPTIONS=-Xmx4096m

Nakon toga, odjaviti se sa korisničkog naloga (eng. logout), te se ponovo prijaviti.

Kako je ovo prvi poziv make komande, očekivano je da izvršavanje traje duže od 10
minuta. Ova komanda radi sljedeće ključne stvari:
2
Pojam kros-kompajliranje se odnosi na proces kompajliranja programa za neku drugu platformu ili
arhitekturu. To znači da se kompajliranje vrši na, recimo, x86 mašini, ali se generiše izvršni fajl za neku
drugu arhitekturu, recimo ARM ili RISC-V. Kros-kompajliranje je potpuno suprotan pojam od nativnog
kompajliranja (eng. native), koje predstavlja kompajliranje i izvršavanje na mašini iste arhitekture.

21
 • Pokreće sbt (Scala Build Tool ), kompajlira i pokreće Chisel kod koji generiše Verilog
opis procesora. Ovaj opis se može naći na putanji:

/sims/verilator/generated-src

• Pokreće Verilator, koji Verilog opis pretvara u C++ simulacioni model.

• Kompajlira prethodno generisani C++ u x86 izvršni fajl.

Sada je moguće izvršavanje benchmark programa na ovom procesoru. Pokretanjem

sljedeće komande, Towers of Hanoi benchmark se pokreće na rv32_1stage procesoru.

cd sims/verilator
make CONFIG=Sodor1StageConfig run-binary BINARY=${BMARKS}/towers.riscv

Očekivano je da se na kraju izvršavanja dobije ispis ukupnog broja ciklusa (mcycle) i

broja instrukcija (minstret).
Na isti način se pokreću i ostali benchmark programi.

make CONFIG=Sodor1StageConfig run-binary BINARY=${BMARKS}/towers.riscv

make CONFIG=Sodor1StageConfig run-binary BINARY=${BMARKS}/dhrystone.riscv
make CONFIG=Sodor1StageConfig run-binary BINARY=${BMARKS}/multiply.riscv
make CONFIG=Sodor1StageConfig run-binary BINARY=${BMARKS}/median.riscv
make CONFIG=Sodor1StageConfig run-binary BINARY=${BMARKS}/qsort.riscv
make CONFIG=Sodor1StageConfig run-binary BINARY=${BMARKS}/rsort.riscv
make CONFIG=Sodor1StageConfig run-binary BINARY=${BMARKS}/vvadd.riscv

Kao izlaz iz svake od prethodno pokrenutih komandi, generišu se .out fajlovi, na

sljedećoj putanji:

sims/verilator/output/chipyard.TestHarness.Sodor1StageConfig

Ovi fajlovi sadrže detaljan opis stanja procesora tokom izvršavanja benchmark programa.
Tako je moguće doći do informacije koja instrukcija se izvršila u kojem ciklusu, koje je
stanje PC registra i slično.
Ukoliko je potrebno simulirati na nekom drugom procesoru, prvo se ponavlja make ko-
manda sa odgovarajućim config fajlom, pa se onda programi simuliraju kao i na rv32_1stage
procesoru.

4.2.1 Ispitivanje raspodjele tipova instrukcija pomoću jednoste-

penog procesora
Kod pisanja benchmark programa, veoma su bitni tipovi korišćenih instrukcija (eng. in-
struction mix ). Pojam instruction mix se odnosi na „mješavinu" tipova instrukcija u
programu. S obzirom da benchmark program treba da reflektuje neki tip aplikacije (npr.
biznis aplikacije, obrada videa itd.), bitno je da odnos I/O instrukcija i instrukcija koje
manipulišu podacima bude odgovarajući datoj aplikaciji. Cilj ovog dijela jeste da se ispi-
taju ovi odnosi u dostupnim benchmark programima.
Kako bi se došlo do informacija o izvršavanju programa, svi benchmark programi se
moraju pokrenuti na jednostepenom Sodor jezgru, radi dobijanja .out fajlova.
Kako je već pomenuto, .out fajlovi sadrže stanja procesora po ciklusima tokom izvrša-
vanja programa, uključujući i instrukciju koja se izvršava u datom ciklusu. Da bi se došlo

22
do informacije koji procenat programa čine pojedini tipovi instrukcija, bilo bi potrebno
izbrojati sve instrukcije datog tipa, pa ih podijeliti sa ukupnim brojem instrukcija, te
ponoviti ovaj postupak za svaki tip. Ovaj proces je automatizovan Python skriptom
datoj na putanji:
${SCRIPTS}/tracer.py
Skripta parsira izlazne fajlove i daje osnovnu statistiku za benchmark programe.
Pokretanje se vrši na sljedeći način:
cd sims/verilator/output/chipyard.TestHarness.Sodor1StageConfig
${SCRIPTS}/tracer.py rsort.out
Ovom komandom je tracer.py skripti proslijeđen rezultat izvršavanja rsort.riscv pro-
grama na jednostepenom Sodor procesoru. Očekivani izlaz u ovom slučaju je:

Stats:

CPI : 1.000
IPC : 1.000
Cycles : 374745
Instructions : 374746
Bubbles : 0

Instruction Breakdown:
% Arithmetic : 59.627 %
% Ld/St : 34.855 %
% Branch/Jump : 4.364 %
% Misc. : 1.154 %

Potrebno je isti postupak ponoviti za sve benchmark programe i uočiti raspodjele

instrukcija. To podrazumijeva identifikaciju programa koji imaju najveći broj aritmetičkih
instrukcija, zatim programa koji su usko vezani sa memorijom, kao i onih koji najviše
zavise od performansi prediktora grananja.

4.2.2 Ispitivanje CPI pomoću jednostepenog procesora

Kada su prikupljeni rezultati ispitivanja raspodjele instrukcija za pojedine benchmark pro-
grame, moguće je ispitati na koji način bi potencijalne izmjene dizajna uticale na ukupan
CPI, tj. na performanse procesora u pojedinim tipovima aplikacija.

Pretpostavimo da je potrebno dizajnirati novu mašinu koja ima prosječan CPI za

load i store instrukcije jednak 2 ciklusa, za aritmetičke instrukcije 1 ciklus, te za ostale
instrukcije prosječno 1.5 ciklusa. Potrebno je odrediti ukupan CPI ove mašine za svaki
benchmark, kao i poboljšanje koje bi se dobilo ako se prosječan CPI za load i store in-
strukcije smanji na 1.

Prvo se za svaki benchmark računa CPI, ako se uvedu prethodno navedene izmjene.

1. vvadd
Statistika za ovaj benchmark, dobijena u prethodnoj tački je:

23
CPI : 1.000
IPC : 1.000
Cycles : 12413
Instructions : 12414
Bubbles : 0

Instruction Breakdown:
% Arithmetic : 46.858 %
% Ld/St : 29.861 %
% Branch/Jump : 22.152 %
% Misc. : 1.128 %
Informacije koje su od interesa su relativne frekvencije (procenti) instrukcija u programu.
Po ugledu na primjer 1 iz poglavlja 1.2.1, te prema jednačini (1.3), ukupan CPI se računa
na sljedeći način:
n
X ICi
CP Ivvadd = CP Ii × ( )
broj instrukcija
i=1
(4.1)
= (2 × 29.861%) + (1 × 46.858%) + (1.5 × 23.281%)
= 1.415
Ukoliko bi se prosječni CPI za load i store instrukcije smanjio na 1, relativno ubrzanje bi
bilo:
CP Ivvadd
U brzanje =
CP Ivvadd,2
1.415 (4.2)
=
1.15
= 1.23
gdje je CP Ivvadd,2 novi CPI dobijen na isti način kao i CP Ivvadd .

Na isti način se postupa i za sve ostale programe.

2. multiply

CPI : 1.000
IPC : 1.000
Cycles : 50091
Instructions : 50092
Bubbles : 0

Instruction Breakdown:
% Arithmetic : 63.571 %
% Ld/St : 4.444 %
% Branch/Jump : 31.634 %
% Misc. : 0.351 %
CP Imultiply = 1.2

3. median

24
CPI : 1.000
IPC : 1.000
Cycles : 16706
Instructions : 16707
Bubbles : 0

Instruction Breakdown:
% Arithmetic : 32.088 %
% Ld/St : 31.753 %
% Branch/Jump : 35.321 %
% Misc. : 0.838 %

CP Imedian = 1.5

4. qsort

CPI : 1.000
IPC : 1.000
Cycles : 236101
Instructions : 236102
Bubbles : 0

Instruction Breakdown:
% Arithmetic : 38.415 %
% Ld/St : 31.438 %
% Branch/Jump : 29.825 %
% Misc. : 0.323 %

CP Iqsort = 1.47

5. rsort

CPI : 1.000
IPC : 1.000
Cycles : 374745
Instructions : 374746
Bubbles : 0

Instruction Breakdown:
% Arithmetic : 59.627 %
% Ld/St : 34.855 %
% Branch/Jump : 4.364 %
% Misc. : 1.154 %

CP Irsort = 1.38

6. towers

CPI : 1.000
IPC : 1.000

25
Cycles : 19091
Instructions : 19092
Bubbles : 0

Instruction Breakdown:
% Arithmetic : 42.201 %
% Ld/St : 42.070 %
% Branch/Jump : 14.996 %
% Misc. : 0.733 %

CP Itowers = 1.5

7. dhrystone

CPI : 1.000
IPC : 1.000
Cycles : 244155
Instructions : 244156
Bubbles : 0

Instruction Breakdown:
% Arithmetic : 40.482 %
% Ld/St : 35.236 %
% Branch/Jump : 23.738 %
% Misc. : 0.545 %

CP Idhrystone = 1.47

4.2.3 Ispitivanje CPI pomoću petostepenog procesora

Ovaj dio za cilj ima proučavanje efekata grananja i tehnike prosljeđivanja (eng. forwarding
ili bypassing) u petostepenom Sodor jezgru (rv32_5stage). Ovo jezgro je parametrizovano
tako da je moguće uključiti ili isključiti prosljeđivanje, što omogućava ispitivanje uticaja
ove tehnike na performanse procesora.
Prvo je potrebno u kodu verifikovati da li je prosljeđivanje omogućeno, što je moguće
provjeriti na sljedeći način:

cd generators/riscv-sodor/src/main/scala/rv32_5stage
nano consts.scala

Na 21. liniji nalazi se sljedeća konstanta:

val USE_FULL_BYPASSING = true

Na koji način ovaj parametar utiče na procesor moguće je vidjeti u implementacijama

data path-a i control path-a u fajlovima dpath.scala (linije 269 do 301) i cpath.scala
(linije 226 do 245), respektivno. U cpath.scala, dio koda na koji utiče ovaj parametar
prikazan je na listingu 4.2.

26
1 // Stall signal stalls instruction fetch & decode stages ,
2 // inserts NOP into execute stage , and drains execute , memory , and
writeback stages
3 // stalls on I$ misses and on hazards
4 if ( U SE _FU LL _B YPA SS IN G )
5 {
6 // stall for load - use hazard
7 stall : = (( exe_inst_is_load ) && ( exe_reg_wbaddr = = = dec_rs1_addr ) && (
exe_reg_wbaddr = / = 0. U ) && dec_rs1_oen ) ||
8 (( exe_inst_is_load ) && ( exe_reg_wbaddr = = = dec_rs2_addr ) && (
exe_reg_wbaddr = / = 0. U ) && dec_rs2_oen ) ||
9 ( exe_reg_is_csr )
10 }
11 else
12 {
13 // stall for all hazards
14 stall : = (( exe_reg_wbaddr = = = dec_rs1_addr ) && ( dec_rs1_addr = / = 0. U )
&& e x e _r e g_ c t rl _ rf _ we n && dec_rs1_oen ) ||
15 (( mem_reg_wbaddr = = = dec_rs1_addr ) && ( dec_rs1_addr = / = 0. U )
&& m e m _r e g_ c t rl _ rf _ we n && dec_rs1_oen ) ||
16 (( wb_reg_wbaddr = = = dec_rs1_addr ) && ( dec_rs1_addr = / = 0. U )
&& wb _r eg _ct rl _r f_w en && dec_rs1_oen ) ||
17 (( exe_reg_wbaddr = = = dec_rs2_addr ) && ( dec_rs2_addr = / = 0. U )
&& e x e _r e g_ c t rl _ rf _ we n && dec_rs2_oen ) ||
18 (( mem_reg_wbaddr = = = dec_rs2_addr ) && ( dec_rs2_addr = / = 0. U )
&& m e m _r e g_ c t rl _ rf _ we n && dec_rs2_oen ) ||
19 (( wb_reg_wbaddr = = = dec_rs2_addr ) && ( dec_rs2_addr = / = 0. U )
&& wb _r eg _ct rl _r f_w en && dec_rs2_oen ) ||
20 (( exe_inst_is_load ) && ( exe_reg_wbaddr = = = dec_rs1_addr ) && (
exe_reg_wbaddr = / = 0. U ) && dec_rs1_oen ) ||
21 (( exe_inst_is_load ) && ( exe_reg_wbaddr = = = dec_rs2_addr ) && (
exe_reg_wbaddr = / = 0. U ) && dec_rs2_oen ) ||
22 (( exe_reg_is_csr ) )
23 }
Listing 4.2: Uticaj USE_FULL_BYPASSING na control path
U zavisnosti od toga da li je USE_FULL_BYPASSING omogućen, stall se aktivira
samo za hazard kod load instrukcije, odnosno za svaki tip hazarda.
Potrebno je testirati kako USE_FULL_BYPASSING parametar utiče na CPI. Kao
i kod jednostepenog procesora, potrebno je prvo kompajlirati procesor, te pokrenuti
svaki od benchmark programa na petostepenom procesoru. Korišćenjem Python skripte,
određuje se CPI za svaki od programa.
Nakon toga, isključuje se prosljeđivanje postavljanjem odgovarajuće konstante na false:
val USE_FULL_BYPASSING = false
Sada je potrebno ponovo kompajlirati procesor, te ponovo pokrenuti benchmark programe
i odrediti CPI za svaki, u cilju određivanja načina na koji tehnika prosljeđivanja utiče na
performanse procesora.

Prvo se kompajlira petostepeni procesor na sljedeći način:

cd sims/verilator
make CONFIG=Sodor5StageConfig
Kada je procesor kompajliran, moguće je izvršavanje benchmark programa na isti način
kao kod jednostepenog procesora, kao na primjer:

27
make CONFIG=Sodor5StageConfig run-binary BINARY=${BMARKS}/qsort.riscv

Zatim se qsort.out fajl analizira Python skriptom:

cd sims/verilator/output/chipyard.TestHarness.Sodor5StageConfig
${SCRIPTS}/tracer.py qsort.out

Dobijaju se sljedeći rezultati za CPI:

• dhrystone: 1.321
• qsort: 1.42
• rsort: 1.082
• median: 1.463
• multiply: 1.564
• towers: 1.242
• vvadd : 1.341

Sada se modifikuje USE_FULL_BYPASSING tako da bude isključen, pa se procesor

ponovo kompajlira, te se ponovo izvršava i analizira svaki benchmark. Sada se dobijaju
sljedeći rezultati za CPI:

• dhrystone: 1.984
• qsort: 1.935
• rsort: 2.323
• median: 1.878
• multiply: 1.907
• towers: 1.662
• vvadd : 1.832

Ovi podaci su vizuelizovani na slici 4.1. Sa ovog grafika je očigledno da prosljeđivanje

smanjuje CPI na svakom benchmark programu, tj. na svakom tipu aplikacije.

4.2.4 Procjena potencijalne modifikacije petostepenog procesora

U ovom dijelu je potrebno procijeniti potencijalnu modifikaciju petostepenog Sodor jezgra.
Naime, predložena je modifikacija da se Execution/effective address faza i Memory Access
faza spoje u jedan stepen. U ovom kombinovanom stepenu, ALU i memorija funkcionišu
paralelno. Instrukcije koje pristupaju podacima će koristiti memoriju, te ostaviti ALU
neaktivnim, dok će aritmetičke instrukcije koristiti ALU, te ostaviti memoriju neaktivnom.

RISC-V instrukcijski set predviđa da se efektivna adresa load i store instrukcija računa
sabirajući vrijednost u rs1 registru sa neposrednom vrijednošću(imm). Problem koji se
javlja ako se uvede predložena modifikacija jeste da se sada ne može vršiti izračuna-
vanje efektivne adrese, s obzirom da load i store instrukcije ne mogu dobiti pristup ALU.
S obzirom na to, postoji samo jedan tip adresiranja: direktno registarsko adresiranje.
Dakle, koristi se samo jedan registar koji sadrži adresu, te nije moguće specifikovati ofset.

28
 Slika 4.1: Uticaj prosljeđivanja na CPI

To dalje znači da imm vrijednost mora biti jednaka nuli. U novom dizajnu, svaka instruk-
cija kojoj je imm različit od nule bi zapravo zahtijevala dvije instrukcije: prvo sabiranje
rs1 registra sa imm vrijednošću, te nakon toga pristup izračunatoj adresi. Na instrukcije
koje imaju imm = 0 modifikacija ne bi imala efekta.

Potrebno je, pomoću dostupnih benchmark programa, odrediti procentualno povećanje

broja instrukcija koje bi se morale izvršiti u novom dizajnu. Za postizanje ovog cilja,
potrebno je modifikovati Python skriptu za analizu benchmark programa, tracer.py, tako
da bude u stanju da odredi procenat load i store instrukcija sa nenultim ofsetom. Nakon
toga, analizirati sve dostupne programe, te odrediti koliko je povećanje broja instrukcija
ako bi se koristio novi dizajn. Na osnovu dobijenih podataka, procijeniti da li i u kojim
slučajevima bi predložena modifikacija imala smisla.

4.2.5 Zadatak
Popuniti tabelu 1 sa „povećava se", „smanjuje se" ili „ostaje isto", te navesti razloge
odgovora.

29
Tabela 1. Ocjena potencijalnih modifikacija
Modifikacija Broj CPI Ukupne
instrukcija performanse
Dodavanje
kompleksne
instrukcije
Smanjenje
broja registara
Povećanje
brzine pristupa
memoriji
Dodavanje
16-bitnih
verzija
najčešćih
instrukcija

30
Poglavlje 5

Rocket Chip

Cilj ovog poglavlja jeste izučavanje memorijske hijerarhije procesora pomoću eksperi-
menata na RISC-V jezgru pod nazivom Rocket. Za razliku od Sodor jezgara, podskup
realizovanih instrukcija je RV64IMAFDC, pa su Rocket jezgra sposobna za butanje Linux
operativnog sistema.

Kako bi se zapravo generisao cijeli sistem, uključujući memoriju i procesor i magistrale

koje ih povezuju, koristi se Rocket Chip. Rocket Chip je SoC generator razvijen na Berkliju.
To je skup alata koji služe kao generatori parametrizvanih jezgara, keš memorije i sistema
za njihovo povezivanje. Rocket Chip sistem generiše RTL koji je moguće sintetizovati.
Činjenica da je Rocket Chip moguće proizvoljno parametrizovati doprinijela je upotrebi
ovog alata u industriji.

5.1 Struktura
Dijagram Rocket Chip sistema je prikazan na slici 5.1. Prikazana je osnovna konfigu-
racija, koju je moguće proizvoljno izmijeniti. Osnovna jedinica Rocket Chip sistema je
tzv. tile, tj. pločica. Jednu pločicu čine procesorsko jezgro1 , PWT (eng. Page Table
Walker ), L1 instrukcijski keš, L1 keš podataka i interfejs kojim se pločica povezuje sa
sistemskom magistralom. Na prikazanom dijagramu se nalaze dvije pločice, što znači da
je u pitanju dvojezgarni Rocket sistem. Osim pločica, Rocket Chip sistem čine i sistemska
magistrala, L2 keš, kontrolna magistrala i nekoloko konvertera koji služe za povezivanje
sa drugim sistemima koji komuniciraju preko AXI protokola, što nije u fokusu ovog teksta.

Procesorsko jezgro koje se koristi je Rocket jezgro, napisano u Chisel programskom

jeziku inicijalno razvojeno na Berkliju. U pitanju je petostepeni procesor, adaptiran
za ASIC upotrebu, te se stoga u određenim segmentima razlikuje od klasičnog petoste-
penog procesora, kakav je recimo petostepeni Sodor procesor, razmatran u prethodnom
poglavlju. Trenutno Rocket jezgro podržava kompanija SiFive, a veliki broj kompanija iz
oblasti projektovanja mikroprocesora, akceleratora i slično koristi Rocket kao osnovu za
svoje sisteme.

Svaka Rocket pločica sadrži L1D i L1I keš. Veličina i asocijativnost se mogu proizvoljno
parametrizovati. Rocket Chip sistem koristi L2 keš generator kompanije SiFive, te ga je
1
U ovom slučaju Rocket, ali može biti i BOOM. Rocket Chip je ime dobio po Rocket jezgru koje
uobičajeno koristi.

31
 Slika 5.1: Tipičan Rocket Chip sistem

takođe moguće proizvoljno parametrizovati. Jezgra dijele L2 keš.

5.2 Pripremanje potrebnih datoteka

Fajlovi potrebni za eksperimente se nalaze u Chipyard direktorijumu, koji je već kloniran.
Sljedećom komandom se može privjeriti trenutno aktivna grana:

git branch -a

Aktivna grana će biti označena zelenom bojom. Ukoliko nije već aktivna, potrebno je
prebaciti se na cs152-sp21-lab2 granu, pomoću sljedeće komande:

git checkout cs152-sp21-lab2

32
Ukoliko se pojavi greška sljedećeg ili sličnog sadržaja:
error: Your local changes to the following files would be overwritten by
checkout:
sims/verilator/Makefile
Please commit your changes or stash them before you switch branches.
Aborting
potrebno je izvršiti sljedeću komandu2 :

git reset --hard

Nakon ovoga je moguće prebaciti se na odgovarajuću granu, koja sadrži folder lab/directed,
unutar kojeg su testni program transpose.c, te Makefile za njegovo kompajliranje. Radi
lakšeg referenciranja ovog programa, može se izvršiti sljedeća komanda:

export T_DIR=$PWD/lab/directed

Nakon toga je potrebno izvršiti skriptu koja instalira odgovarajuće alate za kompajliranje
Scala projekata:

./scripts/init-submodules-no-riscv-tools.sh

Ova skripta se izvršava nakon svakog prelaska na novu granu.

5.3 Simulacija na Rocket jezgrima

Parametrizovanje memorijske hijerarhije vrši se kroz Scala-bazirane konfiguracione fajlove,
koji se prosljeđuju Rocket Chip generatoru prilikom kompajliranja. Konfiguracioni fajlovi
se mogu naći na sljedećoj putanji:

/chipyard/generators/chipyard/src/main/scala/config

U okviru ovog teksta se koristi konfiguracioni fajl pod nazivom CS152Configs.scala

koji definiše nekoliko konfiguracija. Eksperimentisanje sa memorijskom hijerarhijom će
se testirati pomoću programa koji vrši operaciju transponovanja matrice, a koji je imple-
mentiran u pomenutom transpose.c fajlu. U pitanju je neefikasna implementacija for
petljama koja direktno slijedi iz matematičke definicije. Matrica koja se transponuje je
dimenzija 256x64, te se u memoriji čuva tako da su svi brojevi koji pripadaju istom redu
susjedni(eng. row-major ). Izlazna matrica se čuva na isti način.
Program se kompajlira na sljedeći način:

cd lab/directed
make

Na ovaj način se u trenutnom direktorijumu kreiraju izvršni fajl, sa ekstenzijom .riscv i

.dump fajl. Nakon toga, generiše se simulator izvršavanjem sljedećih komandi:

cd sims/verilator
make CONFIG=CS152RocketConfig -j4
2
Dobra praksa je i da se nakon završetka rada izvrši ova komanda i vrati na master granu, naročito
ako se radi u okruženju koje koristi više studenata.

33
 Moguće je make izvršiti i bez -j4, koji se koristi da bi se pokrenulo više komandi istovre-
meno na višeprocesorskim sistemima.
Konfiguracija CS152RocketConfig je definisana u CS152Configs.scala fajlu na sljedeći
način:
1 class CS 152Rocket Config extends Config (
2 new WithL1ICacheSets (64) ++
3 new WithL1ICacheWays (1) ++
4 new WithL1DCacheSets (64) ++
5 new WithL1DCacheWays (1) ++
6 new CS 152 A b st r ac t C on f ig ++
7 new Wi thC a c he B lo c k By t es (64) )
Listing 5.1: Konfiguracija Rocket jezgra
Na ovaj način se u okviru Rocket chip-a definiše asocijativnost keš memorije. Parametri
WithL1ICacheSets i WithL1DCacheSets definišu na koliko koliko grupa se dijeli keš.
Parametri WithL1ICacheWays i WithL1DCacheWays definišu koliko lokacija se nalazi u
jednoj grupi. Parametar WithCacheBlockBytes određuje veličinu jednog bloka u baj-
tovima.
Može se primijetiti da ova konfiguracija definiše 4KB direktno mapiranog instrukcijskog
keša i 4KB direktno mapiranog keša za podatke, te da su keš linije duge 64B.

Testni program se pokreće sljedećom komandom:

make CONFIG=CS152RocketConfig run-binary-hex BINARY=${T_DIR}/transpose.riscv

Nakon izvršenja programa, na standardni izlaz se ispisuju vrijednosti nekoliko brojača

koji su pratili performanse hardvera tokom izvršavanja programa. Ovi podaci se mogu
iskoristiti da bi se dobio uvid u rad i performanse keš memorije. Konkretno, dobija se
sljedeći ispis:

cycles : 1346773
instret : 83261
loads : 16384
stores : 16407
I$ miss : 4
D$ regular miss : 18661
D$ prefetch miss : 0
D$ release : 28027
ITLB miss : 0
DTLB miss : 0
L2 TLB miss : 0
branches : 16640
mispredicts : 521
load-use interlock : 0
I$ blocked : 126
D$ blocked : 907670

Moguće je primijetiti nekoliko činjenica:

• Za izvršenje operacije je potrebno 1346773 ciklusa.

34
 • Kako se matrica čuva u row-major poretku, očekivano je da pristup po kolonama iza-
zove promašaje u keš memoriji. Kako je već naglašeno, teži se iskorišćenju prostorne
lokalnosti, pa će se u keš memoriji čuvati i neki podaci koji nisu još referencirani,
ali su susjedni trenutno referenciranom podatku. S obzirom da je susjedni podatak
sljedeći broj po redu, a ne koloni, dešava se keš promašaj.
• Broj promašaja u instrukcijskom kešu je nizak, što je i očekivano, jer je u pitanju for
petlja, pa su potrebne samo instrukcije sabiranja (inkrementovanje brojača petlje),
poređenja (da li je brojač dostigao krajnju vrijednost) i store instrukcije za čuvanje
podatka u destinacijsku matricu.

5.3.1 Zadatak: Cache blocking mehanizam

Iz prethodnog eksperimenta je očigledno da ovakav način implementacije transponovanja
nije optimalan u pogledu performansi keš memorije. Pokazuje se da se bolje performanse,
tj. manji broj promašaja, dobijaju kada se iskoristi tehnika blokovskog pristupa po-
dacima. To znači da se ulazna matrica dijeli na određen broj blokova dimenzija BxB, te
se operacija transponovanja izvodi nad ovim blokovima.
Potrebno je, u fajlu transpose.c, u funkciji transpose, napisati novi algoritam
koji će matricu transponovati na prethodno opisani način, te analizirati kako ovaj način
transponovanja utiče na performanse keš memorije. Takođe, potrebno je odrediti opti-
malnu vrijednost parametra B.

5.3.2 Ispitivanje uticaja načina asocijativnosti na performanse

keš memorije
Parametri keš memorije specifikovani su u config fajlu CS152RocketConfigs, kao što je
prikazano na listingu 5.1. Inicijalno je keš memorija podešena kao direktno mapirana,
što je definisano parametrom WithL1DWays, koji je jednak 1, što znači da se u svakoj
od 64 grupe nalazi po jedna lokacija, što dalje znači da se jedan blok može smjestiti
samo na jednu lokaciju. Potrebno je testirati kako će promjena asocijativnosti uticati na
performanse. Promijeniti asocijativnost na 2 modifikacijom parametara WithL1DWays i
WithL1DSets (kako bi kapacitet ostao isti), te ponovo kompajlirati simulator i pokrenuti
program koji vrši blokovsko transponovanje. Ponoviti postupak za vrijednosti asocija-
tivnosti od 4 i 8. Analizirati dobijene rezultate i primijetiti kako se broj promašaja
mijenja sa rastom asocijativnosti.

35
 Literatura

[1] CS152 kurs, https://inst.eecs.berkeley.edu/ cs152/sp21/

[2] David A Patterson, John L. Hennessy, Computer Architecture: A Quantitative
Approach
[3] David A Patterson, John L. Hennessy, Computer Organization and Design RISC-V
Edition: The Hardware Software Interface
[4] Andrew S. Tanenbaum, Structured Computer Organization
[5] Chipyard dokumentacija, https://chipyard.readthedocs.io/en/latest/
[6] Sodor dokumentacija, https://github.com/librecores/riscv-sodor/wiki
[7] RISC-V Instruction Set Manual,
https://riscv.org/wp-content/uploads/2017/05/riscv-spec-v2.2.pdf

36