cs-486:homework-12 [CS Wiki]

This Homework has you implement a BDD package. The classes and their interfaces that you need to implement are defined in the file bddObj.h which is part of the source distribution. You must create the necessary support functions and data types to implement the classes and functions in the in the file bddObj.h and bddObj.cpp. You may modify only these two files and the file main.cpp. Everything should be defined, where possible, using the ITE operator. Also, you are required to use a unique table and a compute table for ITE. A compute table memorizes calls to ITE and returns the previously computed BDD (e.g., a cache keyed on the parameters to ITE). This project includes a predefined main, and you can change it to suit your needs. Also included is a Makefile for your convenience.

The ITE function declaration is given below:

BDD Ite(const BDD& g, const BDD& h, unsigned int limit = 0) const;

The function f is this object invoking the method (i.e., the this-object in the method definition). The function g and h have their usual meanings. Please ignore the limit variable that is optional in the CUDD interface.

Part of your grade depends on correctly managing memory. Memory leaks will cause deductions in your final score. You will need to check your work by running it with valgrind, ccmalloc, or similar memory degugging tool. Valgrind is current running on any of the Linux open lab machines.

Variable Ordering

The variable order is the order in which variables are created. The first created variable is the least variable that sits highest in the BDD. The most recent created variable is the greatest variable that sits just above the terminals. Using such an order will match the ordering in CUDD, and it will match the expected (assumed) ordering for the bddToDot function.

Obtaining the Source Distribution

The source is in a GIT repository which need to clone. The repository is located on the CS Open Lab under the egm account: ~egm/public-git/cs686/bdd-package. You must use GIT to clone the repository as well as to get updates and revisions throughout the semester. The GIT clone can be done as:

$ git clone ssh://_YOURID_@schizo.cs.byu.edu/~egm/public-git/cs686/bdd-package
   Cloning into 'bdd-package'...
   remote: Counting objects: 9, done.
   remote: Compressing objects: 100% (8/8), done.
   remote: Total 9 (delta 0), reused 0 (delta 0)
   Receiving objects: 100% (9/9), 8.15 KiB, done.

Please note that <user> should be your user name for the CS system. Also, some versions of GIT do not like the ~-expansion so you might need to include the full path to my home directory (/users/faculty/egm/public-git/cs431/lectures).

Building and Running

This source distribution should compile and link out of the box but running it will cause a segmentation fault. To build and run, use the command:

   > make; bdd-test

Edit the Makefile to change compilers, flags, objects for linking etc.

Using CUDD as an Oracle

Download and install the Cudd and Graphviz libraries. And then do

make USE_CUDD=1

Be sure to run make clean first to remove any object files that may be build with your code.

DumpDot for Debugging

Using DumpDot is not mandatory for completing the homework as it is very possible to test your results by traversing your unique table and comparing to expected answers. That said, it is still highly recommended as it is extremely helpful to analyze a visual representation of a BDD especially when debugging.

CUDD provides a cofactor method that operates not just on a variable but any arbitrary function. The function f.Restrict(g) returns a new function that is f only variables in f are restricted to specific values which are those that allow g to be true on some assignment of the remaining variables (if at all possible). If you call restrict as

BDD x = bddMgr.getVar(2);
f.Restrict(x);

The you get the function f with x set to true, which is a positive cofactor. f.Restrict(~x) is the negative cofactor. The Restrict method devolves into a simple cofactor, just like what is used in a Shannon expansion when, for a given variable $x$, using the BDD representing $f(x) = x$. As such, DumpDot requires a restrict function to traverse the BDD: BDD BDD::Restrict(BDD g) The below code is a simple implementation of the restrict function which can be readily added to your BDD interface:

BDD BDD::Restrict(BDD g) {
   if (isOne() || isZero()) return *this; 
   int varIng = g.getVariable();
   int varInf = this.getVariable();
   BDD high = g.getHigh();
   BDD low = g.getLow();
   // Make sure g is an identify function: f(g) = g
   assert (high == bddMgr.getOne() || high == bddMgr.getZero());
   assert (low == bddMgr.getOne() || low == bddMgr.getZero());
   if (varIng > varInf) {
      assert(0);
   }
   if (varIng == varInf) {
      if (high == bddMgr.getOne())
         return this.getHigh();
      else 
         return this.getLow();
   }
   return *this;
}

The above code is only a template, and you will need to satisfy yourself that it is correct (or otherwise). Once it is added to the interface, then DumpDot behaves just like it companion version in Cudd only you have to provide the BDD manager as the first argument. See the main.cpp file for an example.

Grading

80 points: Ite Implementation
5 points: Using Ite to implement all Boolean connectives where apprioriate
15 points: Tests and documentation (implementation details and how to test your code). Your documentation can be a separate file or the body of your commit comment (see me for help with Git).

Submission

Please submit a patch to the original repository via the Homework 5 link in Learning Suite.

cs-486/homework-12.txt · Last modified: 2017/12/06 14:40 by egm

Back to top

Table of Contents