Worst case analysis on modulo scheduling for specialized processors systems

National audienceThe problem of cyclic scheduling for specialized processors systems is pre-sented and a worst case analysis of a heuristic scheduling algorithm is studied. Aresource constrained cyclic scheduling problem is characterized by k, the number oftypes of functional units employed, mx the maximal number of processors of the sametype and ± the maximal precedence delay. The main problem is to cope with bothprecedence and resource constraints which make the problem NP-complete in general.A guaranteed approach, called decomposed software pipelining, has been proposed byGasperoni and Schwiegelshohn, followed by the retiming method by Calland, Darteand Robert to solve the problem for parallel processors. We present, in this paper,an extension of this approach to resource-constrained cyclic scheduling problems withprecedence delays and we provide an approximation algorithm. Let ¸ and ¸opt berespectively the period given by the algorithm and the optimal period. We establishan approximation bound