Full Text Available
Note: Clicking the button above will open the full text document at the original institutional repository in a new window.
Distributed binary decision diagrams
Thesis (MSc (Mathematical Sciences)--University of Stellenbosch, 2010.
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | English |
| Published: |
Stellenbosch : University of Stellenbosch
2010
|
| Subjects: | |
| Tags: |
No Tags, Be the first to tag this record!
|
| _version_ | 1867614030029389824 |
|---|---|
| access_status_str | Open Access |
| author | Fasan, Mary Oluwasola |
| author2 | Geldenhuys, Jaco |
| author_browse | Fasan, Mary Oluwasola Geldenhuys, Jaco |
| author_facet | Geldenhuys, Jaco Fasan, Mary Oluwasola |
| author_sort | Fasan, Mary Oluwasola |
| collection | Thesis |
| dc_rights_str_mv | University of Stellenbosch |
| description | Thesis (MSc (Mathematical Sciences)--University of Stellenbosch, 2010. |
| format | Thesis |
| id | oai:scholar.sun.ac.za:10019.1/5411 |
| institution | Stellenbosch University (South Africa) |
| language | English |
| last_indexed | 2026-06-10T12:45:32.686Z |
| license_str | Other — see source repository |
| provenance_str_mv | Harvested via OAI-PMH from SUNScholar — Stellenbosch University Repository |
| publishDate | 2010 |
| publishDateRange | 2010 |
| publishDateSort | 2010 |
| publisher | Stellenbosch : University of Stellenbosch |
| publisherStr | Stellenbosch : University of Stellenbosch |
| record_format | dspace |
| source_str | SUNScholar — Stellenbosch University Repository |
| spelling | oai:scholar.sun.ac.za:10019.1/5411 Distributed binary decision diagrams Fasan, Mary Oluwasola Geldenhuys, Jaco University of Stellenbosch. Faculty of Science. Dept. of Mathematical Sciences. Computer Sciience. Program verification Data structures Binary decision diagrams Distributed computing Dissertations -- Mathematical sciences Theses -- Mathematical sciences Dissertations -- Computer science Theses -- Computer science Thesis (MSc (Mathematical Sciences)--University of Stellenbosch, 2010. ENGLISH ABSTRACT: Binary Decision Diagrams (BDDs) are data structures that have been used to solve various problems in different aspects of computer aided design and formal verification. The large memory and time requirements of BDD applications are the major constraints that usually prevent the use of BDDs since there is a limited amount of memory available on a machine. One way of overcoming this resource limitation problem is to utilize the memory available on a network of workstations (NOW). This requires the distribution of the computation and memory requirements involved in the manipulation of BDDs over a NOW. In this thesis, an algorithm for manipulating BDDs on a NOW is presented. The algorithm makes use of the breadth-first technique to manipulate BDDs so that various BDD operations can be started concurrently on the different workstations on the NOW. The design and implementation details of the distributed BDD package are described. The various approaches considered in order to optimize the performance of the algorithm are also discussed. Experimental results demonstrating the performance and capabilities of the distributed package and the benefits of the different optimization approaches are given. AFRIKAANSE OPSOMMING: Binêre besluitnemingsbome (BBBs) is data strukture wat gebruik word om probleme in verskillende areas van Rekenaarwetenskap, soos by voorbeeld rekenaargesteunde ontwerp en formele verifikasie, op te los. Die tyd- en spasiekoste van BBB-gebaseerde toepassings is die hoofrede waarom BBBs nie altyd gebruik kan word nie; die geheue van ’n enkele is ongelukkig te beperkend. Een manier om hierdie hulpbronprobleem te omseil, is om die gedeelde geheue van die werkstasies in ’n netwerk van werkstasies (Engels: “network of workstations”, oftewel, ’n NOW) te benut. Dit is dus nodig om die berekening en geheuevoorvereistes van die BBB bewerking oor die NOW te versprei. Hierdie tesis bied ’n algoritme aan om BBBs op ’n NOW te hanteer. Die algoritme gebruik die breedte-eerste soektegniek, sodat BBB operasies gelyklopend kan uitvoer. Die details van die ontwerp en implementasie van die verspreide BBB bilbioteek word beskryf. Verskeie benaderings om die gedrag van die biblioteek te optimeer word ook aangespreek. Empiriese resultate wat die werkverrigting en kapasiteit van die biblioteek meet, en wat die uitwerking van die onderskeie optimerings aantoon, word verskaf. 2010-09-16T09:41:00Z 2010-12-15T10:43:03Z 2010-09-16T09:41:00Z 2010-12-15T10:43:03Z 2010-12 Thesis http://hdl.handle.net/10019.1/5411 en University of Stellenbosch 95 p. : ill. application/pdf Stellenbosch : University of Stellenbosch |
| spellingShingle | Program verification Data structures Binary decision diagrams Distributed computing Dissertations -- Mathematical sciences Theses -- Mathematical sciences Dissertations -- Computer science Theses -- Computer science Fasan, Mary Oluwasola Distributed binary decision diagrams |
| title | Distributed binary decision diagrams |
| title_full | Distributed binary decision diagrams |
| title_fullStr | Distributed binary decision diagrams |
| title_full_unstemmed | Distributed binary decision diagrams |
| title_short | Distributed binary decision diagrams |
| title_sort | distributed binary decision diagrams |
| topic | Program verification Data structures Binary decision diagrams Distributed computing Dissertations -- Mathematical sciences Theses -- Mathematical sciences Dissertations -- Computer science Theses -- Computer science |
| url | http://hdl.handle.net/10019.1/5411 |
| work_keys_str_mv | AT fasanmaryoluwasola distributedbinarydecisiondiagrams |