1st Edition

Memory Management for Synthesis of DSP Software

    320 Pages 107 B/W Illustrations
    by CRC Press

    Although programming in memory-restricted environments is never easy, this holds especially true for digital signal processing (DSP). The data-rich, computation-intensive nature of DSP makes memory management a chief and challenging concern for designers. Memory Management for Synthesis of DSP Software focuses on minimizing memory requirements during the synthesis of DSP software from dataflow representations. Dataflow representations are used in many popular DSP design tools, and the methods of this book can be applied in that context, as well as other contexts where dataflow is used.

    This book systematically reviews research conducted by the authors on memory minimization techniques for compiling synchronous dataflow (SDF) specifications. Beginning with an overview of the foundations of software synthesis techniques from SDF descriptions, it examines aggressive buffer-sharing techniques that take advantage of specific and quantifiable tradeoffs between code size and buffer size to achieve high levels of buffer memory optimization.

    The authors outline coarse-level strategies using lifetime analysis and dynamic storage allocation (DSA) for efficient buffer sharing as one approach and demonstrate the role of the CBP (consumed-before-produced) parameter at a finer level using a merging framework for buffer sharing. They present two powerful algorithms for combining these sharing techniques and then introduce techniques that are not restricted to the single appearance scheduling space of the other techniques.

    Extensively illustrated to clarify the mathematical concepts, Memory Management for Synthesis of DSP Software presents a comprehensive survey of state-of-the-art research in DSP software synthesis.

    INTRODUCTION
    Electronic Embedded Systems
    Digital Signal Processing Systems
    Actor-Oriented Design
    Dataflow MoCs for DSP Systems
    Synthesis Techniques in AOPEs
    Advances in Compilers for DSPs
    Other Related Work-Nested Loop Scheduling

    NOTATION AND BACKGROUND
    Graph Terminology
    Synchronous Dataflow
    Synthesis from SDF Graphs
    Scheduling Problems for SDF Graphs
    Constructing Memory-Efficient Loop Structures
    Scheduling for Other Metrics
    Other Topics: Holes
    Summary

    LIFETIME ANALYSIS
    Introduction
    The Shared Buffer Model
    Creating the Interval Instances from a SAS
    Conclusion

    DYNAMIC STORAGE ALLOCATION
    Some Notation
    Heuristic for DSA
    Computing the Maximum Clique Weight
    Experimental Results
    Approximation Algorithms

    THE CBP PARAMETER
    Related Work
    Introduction to Buffer Merging
    The CBP Parameter
    Multirate FIR Filters
    Chop
    Autocorrelation
    CBP Tables
    Summary of Derivations
    Conclusion

    BUFFER SHARING VIA MERGING TECHNIQUES
    Merging an Input/Output Buffer Pair
    Merging a Chain of Buffers
    A Heuristic for Merged Cost-Optimal SAS
    Conclusion

    BUFFER MERGING ALGORITHMS
    Acyclic Graphs
    Experimental Results
    Conclusion

    BEYOND SINGLE APPEARANCE SCHEDULES
    Recursive Decomposition of a Two-Actor SDF Graph
    Extension to Arbitrary SAS
    CD-DAT Example
    Experimental Results
    Conclusion

    CONCLUSION
    Regularity
    Fixed-Point Optimizations
    Reconfigurable Systems
    Grand Challenge

    REFERENCES
    INDEX

    Biography

    Praveen K. Murthy, Shuvra S. Bhattacharyya