An Integer Programming Approach to Optimal Basic Block Instruction Scheduling for Single-Issue Processors

J√ľnger, Michael and Mallach, Sven (2015) An Integer Programming Approach to Optimal Basic Block Instruction Scheduling for Single-Issue Processors.
Published in: Discrete Optimization (Special Issue on Combinatorial Optimization). ISSN 1572-5286

This is the latest version of this item.

Abstract

We present a novel integer programming formulation for basic block instruction scheduling on single-issue processors. The problem can be considered as a very general sequential task scheduling problem with delayed precedence constraints. Our model is based on the linear ordering problem and has, in contrast to the last IP model proposed, numbers of variables and constraints that are strongly polynomial in the instance size. Combined with improved preprocessing techniques and given a time limit of ten minutes of CPU and system time, our branch-and-cut implementation is capable to solve all but eleven of the 369,861 basic blocks of the SPEC 2000 integer and floating point benchmarks to proven optimality. This is competitive to the current state-of-the art constraint programming approach that has also been evaluated on this test suite.


Actions:
Full text not available from this repository.
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: UNSPECIFIED
Depositing User: Sven Mallach
Date Deposited: 01 Feb 2016 12:37
Last Modified: 01 Feb 2016 12:37
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/897

Available Versions of this Item