Publication: A Constraint Programming Approach for Instruction Assignment

All || By Area || By Year

Title	A Constraint Programming Approach for Instruction Assignment
Authors/Editors*	Mirza Beg and Peter van Beek
Where published*	Proceedings of the 15th Workshop on Interaction between Compilers and Computer Architectures (Interact-15), San Antonio, Texas
How published*	Proceedings
Year*	2011
Volume
Number
Pages
Publisher
Keywords
Link
Abstract	A fundamental problem in compiler optimization, which has increased in importance due to the spread of multi-core architectures, is to find parallelism in sequential programs. Current processors can only be fully taken advantage of if workload is distributed over the available processors. In this paper we look at distributing instructions in a block of code over multi-cluster processors, the {\it instruction assignment problem}. The optimal assignment of instructions in blocks of code on multiple processors is known to be NP-complete. In this paper we present a constraint programming approach for scheduling instructions on multi-cluster systems that feature fast inter-processor communication. We employ a problem decomposition technique to solve the problem in a hierarchical manner where an instance of the master problem solves multiple sub-problems to derive a solution. We found that our approach was able to achieve an improvement of 6\%-20\%, on average, over the state-of-the-art techniques on superblocks from SPEC 2000 benchmarks.