COMPILE-TIME SCHEDULING OF DYNAMIC CONSTRUCTS IN DATA-FLOW PROGRAM GRAPHS

Scheduling dataflow graphs onto processors consists of assigning actor s to processors, ordering their execution within the processors, and s pecifying their firing time. While all scheduling decisions can be mad e at runtime, the overhead is excessive for most real systems. To redu ce this overhead, compile-time decisions can be made for assigning and /or ordering actors on processors. Compile-time decisions are based on known profiles available for each actor at compile time. The profile of an actor is the information necessary for scheduling, such as the e xecution time and the communication patterns. However, a dynamic const ruct within a macro actor, such as a conditional and a data-dependent iteration, makes the profile of the actor unpredictable at compile tim e. For those constructs, we propose to assume some profile at compile- time and define a cost to be minimized when deciding on the profile un der the assumption that the runtime statistics are available at compil e-time. Our decisions on the profiles of dynamic constructs are shown to be optimal under some bold assumptions, and expected to be near-opt imal inmost cases. The proposed scheduling technique has been implemen ted as one of the rapid prototyping facilities in Ptolemy. This paper presents the preliminary results on the performance with synthetic exa mples.