Universität zu Köln

Juenger, Michael and Mallach, Sven ORCID: 0000-0001-5335-0678 (2016). An integer programming approach to optimal basic block instruction scheduling for single-issue processors. Discret. Optim., 22. S. 37 - 66. AMSTERDAM: ELSEVIER. ISSN 1873-636X

Full text not available from this repository.

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. (C) 2015 Elsevier B.V. All rights reserved.

Item Type:	Journal Article
Creators:	Creators Email ORCID ORCID Put Code Juenger, Michael UNSPECIFIED UNSPECIFIED UNSPECIFIED Mallach, Sven UNSPECIFIED orcid.org/0000-0001-5335-0678 UNSPECIFIED
URN:	urn:nbn:de:hbz:38-256593
DOI:	10.1016/j.disopt.2015.10.003
Journal or Publication Title:	Discret. Optim.
Volume:	22
Page Range:	S. 37 - 66
Date:	2016
Publisher:	ELSEVIER
Place of Publication:	AMSTERDAM
ISSN:	1873-636X
Language:	English
Faculty:	Faculty of Mathematics and Natural Sciences
Divisions:	Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science
Subjects:	Data processing Computer science
Uncontrolled Keywords:	Keywords Language MACHINE SEQUENCING PROBLEM; EXPRESSIONS; ALGORITHM Multiple languages Operations Research & Management Science; Mathematics, Applied Multiple languages
Refereed:	Yes
URI:	http://kups.ub.uni-koeln.de/id/eprint/25659