Publications of the Ptolemy Group
Compile-Time Scheduling of Dynamic Constructs in
Dataflow Program Graphs
by Soonhoi Ha and Edward A. Lee
IEEE Transactions on Computers, Vol. 46, No. 7, July 1997.
Scheduling dataflow graphs onto processors
consists of assigning actors to processors,
ordering their execution within the processors, and specifying
their firing time.
While all scheduling decisions can be made at runtime,
the overhead is excessive for most real systems. To reduce 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 such as
the execution time and the communication patterns. However, a
dynamic construct within a macro actor,
such as a conditional and a data-dependent iteration, makes
the profile of the actor unpredictable at compile time.
For those constructs, we propose to assume some profile at
compile-time and define a cost to be minimized
when deciding on the profile under the assumption that the runtime
statistics are available at compile-time.
Our decisions on the profiles of dynamic constructs are shown
to be optimal under some bold assumptions, and expected to be near-optimal
in most cases. The proposed scheduling technique has been implemented
as one of the rapid prototyping facilities in Ptolemy. This paper presents
the preliminary results on the performance with synthetic examples.
Send comments to Soonhoi Ha at firstname.lastname@example.org.