Tag Line

PolyBoRi was created by man. There are two developers. And they have a plan.“

Tuesday, June 4, 2013

GSOC 2013 project for Polybori

I am Ioana-Maria Tamas and for this year's Google Summer of code, I will be working for lmonade's project: "Binary decision diagrams for Boolean polynomial rings". The main details of the project are the ones  below, but small modifications may occur.

  • 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