S-Space College of Engineering/Engineering Practice School (공과대학/대학원) Dept. of Computer Science and Engineering (컴퓨터공학부) Journal Papers (저널논문_컴퓨터공학부)
Compile-Time Scheduling of Dynamic Contructs in Dataflow Program Graphs
- Ha, Soonhoi; Lee, Edward A.
- Issue Date
- IEEE Transactions on Computers, Vol. 46, No. 7, pp. 768-778, 1997
- multiprocessor scheduling; dynamic constructs; profile; macro actor; dataflow program graphs
- Scheduling data
ow 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 deci-
sions 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 un-
der 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 as-
sumptions, 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.
- Files in This Item: There are no files associated with this item.