OBF: Optimized Blist Form
Professor Jarek Rossignac
School of Interactive Computing
College of Computing, Georgia Tech
TSRB-320 (Tech Square), directions


Let F be a positive-form Boolean expression with n literals. Assume that the values of the literals are made available one at a time in any desired order, but only once. Let s(n) be the number of steps (operations) and b(n) of bits of working memory (footprint) needed to evaluate F. The Optimized Blist Form (OBF) evaluates F using only s(n)=n steps and b(n)=log2j bits, where j=log2(2n/3+2). This unprecendented O(loglog n) guaranteed footprint upper bound has considerable theoretical and practical applications.

A Boolean expression F may be converted to its positive form and represented by a binary tree with only union and intersection nodes and leaves each representing a literal. Such a tree may be converted ("wired") into its Blist form, which can be represented as a digital circuit and evaluated by accessing the leaves values one by one from left to right. The working memory (footprint) needed for the evaluation of E corresponds symbolically to the maximum number of wires crossing any vertical line that would split the circuit. Hence, the expression below needs 3 bits because 3 wires are running through a vertical that would separate the two last gates.

The Optimized Blist Form (OBF) is the Blist form of an equivalent version of the Boolean expression F obtained through a linear cost "Flipper" algorithm that pivots (swaps) the left and right children of some of the operators in the tree. The pivoting reduces b(n). In the example below, it reduces the footprint b(n) from 5 to 2 bits.

...

We investigate three applications:
  • Direct CSG (Constructive Solid Geometry) rendering on the GPU, where candidate surfels are each classified against arbitrarily complex Boolean expressions using only 6 stencil bits.

  • Logic Matrix (LM), which evaluates E in one cycle using a matrix of nxj wires/lines; and

  • Logic Pipe (LP), which uses n gates connected by a pipe of log2j lines and when receiving a staggered stream of input vectors produces a new value of F per cycle.

    Report: "Optimized Blist Form (OBF)" by J. Rossignac. GVU Tech Report GIT-GVU-07-10. PDF
    search site    or the Web