Partitioned Boolean Quadratic Programming (PBQP)
|Institut für Computersprachen E185/1|
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:
LibraryThe PBQP library is written in C for Linux. It provides a generic interface for various approaches to solve a specific PBQP problem. At the moment a brute force approach and the linear approach with heuristics are available. A branch and bound approach will be available soon. A set of tools also provides graphical HTML dumps for debug purposes and a fitness tests for PBQP solutions.
The goal of our work has been twofold:
Source CodePBQP v1.0 is the latest version of the library tarball.
 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]
 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]
 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]
 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]