(PDF) Mirza Beg and Peter van Beek. A Constraint Programming Approach for Instruction Assignment. Proceedings of the 15th Workshop on Interaction between Compilers and Computer Architectures (Interact-15), San Antonio, Texas, February, 2011
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.