My proposal for GSOC2013

I wrote this proposal for this year's Google Summer of Code, as I intend to work for a project of the Lmonade organisation. More specifically, this project involves working with Polybori, a C++ library that allows high-level manipulation of Boolean Polynomial Rings.

• Title

"Binary decision diagrams for Boolean polynomial rings"

• Abstract

Zero-suppressed binary decision diagrams are used by Polybori for efficiently representing Boolean polynomials. At the moment, they are manipulated via CUDD, which is not specialized on this type of diagrams and only uses C in the implementation. The goal of the project is implementing an independent library in C++, that is specialized on  zero-suppressed binary decision diagrams.

• Objective

There are no major problems in the current method used to deal with decision diagrams, but implementing the new library will definitely increase Polybori’s usability and efficiency. The things that will be reimplemented are the reference counting, the caching management, the diagram manager and then the operators and methods from the decision diagram class.

• Deliverables

The final product will be a well-documented, well-tested and easy to build library, that will help Polybori manipulate Boolean Polynomials without using CUDD in the background, and in a more efficient and specialized way.

• Timeline

  
  

  
  

  Time Frame	Milestone
  17 June - 24 June	Prepare unit tests for a wrapper class that works with CUDD in the background
  25 June - 5 July	Implement a C++ reference counting method
  6 July - 11 July	Add the new method to the wrapper and test
  12 July - 26 July	Implement a C++ cache management method
  27 July - 2 August	Add the new method to the wrapper and test Prepare for midterm evaluation
  3 August - 16 August	Re-implement the DdManager, DdNode and DdChild and test them
  17 August - 31 August	Implement a C++ ZDD class, with all the operations and methods available in CUDD
  1 September - 9 September	Write unit tests that are independent from CUDD
  10 September - 15 September	Optional: Make an independent C++ library using the new implementations (with a proper build system) Test everything without CUDD
  16 September - 23 September	Finalize documentation Prepare for final evaluation