  Dataflow devices represent an avenue towards saving the control and data
movement overhead of Load-Store Architectures. Various dataflow accelerators
have been proposed, but how to efficiently schedule applications on such
devices remains an open problem. The programmer can explicitly implement both
temporal and spatial parallelism, and pipelining across multiple processing
elements can be crucial to take advantage of the fast on-chip interconnect,
enabling the concurrent execution of different program components. This paper
introduces canonical task graphs, a model that enables streaming scheduling of
task graphs over dataflow architectures. We show how a task graph can be
statically analyzed to understand its steady-state behavior, and we use this
information to partition it into temporally multiplexed components of spatially
executed tasks. Results on synthetic and realistic workloads show how streaming
scheduling can increase speedup and device utilization over a traditional
scheduling approach.
