Les tables de réservation numériques: Un outil pour la résolution de certains problèmes d’ordonnancement cycliques. (Numeric reservation tables: A tool for the solution of certain cyclic scheduling problems). (French) Zbl 0699.90058

Summary: This paper tackles a cyclic scheduling problem with resource constraints issued from a particular application: mapping a vector recurrent loop on a pipe-lined architecture. Any iteration is processed according to the same fixed generic schedule of its elementary taks. Iterations must be initiated so that the throughput is maximized. We define the numeric reservation table in order to manage general shared resource constraints and data dependences between the iterations, that were not taken into account in usual models. We develop an algorithm based on the search for critical cycles in a state graph, that produces the optimal periodic schedule for a given table. Moreover, a new upper bound of the throughput is stated.


90B35 Deterministic scheduling theory in operations research
Full Text: DOI EuDML