SYNTHESIS OF EMBEDDED SOFTWARE FROM SYNCHRONOUS DATAFLOW SPECIFICATIONSShuvra S. Bhattacharyya, Praveen K. Murthy, and Edward A. LeeABSTRACTThe implementation of software for embedded digital signal processing (DSP) applica-tions is an extremely complex process. The complexity arises from escalating functionality in theapplications; intense time-to-market pressures; and stringent cost, power and speed constraints.To help cope with such complexity, DSP system designers have increasingly been employinghigh-level, graphical design environments in which system specification is based on hierarchicaldataflow graphs. Consequently, a significant industry has emerged for the development of data-flow-based DSP design environments. Leading products in this industry include SPW fromCadence, COSSAP from Synopsys, ADS from Hewlett Packard, and DSP Station from MentorGraphics.This paper reviews a set of algorithms for compiling dataflow programs for embeddedDSP applications into efficient implementations on programmable digital signal processors. Thealgorithms focus primarily on the minimization of code size, and the minimization of the memoryrequired for the buffers that implement the communication channels in the input dataflow graph.These are critical problems because programmable digital signal processors have very limitedamounts of on-chip memory, and the speed, power, and cost penalties for using off-chip memoryare often prohibitively high for embedded applications. Furthermore, memory demands of appli-cations are increasing at a significantly higher rate than the rate of increase in on-chip memorycapacity offered by improved integrated circuit technology.This research is part of the Ptolemy project, which is supported by the Defense AdvancedResearch Projects Agency (DARPA), the Air Force Research Laboratory, the State of California MICROprogram, and the following companies: The Alta Group of Cadence Design Systems, Hewlett Packard,Hitachi, Hughes Space and Communications, NEC, Philips, and Rockwell.S. S. Bhattacharyya is with the Department of Electrical and Computer Engineering and the Insti-tute for Advanced Computer Studies, University of Maryland, College Park.P. K. Murthy is with Angeles Design Systems, San Jose, California.E. A. Lee is with the Department of Electrical Engineering and Computer Sciences, University ofCalifornia at Berkeley.In Journal of VLSI Signal Processing Systems, Vol 21, No. 2, pages 151-166, June 1999.© 1999 Kluwer Academic Publishers.21. IntroductionNumerous software design environments for digital signal processing applications, such as those described in [6, 14, 16, 23, 24, 27], support code-generation for programmable digital signal processors used in embedded systems. Traditionally, programmable digital signal proces-sors have been programmed manually, in assembly language, and this is a tedious, error-prone process at best. Hence, generating code automatically is a desirable goal. Since the amount of on-chip memory in programmable digital signal processors is severely limited, it is imperative that the generated code be parsimonious in its memory usage. Adding off-chip memory is often highly unattractive due to increased cost, increased power requirements, and a speed penalty that will affect the feasibility of real-time implementations. One approach to automatic code generation is to specify the program in an imperative lan-guage such as C, C++, or FORTRAN and use a good compiler. However, even the best compilers today produce inefficient code [31], although a significant research community is evolving to address the challenges of compiling imperative programming languages into implementations on embedded processors such as programmable digital signal processors [20]. In addition, specifica-tions in imperative languages are difficult to parallelize, are difficult to change due to side effects, and offer few chances for any formal verification of program properties. An alternative is to use a block diagram language based on a model of computation with strong formal properties such as synchronous dataflow [17] to specify the system, and to perform code-generation starting from this specification. One reason that a compiler for a block diagram language is likely to deliver bet-ter performance than a compiler for an imperative language is that the underlying model of com-putation often exposes restrictions on the control flow of the specification, and this can be profitably exploited by the compiler.Synchronous dataflow (SDF) [17] is a special case of dataflow. In SDF, a program is rep-resented by a directed graph in which each vertex (actor) represents a computation, an edge spec-ifies a FIFO buffer, and each actor produces (consumes) a fixed number of data values (tokens) onto (from) each output (input) edge per invocation. A parameter on each edge specifies the num-ber of initial tokens (called delays) residing on that edge.One code-generation strategy followed in many block diagram programming environ-3ments is called threading; in this method, the underlying model (in this case, SDF) is scheduled to generate a sequence of actor invocations (provided that the model can be scheduled at compile time of-course). A code generator then steps through this schedule, and for each actor encoun-tered in the schedule, the code generator inserts a code block that implements the computation specified by the given actor. The individual code blocks, which can be specifications in assembly language or any high level language, are obtained from a predefined library of actor code blocks. Typically, in block diagram design tools for DSP, assembly language (feasible since the actors are usually small, modular components) or C is used to specify the functionality of individual code blocks. By “compiling an SDF graph”, we mean exactly the strategy described above for generat-ing a software implementation from an SDF graph specification of the system in a block diagram environment.We also assume that the code-generator generates inline code; this is because the alterna-tive of using subroutine calls can have unacceptable overhead, especially if there are many small tasks. A key problem that arises with such an in-line code generation strategy is code-size explo-sion. For example, if an actor appears 20 times in the schedule, then there will be 20 code blocks in the generated code. Clearly, such code duplication can consume enormous amounts of memory, especially if