Partitioned Boolean Quadratic Programming (PBQP)

Introduction

The Partitioned Boolean Quadratic Problem (PBQP) is a kind of Quadratic Assignment Problem (QAP). It was successfully applied to code generation techniques for embedded system processors such as Digital Signal Processors (DSP).  The problem is NP complete. In general it is very hard to obtain an optimal solution. However, a sub-class of PBQP can be solved in linear time.  By extending the linear algorithm with simple heuristics we achieved exceptional good results for our code generation techniques as shown in [1,2,3,4].

The mathematical formulation of PBQP is given in matrix notation. The unknowns of PBQP is a set of boolean decision vectors whose elements are in the domain of zeros and ones. An additional constraint restricts the decision vectors such that only one element of the vectors is assigned one; all other elements are set to zero. Between two boolean decision vectors costs are imposed by a cost matrix, which is formulated as a quadratic form. The objective is to minimize the overall costs. More formally, PBQP is defined as follows:

We use a normal form for which cost matrices with the same i and j are replaced by cost vectors and the two matrices of two boolean vectors are aggregate to one matrix due to properties of quadratic forms. The normal form is required for solving the problem and is given below:

Library

The goal of our work has been twofold:

• to find efficient and effective algorithms for achieving optimal or nearly optimal solution for PBQP
• to provide a PBQP library for daily use. This means defining useful interfaces and features to support applications.
  

run_test performs the fitness test of various approaches with a small given benchmark

make_dump produces the graphical HTML dump for the linear approach

Source Code

References

[1] Register Allocation for Irregular Architectures. B. Scholz and E. Eckstein. In Proc. of Joint-Conference on Languages, Compilers, and Tools for Embedded Systems and Software and Compilers for Embedded Systems (LCTES/SCOPES'02), pp. 139-148, ACM Press,  Berlin, Germany, June 2002. [ps.gz]

[2] Address Mode Selection. E. Eckstein and B. Scholz. In Proc. of  International Symposium on Code Generation and Optimization (CGO'03), pp. 337-346, IEEE Press, San Francisco, California, USA, March 2003. [pdf]

[3] Code Instruction Selection based on SSA-Graphs. E. Eckstein, O. König, and B. Scholz. In Proc. of International Workshop on Software and Compilers for Embedded Systems (SCOPES'03), Lecture Notes in Computer Science (LNCS), Vol. 2826, pp. 49-65, Springer Press, Vienna, Austria, September 2003. (best paper award). [pdf]

[4] Graph Coloring vs. Optimal Register Allocation for Optimizing Compilers. U. Hinschrott, A. Krall, and  B. Scholz. In Proc. of the Joint Modular Languages Conference (JMLC'03), Lecture Notes in Computer Science (LNCS), Vol. 2789, pp. 202-213, Springer Press, Klagenfurt, Austria, August 2003. [pdf]