More Web Proxy on the site http://driver.im/

research-article

Efficient simulation of critical synchronous dataflow graphs

Authors:

Shuvra S. Bhattacharyya,

Suren Ramasubbu,

José Luis PinoAuthors Info & Claims

ACM Transactions on Design Automation of Electronic Systems (TODAES), Volume 12, Issue 3

Article No.: 21, Pages 1 - 28

https://doi.org/10.1145/1255456.1255458

Published: 22 May 2008 Publication History

Abstract

System-level modeling, simulation, and synthesis using electronic design automation (EDA) tools are key steps in the design process for communication and signal processing systems, and the synchronous dataflow (SDF) model of computation is widely used in EDA tools for these purposes. Behavioral representations of modern wireless communication systems typically result in critical SDF graphs: These consist of hundreds of components (or more) and involve complex intercomponent connections with highly multirate relationships (i.e., with large variations in average rates of data transfer or component execution across different subsystems). Simulating such systems using conventional SDF scheduling techniques generally leads to unacceptable simulation time and memory requirements on modern workstations and high-end PCs. In this article, we present a novel simulation-oriented scheduler (SOS) that strategically integrates several techniques for graph decomposition and SDF scheduling to provide effective, joint minimization of time and memory requirements for simulating critical SDF graphs. We have implemented SOS in the advanced design system (ADS) from Agilent Technologies. Our results from this implementation demonstrate large improvements in simulating real-world, large-scale, and highly multirate wireless communication systems (e.g., 3GPP, Bluetooth, 802.16e, CDMA 2000, XM radio, EDGE, and Digital TV).

References

[1]

Ade, M., Lauwereins, R., and Peperstraete, J. A. 1997. Data memory minimization for synchronous data flow graphs emulated on DSP-FPGA targets. In Proceedings of the Design Automation Conference.

Digital Library

[2]

Bhattacharyya, S. S., Leupers, R., and Marwedel, P. 2000. Software synthesis and code generation for DSP. IEEE Trans. Circ. Syst. II: Analog Digital Signal Process. 47, 9 (Sept.), 849--875.

[3]

Bhattacharyya, S. S., Murthy, P. K., and Lee, E. A. 1996. Software Synthesis from Dataflow Graphs. Kluwer Academic, Hingham, MA.

Digital Library

[4]

Bilsen, G., Engels, M., Lauwereins, R., and Peperstraete, J. A. 1996. Cyclo-Static dataflow. IEEE Trans. Signal Process. 44, 2 (Feb.), 397--408.

Digital Library

[5]

Buck, J. T. 1993. Scheduling dynamic dataflow graphs with bounded memory using the token flow model. Ph.D. thesis UCB/ERL 93/69, Department of EECS, U. C. Berkeley.

Digital Library

[6]

Buck, J. T., Ha, S., Lee, E. A., and Messerschmitt, D. G. 1994. Ptolemy: A framework for simulating and prototyping heterogeneous systems. Int. J. Comput. Simul. 4, 155--182.

[7]

Buck, J. T. and Vaidyanathan, R. 2000. Heterogeneous modeling and simulation of embedded systems in El Greco. In Proceedings of the International Workshop on Hardware/Software Codesign (San Diego, CA).

Digital Library

[8]

Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. 2001. Introduction to Algorithms, 2nd ed. The MIT Press, Cambridge, MA.

Digital Library

[9]

Cubric, M. and Panangaden, P. 1993. Minimal memory schedules for dataflow networks. In Proceedings of the International Conference on Concurrency Theory (CONCUR), 368--383.

Digital Library

[10]

Eker, J., Janneck, J. W., Lee, E. A., Liu, J., Liu, X., Ludvig, J., Neuendorffer, S., Sachs, S., and Xiong, Y. 2003. Taming heterogeneity---The Ptolemy approach. Proc. IEEE 91, 1 (Jan.), 127--144.

[11]

Geilen, M., Basten, T., and Stuijk, S. 2005. Minimising buffer requirements of synchronous dataflow graphs with model checking. In Proceedings of the Design Automation Conference (Anaheim, CA), 819--824.

Digital Library

[12]

Hsu, C. and Bhattacharyya, S. S. 2007. Cycle-Breaking techniques for scheduling synchronous dataflow graphs. Tech. Rep. UMIACS-TR-2007-12, Institute for Advanced Computer Studies, University of Maryland at College Park.

[13]

Hsu, C., Ko, M., and Bhattacharyya, S. S. 2005. Software synthesis from the dataflow interchange format. In Proceedings of the International Workshop on Software and Compilers for Embedded Systems (Dallas, TX), 37--49.

