|
Abstract : |
GLOBECOM, Dallas, Texas, November I989 completely addressed, either in the deterministic scheduling literature or in the multiprocessor systems literature. This paper will attempt to define these. Real-time digital signal processing often requires multiple processors. We assume the description of the program to be scheduled is a Unfortunately, in most practical situations, partitioning of DSP applica- dataflow graph, signal flow graph, or block diagram. Language classes tions for execution on multiple programmable Processors is ad-hoc. that are efficiently translated into dataflow graphs include functional, Automatic schedulers either (1) add unacceptable Cost to the implementation Or (2) address only a subset of applications. This Paper applicative, and single-assignment. In a dataflow graph the nodes, or actors, are functions that operate on data passed through the arcs. The explores the possibilities for automatic schedulers that result in IOW model is data-driven, in that actors fire (or perform their computation), imP1emenQfion Cost and Can target a broad class of DSP applications. when sufficient data is available on their input arcs. The role of the We Can define four classes of scheduling strategies, (1) fully dynamic, scheduler is simply to determine when to fire actors and on which pro-(2) static assiPment, (3) self-timed, and (4) fully static. Moving from cessor. The actors may have arbitrary granularity, meaning that they (1) to (4). more scheduling activity is Performed at compile time and less at run time. This Paper argues that for most DSP applications, self-timed scheduling is the most attractive. may represent atomic operations, such as addition and multiplication, or much more elaborate operations, such as transforms or digital filters. We assume that no attempt will be made to exploit concurrency within an actor, so that the scheduler only needs to operate on the dataflow 1., |
