This is an outdated home-page! Please visit my new one http://www.cs.usyd.edu.au/~scholz .

## Partitioned Boolean Quadratic Programming (PBQP)

Institut für Computersprachen E185/1
Home

Research

Embedded
Systems

PBQP

PDFA

Symbolic
Analysis

### 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 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:

• 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.
The system components of our PBQP library consists of
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

### 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]

 [TU Wien] [Institut für Computersprachen] [Home] last update: 13 Feb 2004