Digital Library

[14]

Hsu, C., Ramasubbu, S., Ko, M., Pino, J. L., and Bhattacharyya, S. S. 2006. Efficient simulation of critical synchronous dataflow graphs. In Proceedings of the Design Automation Conference (San Francisco, CA), 893--898.

Digital Library

[15]

Ko, M., Murthy, P. K., and Bhattacharyya, S. S. 2004. Compact procedural implementation in DSP software synthesis through recursive graph decomposition. In Proceedings of the International Workshop on Software and Compilers for Embedded Systems (Amsterdam, The Netherlands), 47--61.

[16]

Lauwereins, R., Engels, M., Ade, M., and Peperstraete, J. A. 1995. Grape-II: A system-level prototyping environment for DSP applications. IEEE Comput. Mag. 28, 2 (Feb.), 35--43.

Digital Library

[17]

Lee, E. A., Ho, W. H., Goei, E., Bier, J., and Bhattacharyya, S. S. 1989. Gabriel: A design environment for DSP. IEEE Trans. Acoustics, Speech, Signal Process. 37, 11 (Nov.), 1751--1762.

[18]

Lee, E. A. and Messerschmitt, D. G. 1987. Synchronous dataflow. Proc. IEEE 75, 9 (Sept.), 1235--1245.

[19]

Marwedel, P. and Goossens, G., Eds. 1995. Code Generation for Embedded Processors. Kluwer Academic, Hinghan, MA.

Digital Library

[20]

Murthy, P. K. and Bhattacharyya, S. S. 2006. Memory Management for Synthesis of DSP Software. CRC Press, Baca Raton, FL.

Digital Library

[21]

Murthy, P. K., Bhattacharyya, S. S., and Lee, E. A. 1997. Joint minimization of code and data for synchronous dataflow programs. J. Formal Methods Syst. Des. 11, 1 (Jul.), 41--70.

Digital Library

[22]

Oh, H., Dutt, N., and Ha, S. 2006. Memory optimal single appearance schedule with dynamic loop count for synchronous dataflow graphs. In Proceedings of the Asia and South Pacific Design Automation Conference (Yokohama, Japan), 497--502.

Digital Library

[23]

Patel, H. D. and Shukla, S. K. 2004. SystemC Kernel Extensions for Heterogeneous System Modeling. Kluwer Academic, Hingham, MA.

Digital Library

[24]

Pino, J. L. and Kalbasi, K. 1998. Cosimulating synchronous DSP applications with analog RF circuits. In Proceedings of the IEEE Asilomar Conference on Signals, Systems, and Computers (Pacific Grove, CA).

[25]

Robbins, C. B. 2002. Autocoding toolset software tools for automatic generation of parallel application software. Tech. Rep., Management Communications and Control, Inc.

[26]

Stefanov, T., Zissulescu, C., Turjan, A., Kienhuis, B., and Deprettere, E. 2004. System design using Kahn process networks: The Compaan/Laura approach. In Proceedings of the Design, Automation and Test in Europe Conference.

Digital Library

[27]

Sung, W., Oh, M., Im, C., and Ha, S. 1997. Demonstration of hardware software codesign workflow in PeaCE. In Proceedings of the International Conference on VLSI and CAD.

Cited By

Rubattu CPalumbo FBhattacharyya SPelcat M(2022)PathTracer: Understanding Response Time of Signal Processing Applications on Heterogeneous MPSoCsACM Transactions on Modeling and Performance Evaluation of Computing Systems10.1145/35130036:4(1-30)Online publication date: 1-Apr-2022
https://dl.acm.org/doi/10.1145/3513003
Rubattu CPalumbo FBhattacharyya SPelcat M(2021)PathTracing: Raising the Level of Understanding of Processing Latency in Heterogeneous MPSoCsProceedings of the 2021 Drone Systems Engineering and Rapid Simulation and Performance Evaluation: Methods and Tools Proceedings10.1145/3444950.3447282(46-50)Online publication date: 18-Jan-2021
https://dl.acm.org/doi/10.1145/3444950.3447282
Liu YBarford LBhattacharyya S(2018)Generalized Graph Connections for Dataflow Modeling of DSP Applications2018 IEEE International Workshop on Signal Processing Systems (SiPS)10.1109/SiPS.2018.8598305(1-6)Online publication date: Oct-2018
https://doi.org/10.1109/SiPS.2018.8598305
Show More Cited By

Index Terms

Efficient simulation of critical synchronous dataflow graphs
1. Software and its engineering
  1. Software creation and management
    1. Designing software
      1. Software implementation planning
        Software design techniques
    2. Software development process management

