Mapping Multiple Independent Synchronous Dataflow Graphs
There are several forms of dataflow defined in Ptolemy. In synchronous dataflow (SDF) [5], the number of tokens produced or consumed in one firing of an actor is constant. This property makes it possible to determine execution order and memory requirements at compile time. These systems do not have the overhead of run-time scheduling (in contrast to dynamic dataflow) and have very predictable run-time behavior.
In this paper, we introduce a new model of computation with multiple independent dataflow graphs. To allow nondeterminate communication among these graphs, we introduce new communication actors that we call peek and poke. From the perspective of the independent dataflow schedulers, the peek actor is a data source and the poke actor is a data sink.
Code generation consists of two phases, scheduling and synthesis. In the scheduling phase, a dataflow graph is partitioned for parallel execution. We splice send and receive actors into the graph where an arc crosses the boundary between partitions that have been mapped to different processors. These actors do the necessary synchronization to prevent data loss in a self-timed implementation [2]. For each target processor, an ordering of actor invocations is determined. When there are multiple independent dataflow graphs, this scheduling process is repeated for each graph in the system. In the synthesis phase, the code segments associated with each actor are stitched together, following the order specified by the scheduler. Commercial systems that use this "threading" technique include Comdisco's DPC [3] and CADIS's Descartes [4]. The techniques we describe here are complementary to those in DPC and Descartes, and could, in principle, be used in combination with them.
In the next section, we discuss how a heterogeneous target is specified in Ptolemy. In section 3, we explain the new model of computation and how it can be used to interconnect independent dataflow graphs. In section 4, we study the implications for static and run-time scheduling of multiple graphs. Finally, we present two applications that run on a heterogeneous platform consisting of a unix workstation and a DSP card.