Citation
Time-Indexed Formulations and a Large Neighborhood Search for the Resource-Constrained Modulo Scheduling Problem. In proceedings of the 3rd Multidisciplinary International Conference on Scheduling : Theory and Applications (MISTA 2007), 28 -31 August 2007, Paris, France, pages 144-151, 2007.
Paper
Abstract
The resource-constrained modulo scheduling problem is motivated by the 1-periodic cyclic instruction scheduling problems that are solved by compilers when optimizing inner loops for instructionlevel parallel processors. In production compilers, modulo schedules are computed by heuristics, because even the most efficient integer programming formulation of resource-constrained modulo scheduling by Eichenberger and Davidson appears too expensive to solve relevant problems. We present a new time-indexed integer programming formulation for the resource-constrained modulo scheduling problem and we propose a large neighborhood search heuristic to make it tractable. Based on experimental data from a production compiler, we show that this combination enables to solve near optimally resource-constrained modulo scheduling problems of significant size. We also show that our large neighborhood search benefits to a lesser extent the resource-constrained modulo scheduling integer programming formulation of Eichenberger and Davidson.
You can download the pdf of this publication from here
doi
This publication does not have a doi, so we cannot provide a link to the original source
What is a doi?: A doi (Document Object Identifier) is a unique identifier for sicientific papers (and occasionally other material). This provides direct access to the location where the original article is published using the URL http://dx.doi/org/xxxx (replacing xxx with the doi). See http://dx.doi.org/ for more information
URL
This pubication does not have a URL associated with it.
The URL is only provided if there is additional information that might be useful. For example, where the entry is a book chapter, the URL might link to the book itself.
Bibtex
@INPROCEEDINGS{2007-144-151-P, author = {B. D. De Dinechin},
title = {Time-Indexed Formulations and a Large Neighborhood Search for the Resource-Constrained Modulo Scheduling Problem},
booktitle = {In proceedings of the 3rd Multidisciplinary International Conference on Scheduling : Theory and Applications (MISTA 2007), 28 -31 August 2007, Paris, France},
year = {2007},
editor = {P. Baptiste and G. Kendall and A. Munier-Kordon and F. Sourd},
pages = {144--151},
note = {Paper},
abstract = {The resource-constrained modulo scheduling problem is motivated by the 1-periodic cyclic instruction scheduling problems that are solved by compilers when optimizing inner loops for instructionlevel parallel processors. In production compilers, modulo schedules are computed by heuristics, because even the most efficient integer programming formulation of resource-constrained modulo scheduling by Eichenberger and Davidson appears too expensive to solve relevant problems. We present a new time-indexed integer programming formulation for the resource-constrained modulo scheduling problem and we propose a large neighborhood search heuristic to make it tractable. Based on experimental data from a production compiler, we show that this combination enables to solve near optimally resource-constrained modulo scheduling problems of significant size. We also show that our large neighborhood search benefits to a lesser extent the resource-constrained modulo scheduling integer programming formulation of Eichenberger and Davidson.},
owner = {Faizah Hamdan},
timestamp = {2012.05.21},
webpdf = {2007-144-151-P.pdf} }