Testarea sistemelor de calcul - Comparatie tehnologica intre 3 biblioteci de BDD (memoria ocupata, timp de raspuns)

Universitatea Politehnica Bucuresti

Facultatea de Automatica si Calculatoare

Testarea sistemelor de calcul

Comparatie tehnologica intre 3 biblioteci de BDD

(memoria ocupata, timp de raspuns)

1.Introducere

Diagramele de decizie binara reprezinta un mod de a reprezenta predicate pe un anumit numar de variabile logice(adevarat/fals), de exemplu, un set de atribuire pentru aceste variabile.

Diagramele de decizie binara sunt folosite in momentul in care putem reprezenta setul de date folosind o un set mai mic. O astfel de diagrama este un arbore binar care reprezinta alegerile care pot fi facute pentru atribuirea unor valori unor variabile logice. Fiecare nod reprezinta o variabila si fiecare sageata spre copii(stanga/dreapta) reprezinta o atribuire de 0 sau 1. Daca nu conteaza ce valoare a retinut variabila, atunci ea nu va mai fi inclusa in diagrama. Frunzele din diagrama sunt de asemenea variabile logice care indica daca atribuirea de valori din drumul parcurs de la radacina pana la ele reprezinta o valoare aflata in setul de date al problemei.

Proiectul de fata urmareste comparatia a 3 biblioteci de diagrame de decizie binara. Acestea sunt :

1.CUDD:CU Decision Diagram Package

2.CAL

3.BUDDY

BUDDY este o librarie de diagrame de decizie cu foarte multe operatii vectoriale optimizate pentru BDD-uri, garbage collector automat , o interfata C++ si multe altele.

CAL este un pachet bazat pe parcurgerea in latime a arborelui. Are implementat un algoritm de garbage collection bazat pe compactarea memoriei folosite.

CUDD este o librarie care manipuleaza BDD-uri, ADD-uri (diagrame de decizie algebrica) si ZDD-uri(Zero-suppressed BDD). In pachet sunt incluse si functii pentru trecerea intre oricare 2 din cele 3 tipuri.

2. Descrierea proiectului

Pentru compararea performantelor celor 3 librarii de am construita o mica aplicatie Java, pornind de la pachetul JavaBDD.

Acesta este o aplicatie care foloseste cele 3 librarii pentru a rezolva 2 probleme celebre : problema celor N dame si problema cubului lui Rubik.   El ne pune la dispozitie 2 clase, cate una pentru fiecare din cele 2 probleme, care pot fi apelate pentru construirea solutiilor.

Interfata grafica a aplicatiei permite utilizatorului sa seteze mai multi parametri : problema ce va fi rezolvata(N dame sau Rubik), dimensiunea tablei de joc, respectiv a cubului si libraria ce va fi folosita la rulare(CAL, CUDD, BUDDY) . Rularea efectiva se va face in momentul apasarii butonului OK. Dupa rularea efectiva a aplicatiei se vor afisa statisticile referitoare la rularea anterioara(timp de procesor si memorie utilizata).

Programul nostru ruleaza unul din cele 2 programe asociate fiecareia dintre cele 2 probleme. Folosind apelurile functiilor de sistem se poate determina cata memorie a fost alocata pentru rezolvarea problemelor, comparand memoria ocupata de aplicatie inainte si dupa rularea problemelor.

3. Testarea proiectului

Pentru compararea performantelor celor 3 biblioteci am rulat de mai multe ori aplicatia cu diferiti parametri pentru problema celor N dame.

Sistemul care a fost folosit are urmatorea configuratie :

AMD Sempron 2200 1.80GHz)

256 MB of RAM

Rezulatele sunt urmatoarele:

Libraria BUDDY:

Libraria CAL:

Libraria CUDD

4.Concluzii

Desi testul nu este cel mai puternic putem spune ca dintre cele 3 pachete cea mai eficienta este BUDDY, dupa care urmeaza CUDD. Dupa cum se poate observa