Naslov
Dodjeljivanje registara bojenjem grafova
(Register assignment using graph coloring algorithms)

Autori
Dalbelo Bašić, Bojana

Vrsta, podvrsta i kategorija rada
Ocjenski radovi, magistarski rad

Fakultet
Fakultet elektrotehnike i računarstva

Mjesto
Zagreb

Datum
26.01

Godina
1993

Stranica
89

Mentor
Ribarić, Slobodan

Ključne riječi
bojenje grafova
(graph coloring)

Sažetak
Dodjela registara varijablama iz programa dio je završnog dijela prevoditelja. Djelotvornijom dodjelom registara ubrzava se rad prevedenog programa. Oblikovanje problema dodjele registara kao problema bojenja grafova daje vrlo jednostavnu i djelotvornu metodu za globalnu dodjelu registara. Svakoj varijabli iz programa odgovara jedan vrh na grafu interferencije, a brid između dva vrha postoji ako su varijable žive istodobno. Ako se graf interferencije može obojiti s k boja tako da nikoja dva susjedna vrha nisu obojena istom bojom, znači da se varijablama iz programa može dodijeliti k registara tako da se dvije istodobno žive varijable nisu dodijeljene istom registru. Budući da je problem nalaženja k-obojenosti grafa NP-potpun, uvode se heurističke metode koje u polinomijalnom vremenu nalaze zadovoljavajuća suboptimalna rješenja. U radu je prikazan Chaitinov heuristički postupak dodjele registara i njegova poboljšanja. Također su istaknute razlike u načinu rješavanja problema dodjele registara u arhitekturi CISC i RISC. U eksperimentalnom dijelu, izneseni su rezultati simulacije za slučajno generirane grafove različitih veličina, gustoće i raspodjele stupnjeva vrhova grafa. Pokazuje se da se najslabiji rezultati dobijaju kad je vjerojatnost interferencije između vrhova konstantna, tj. kada je očekivani stupanj vrha jednak za sve vrhove. Neravnomjernost stupnjeva vrhova pridonosi boljem smještanju u registre. Time je postavljena donja granica uspješnosti smještanja u registre. Oslanjajući se na rezultate eksperimenata iznesenih u nekim radovima - da je za grafove što nastaju iz stvarnih programa obično broj bridova oko 20 puta veći od broja vrhova - pokazalo se da je 40 registara granica od koje se nadalje sve varijable mogu smjestiti u registre. Primjeri primjene metode bojenja grafova dani su na nekoliko stvarnih procesorskih arhitektura.

Izvorni jezik
Hrvatski

Znanstvena područja
Računarstvo

POVEZANOST RADA