CATEGORII DOCUMENTE |
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.
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:
dimensiune | ||||||
memorie |
8000K |
9728K |
14360K |
34800K |
124768K | |
timp |
0,188s |
0,594s |
2,516s |
14,656s |
81,219s |
dimensiune | ||||||
memorie |
10000K |
11492K |
21060K |
59960K |
170000K | |
timp |
0,266s |
0,75s |
3,467s |
28,406s |
Libraria CUDD
dimensiune | ||||||
memorie |
8652K |
13344K |
66500K |
166000K | ||
timp |
0,187s |
0,781s |
3,469s |
19,359s |
118,016s |
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
Politica de confidentialitate | Termeni si conditii de utilizare |
Vizualizari: 1900
Importanta:
Termeni si conditii de utilizare | Contact
© SCRIGROUP 2024 . All rights reserved