Exploring trade-offs in buffer requirements and throughput constraints for synchronous dataflow graphs

ABSTRACT

Multimedia applications usually have throughput constraints. An implementation must meet these constraints, while it minimizes resource usage and energy consumption. The compute intensive kernels of these applications are often specified as Synchronous Dataflow Graphs. Communication between nodes in these graphs requires storage space which influences throughput. We present exact techniques to chart the Pareto space of throughput and storage trade-offs, which can be used to determine the minimal storage space needed to execute a graph under a given throughput constraint. The feasibility of the approach is demonstrated with a number of examples.

REFERENCES

• 1: Marleen Adé , Rudy Lauwereins , J. A. Peperstraete, Data memory minimisation for synchronous data flow graphs emulated on DSP-FPGA targets, Proceedings of the 34th annual conference on Design automation, p.64-69, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266036]
• 2: Karine Altisen , Gregor Gößler , Joseph Sifakis, A Methodology for the Construction of Scheduled Systems, Proceedings of the 6th International Symposium on Formal Techniques in Real-Time and Fault-Tolerant Systems, p.106-120, September 20-22, 2000
• 3: T. Amnell et al. Times: a tool for schedulability analysis and code generation of real-time systems. In FORMATS'03, number 2791 in LNCS (2004), Springer-Verlag, p. 60--72.
• 4: Shuvra S. Battacharyya , Edward A. Lee , Praveen K. Murthy, Software Synthesis from Dataflow Graphs, Kluwer Academic Publishers, Norwell, MA, 1996
• 5: Shuvra S. Bhattacharyya , Praveen K. Murthy , Edward A. Lee, Synthesis of Embedded Software from Synchronous Dataflow Specifications, Journal of VLSI Signal Processing Systems, v.21 n.2, p.151-166, June 1999 [doi>10.1023/A:1008052406396 ]
• 6: Joseph Tobin Buck , Edward A. Lee, Scheduling dynamic dataflow graphs with bounded memory using the token flow model, 1993
• 7: Marc Geilen , Twan Basten , Sander Stuijk, Minimising buffer requirements of synchronous dataflow graphs with model checking, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, San Diego, California, USA [doi>10.1145/1065579.1065796]
• 8: A. Ghamarian, M. Geilen, S. Stuijk, T. Basten, A. Moonen, M. Bekooij, B. Theelen, and M. Mousavi. Throughput analysis of synchronous data flow graphs. In ACSD'06, Proc. (2006), IEEE.
• 9: R. Govindarajan , Guang R. Gao , Palash Desai, Minimizing Buffer Requirements under Rate-Optimal Schedule in Regular Dataflow Networks, Journal of VLSI Signal Processing Systems, v.31 n.3, p.207-229, July 2002 [doi>10.1023/A:1015452903532 ]
• 10: C.-T. Hwang et al. A formal approach to the scheduling problem in high-level synthesis. IEEE Trans. on Computer-Aided Design 10, 4 (1991), p. 464--475.
• 11: Edward Ashford Lee , David G. Messerschmitt, Static scheduling of synchronous data flow programs for digital signal processing, IEEE Transactions on Computers, v.36 n.1, p.24-35, Jan. 1987
• 12: Praveen K. Murthy , Shuvra S. Bhattacharyya, Shared memory implementations of synchronous dataflow specifications, Proceedings of the conference on Design, automation and test in Europe, p.404-410, March 27-30, 2000, Paris, France [doi>10.1145/343647.343809]
• 13: Qi Ning , Guang R. Gao, A novel framework of register allocation for software pipelining, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.29-42, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158519]
• 14: Hyunok Oh , Soonhoi Ha, Efficient code synthesis from extended dataflow graphs for multimedia applications, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA [doi>10.1145/513918.513990]
• 15: P. Poplavko , T. Basten , M. Bekooij , J. van Meerbergen , B. Mesman, Task-level timing models for guaranteed performance in multiprocessor networks-on-chip, Proceedings of the 2003 international conference on Compilers, architecture and synthesis for embedded systems, October 30-November 01, 2003, San Jose, California, USA [doi>10.1145/951710.951721]
• 16: S. Ritz et al. Scheduling for optimum data memory compaction in block diagram oriented software synthesis. In Int. Conf. on Acoustics, Speech, and Signal Processing, Proc. (1995), IEEE, p. 2651--2654.
• 17: Sandeep K. Shukla , Rajesh K. Gupta, A Model Checking Approach to Evaluating System Level Dynamic Power Management Policies for Embedded Systems, Proceedings of the Sixth IEEE International High-Level Design Validation and Test Workshop (HLDVT'01), p.53, December 07-09, 2001
• 18: Sundararajan Sriram , Shuvra S. Bhattacharyya, Embedded Multiprocessors: Scheduling and Synchronization, Marcel Dekker, Inc., New York, NY, 2000
• 19: S. Stuijk, M. Geilen, and T. Basten. Exploring trade-offs in buffer requirements and throughput constraints for synchronous dataflow graphs. Tech. Report, TU Eindhoven. http://www.es.ele.tue.nl/esreports/esr-2006-01.pdf
• 20: S. Stuijk, M. Geilen, and T. Basten. SDF3: SDF for free. In ACSD'06, Proc. (2006), IEEE. http://www.es.ele.tue.nl/sdf3

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Signal processing systems

General Terms:
Algorithms, Experimentation, Theory

Keywords:
buffering, optimization, synchronous dataflow, throughput