A coupled hardware and software architecture for programmable digital signal processors (synchronous data flow)
Edward Ashford Lee · 1986
Programmable signal processor architectures using extensive concurrency are considered together with the programming of such architectures. A synchronous data flow (SDF) programming paradigm, a special case of data flow (either large grain or atomic), is proposed as an attractive way of partitioning signal processing algorithms for concurrent execution on homogeneous parallel processors sharing memory. SDF programs are directed graphs where each arc represents a signal path and each node represents an operation. The number of samples consumed or produced each time a node is invoked is specified for each input or output path of each node. A SDF graph can be statically scheduled onto parallel processors, so the run time overhead usually associated with data flow evaporates. We show how to identify errors in the construction of an SDF graph, such as sample rate inconsistencies and directed loops with insufficient delay. We prove that a broad class of algorithms will find a periodic schedule if one exists and give specific algorithms, for both single and parallel processors. A procedure for finding a tight lower bound on the iteration period of a SDF graph is derived, and techniques for approaching this bound using cutset transformations are described. Minimizing the amount of memory dedicated to buffering is considered, as is asynchrony, in which the number of samples produced or consumed by a node is not specified. In addition to homogeneous parallel processors, SDF can be used to program extensively pipelined single processor architectures using an old but rarely used architectural approach. Multiple processes are interleaved through a single deeply pipelined processor. The use of both pipelining and interleaving suggests the designation PI or $\pi$ processors. Instead of programming a single pipelined processor, users construct programs that can execute as concurrent processes. A specific $\pi$ architecture is outlined and its programming using SDF is described. A voiceband data modem example implemented on this architecture illustrates the efficacy of one scheduling algorithm for finding parallel implementations without requiring the programmer to consider synchronization, scheduling, or deadlock avoidance.