Numeric reservation tables: A tool for solving some cyclic scheduling problems

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 tasks. Iterations must be initiated so that the throughput is maximized. The paper defines 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. It develops 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.