Citation
Decomposed Software Pipelining for cyclic unitary RCPSP with precedence delays. Proceedings of the 4th Multidisciplinary International Scheduling Conference: Theory and Applications (MISTA 2009), 10-12 Aug 2009, Dublin, Ireland, pages 254-265, 2009.
Paper
Abstract
In this paper we adress a new cyclic problem: finding periodic schedules for unitary resource constrained cyclic scheduling problem. Such resource constraints are characterized by k, the number of types of functional units employed and mx the maximal number of processors of the same type. The main problem is to cope with both precedence delays and resources which make the problem NP-complete in general. A guaranteed approach, called decomposed software pipelining, has been proposed by Gasperoni and Schwiegelshohn, followed by the retiming method by Calland, Darte and Robert to solve the problem for parallel processors and ordinary precedences. We present, in this paper, an extension of this approach to resource-constrained cyclic scheduling problems with precedence delays and we provide an approximation algorithm. Let lambda and lambda_opt be respectively the period given by the algorithm and the optimal period. We establish a new bound.
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{2009-254-265-P, author = {A. Benabid and C. Hanen},
title = {Decomposed Software Pipelining for cyclic unitary RCPSP with precedence delays},
booktitle = {Proceedings of the 4th Multidisciplinary International Scheduling Conference: Theory and Applications (MISTA 2009), 10-12 Aug 2009, Dublin, Ireland},
year = {2009},
editor = {J. Blazewicz and M. Drozdowski and G. Kendall and B. McCollum},
pages = {254--265},
note = {Paper},
abstract = {In this paper we adress a new cyclic problem: finding periodic schedules for unitary resource constrained cyclic scheduling problem. Such resource constraints are characterized by k, the number of types of functional units employed and mx the maximal number of processors of the same type. The main problem is to cope with both precedence delays and resources which make the problem NP-complete in general. A guaranteed approach, called decomposed software pipelining, has been proposed by Gasperoni and Schwiegelshohn, followed by the retiming method by Calland, Darte and Robert to solve the problem for parallel processors and ordinary precedences. We present, in this paper, an extension of this approach to resource-constrained cyclic scheduling problems with precedence delays and we provide an approximation algorithm. Let lambda and lambda_opt be respectively the period given by the algorithm and the optimal period. We establish a new bound.},
owner = {gxk},
timestamp = {2010.10.11},
webpdf = {2009-254-265-P.pdf} }