Naslov
Paralelni algoritmi izgradnje i manipulacije binarnim dijagramima odlučivanja
(Parallel algorithms for construction and manipulation of binary decision diagrams)

Autori
Grudenić, Igor

Vrsta, podvrsta i kategorija rada
Ocjenski radovi, magistarski rad

Fakultet
Fakultet elektrotehnike i računarstva

Mjesto
Zagreb

Datum
26.01

Godina
2006

Stranica
105

Mentor
Bogunović, Nikola

Ključne riječi
binarni dijagrami odlučivanja; paralelni algoritam; simbolička provjera modela; formalna verifikacija
(binary decision diagrams; parallel algorithms; symbolic model checking; formal verification)

Sažetak
Binarni dijagrami odlučivanja (BDD) dijagrami omogućavaju učinkovit prikaz i formalnu verifikaciju digitalnih sustava. Postoje razne heuristike za optimizaciju formalne verifikacije BDD dijagramima. Jedan od načina za poboljšanje efikasnosti formalne verifikacije temeljene na BDD dijagramima je raspodijeljena izgradnja i manipulacija BDD dijagramima. Prednost raspodijeljene izgradnje BDD dijagrama leži u većoj procesorskoj snazi i većoj količini raspoloživog memorijskog prostora. Magistarski rad opisuje raspodijeljeni algoritam izgradnje i manipulacije BDD dijagramima namijenjen sustavu umreženih računala zasnovan na kombiniranom pristupu izgradnje BDD dijagrama. U radu je prikazana arhitektura i neki od detalja implementacije programskog ostvarenja tog algoritma. Mjerenja učinkovitosti algoritma provedena su izgradnjom BDD prikaza digitalnog množila i zbrajala zbog njihovog karakterističnog BDD prikaza. Mjerenja su izvedena na grozdu računala i dvoprocesorskom sustavu. U radu je dodatno analiziran utjecaj ostvarene priručne memorije na učinkovitost raspodijeljene izgradnje BDD dijagrama.

Izvorni jezik
Hrvatski

Znanstvena područja
Računarstvo

POVEZANOST RADA