hrvatski

Dodjeljivanje registara bojenjem grafova

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.

bojenje grafova

nije evidentirano