Low level friendly programming

POLYBORI is implemented as layer over a decision diagram library (CUDD at the moment).

In CUDD every diagram node is unique: If two diagrams have the same structure, they are in fact identical (same position in memory). Another observation is, that CUDD tries to build a functional style API in the C programming language. This means, that no data is manipulated, only new nodes are created. Functional programming is a priori very suited for caching and multithreading (at the moment however threading is not possible in POLYBORI). The ite-operator is the most central function in CUDD. It takes two nodes/diagrams $ t$ , $ e$ and an index $ i$ and creates a diagram with root variable $ i$ and then-branch $ t$ , else-branch $ e$ . It is necessary that the branches have root variables with bigger index (or are constant). It creates either exactly one node, or retrieves the correct node from the cache. Function calls which come essentially down to a single ite call are very cheap.

For example taking the product $ x_1 \boolemult (x_2\boolemult (x3\boolemult (x_4\boolemult x_5)))$ is much cheaper than $ ((((x_1 \boolemult x_2)\boolemult x3)\boolemult x_4)\boolemult x_5)$ . In the first case, in each step a single not is prepended to the diagram, while in the second case, a completely new diagram is created. The same argument would apply for the addition of these variables. This example shows, that having a little bit background about the data structure, it is often possible to write code, that looks as well algebraic as provides good performance.

2011-02-25