Recommendations

Efficient simulation of critical synchronous dataflow graphs
DAC '06: Proceedings of the 43rd annual Design Automation Conference

Simulation and verification using electronic design automation (EDA) tools are key steps in the design process for communication and signal processing systems. The synchronous dataflow (SDF) model of computation is widely used in EDA tools for system ...
Multithreaded simulation for synchronous dataflow graphs
DAC '08: Proceedings of the 45th annual Design Automation Conference

Synchronous dataflow (SDF) has been successfully used in design tools for system-level simulation of wireless communication systems. Modern wireless communication standards involve large complexity and highly-multirate behavior, and typically result in ...
A comparison of synchronous and cycle-static dataflow
ASILOMAR '95: Proceedings of the 29th Asilomar Conference on Signals, Systems and Computers (2-Volume Set)

We compare synchronous dataflow (SDF) and cyclo-static dataflow (CSDF), which are each special cases of a model of computation we call dataflow process networks. In SDF actors have static firing rules: they consume and produce a fixed number of data ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Design Automation of Electronic Systems

ACM Transactions on Design Automation of Electronic Systems Volume 12, Issue 3

August 2007

427 pages

ISSN:1084-4309

EISSN:1557-7309

DOI:10.1145/1255456

Issue’s Table of Contents

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Journal Family

ACM Journals for the Design of Smart and Connected Systems

Publication History

Published: 22 May 2008

Accepted: 01 March 2007

Revised: 01 March 2007

Received: 01 September 2006

Published in TODAES Volume 12, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
395
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)1

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Rubattu CPalumbo FBhattacharyya SPelcat M(2022)PathTracer: Understanding Response Time of Signal Processing Applications on Heterogeneous MPSoCsACM Transactions on Modeling and Performance Evaluation of Computing Systems10.1145/35130036:4(1-30)Online publication date: 1-Apr-2022
https://dl.acm.org/doi/10.1145/3513003
Rubattu CPalumbo FBhattacharyya SPelcat M(2021)PathTracing: Raising the Level of Understanding of Processing Latency in Heterogeneous MPSoCsProceedings of the 2021 Drone Systems Engineering and Rapid Simulation and Performance Evaluation: Methods and Tools Proceedings10.1145/3444950.3447282(46-50)Online publication date: 18-Jan-2021
https://dl.acm.org/doi/10.1145/3444950.3447282
Liu YBarford LBhattacharyya S(2018)Generalized Graph Connections for Dataflow Modeling of DSP Applications2018 IEEE International Workshop on Signal Processing Systems (SiPS)10.1109/SiPS.2018.8598305(1-6)Online publication date: Oct-2018
https://doi.org/10.1109/SiPS.2018.8598305
Sun JAjwani DNicholson PSala AParthasarathy SFox PMcGuinness DPoirer LBoldi PKinder-Kurlanda K(2017)Breaking Cycles In Noisy HierarchiesProceedings of the 2017 ACM on Web Science Conference10.1145/3091478.3091495(151-160)Online publication date: 25-Jun-2017
https://dl.acm.org/doi/10.1145/3091478.3091495
Leong CBexiga VTeixeira JBugalho RFerreira MRodrigues PSilva JLousã PVarela JTeixeira I(2012)Automatic adjustment of a medical imaging data acquisition system to unknown delays in the input communication channelsAnalog Integrated Circuits and Signal Processing10.1007/s10470-011-9780-970:2(213-227)Online publication date: 1-Feb-2012
https://dl.acm.org/doi/10.1007/s10470-011-9780-9
Hsu CPino JBhattacharyya S(2011)Multithreaded Simulation for Synchronous Dataflow GraphsACM Transactions on Design Automation of Electronic Systems10.1145/1970353.197035816:3(1-23)Online publication date: 1-Jun-2011
https://dl.acm.org/doi/10.1145/1970353.1970358
Girão GBarcelos DWagner F(2011)Performance and Energy Evaluation of Memory Organizations in NoC-Based MPSoCs under Latency and Task MigrationVLSI-SoC: Technologies for Systems Integration10.1007/978-3-642-23120-9_4(56-80)Online publication date: 2011
https://doi.org/10.1007/978-3-642-23120-9_4
Hsu CPino JBhattacharyya SFix L(2008)Multithreaded simulation for synchronous dataflow graphsProceedings of the 45th annual Design Automation Conference10.1145/1391469.1391553(331-336)Online publication date: 8-Jun-2008
https://dl.acm.org/doi/10.1145/1391469.1391553

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents