Implementation-Aware Model Analysis: The Case of Buffer-Throughput Tradeoff in Streaming Applications
Authors: 
Kamyar Mirzazad Barijough, 
Matin Hashemi, Volodymyr Khibin, 
Soheil GhiasiAuthors Info & Claims
Article No.: 11, Pages 1 - 10
Abstract
Models of computation abstract away a number of implementation details in favor of well-defined semantics. While this has unquestionable benefits, we argue that analysis of models solely based on operational semantics (implementation-oblivious analysis) is unfit to drive implementation design space exploration. Specifically, we study the tradeoff between buffer size and streaming throughput in applications modeled as synchronous data flow (SDF) graphs. We demonstrate the inherent inaccuracy of implementation-oblivious approach, which only considers SDF operational semantic. We propose a rigorous transformation, which equips the state of the art buffer-throughput tradeoff analysis technique with implementation awareness. Extensive empirical evaluation show that our approach results in significantly more accurate estimates in streaming throughput at the model level, while running two orders of magnitude faster than cycle-accurate simulation of implementations.
References
[1]
M. Ade, R. Lauwereins, and J. Peperstraete. Data memory minimisation for synchronous data flow graphs emulated on DSP-FPGA targets. Design Automation Conference, 1997.
[2]
M. A. Bamakhrama and T. P. Stefanov. On the hard-real-time scheduling of embedded streaming applications. Design Automation for Embedded Systems, 2012.
[3]
S. Bell et al. Tile64 - processor: A 64-core soc with mesh interconnect. International Solid-State Circuits Conference, 2008.
[4]
Benchmarks. http://sharif.edu/~matin and http://leps.ece.ucdavis.edu.
[5]
S. S. Bhattacharyya, P. K. Murthy, and E. A. Lee. Software Synthesis from Dataflow Graphs. Springer, 1996. ISBN 1461286018.
[6]
A. H. Ghamarian et al. Throughput analysis of synchronous data flow graphs. International Conference on Application of Concurrency to System Design, 2006.
[7]
Graphite. http://graphite.csail.mit.edu.
[8]
M. Hashemi and S. Ghiasi. Versatile task assignment for heterogeneous soft dual-processor platforms. IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems, 29(3), 2010.
[9]
M. Hashemi, M. H. Foroozannejad, S. Ghiasi, and C. Etzel. Formless: Scalable utilization of embedded manycores in streaming applications. International Conference on Languages, Compilers, Tools and Theory for Embedded Systems, pages 71--78, 2012.
[10]
M. Hashemi, M. H. Foroozannejad, and S. Ghiasi. Throughput-memory footprint trade-off in synthesis of streaming software on embedded multiprocessors. ACM Transactions on Embedded Computing Systems, 13(3), 2013.
[11]
E. A. Lee and D. G. Messerschmitt. Synchronous data flow. Proceedings of the IEEE, 75(9):1235--1245, 1987.
[12]
E. A. Lee and D. G. Messerschmitt. Static scheduling of synchronous data flow programs for digital signal processing. IEEE Transactions on Computers, 1987.
[13]
J. Miller et al. Graphite: A distributed parallel simulator for multicores. International Symposium on High-Performance Computer Architecture, January 2010.
[14]
A. Moonen et al. Practical and accurate throughput analysis with the cyclo static dataflow model. International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems, 2007.
[15]
O. M. Moreira and M. J. Bekooij. Self-timed scheduling analysis for real-time applications. EURASIP Journal on Advances in Signal Processing, 2007.
[16]
H. Oh and S. Ha. Fractional rate dataflow model for efficient code synthesis. Journal of VLSI signal processing systems for signal, image and video technology, 2004.
[17]
K. Parhi. VLSI Digital Signal Processing Systems: Design and Implementation. Wiley-Interscience, 2008. ISBN B000UGR930.
[18]
A. Pinto, A. Bonivento, A. L. Sangiovanni-Vincentelli, R. Passerone, and M. Sgroi. System level design paradigms: Platform-based design and communication synthesis. ACM Transactions on Design Automation of Electronic Systems, 11 (3):537--563, 2006.
[19]
S. Raghav, A. Marongiu, C. Pinto, M. Ruggiero, D. Atienza Alonso, and L. Benini. SIMinG-1k: A thousand-core simulator running on GPGPUs. Concurrency and Computation: Practice and Experience, 25(10):1443--1461, 2013.
[20]
A. Sangiovanni-Vincentelli and G. Martin. A vision for embedded systems: platform-based design and software methodology. Design Test of Computers, 18(6):23 --33, 2001.
[21]
SDF3. http://www.es.ele.tue.nl/sdf3.
[22]
S. Stuijk et al. Exploring trade-offs in buffer requirements and throughput constraints for synchronous dataflow graphs. Design Automation Conference, 2006.
[23]
W. Thies et al. Streamit: A language for streaming applications. International Conference on Compiler Construction, 2002.
[24]
Z. Xiao and B. Baas. 1080p h.264/avc baseline residual encoder for a fine-grained many-core system. IEEE Transactions on Circuits and Systems for Video Tech., 2011.
[25]
Y. Zhou and E. A. Lee. A causality interface for deadlock analysis in dataflow. International Conference on Embedded Software, pages 44--52, 2006.
Index Terms
- Implementation-Aware Model Analysis: The Case of Buffer-Throughput Tradeoff in Streaming Applications
Recommendations
Implementation-Aware Model Analysis: The Case of Buffer-Throughput Tradeoff in Streaming Applications
LCTES'15: Proceedings of the 16th ACM SIGPLAN/SIGBED Conference on Languages, Compilers and Tools for Embedded Systems 2015 CD-ROMModels of computation abstract away a number of implementation details in favor of well-defined semantics. While this has unquestionable benefits, we argue that analysis of models solely based on operational semantics (implementation-oblivious analysis) ...
Worst-Case Throughput Analysis of SDF-Based Parametrized Dataflow
DSD '15: Proceedings of the 2015 Euromicro Conference on Digital System DesignDynamic dataflow models of computation (MoCs) have been introduced to provide designers with enough expressive power to capture increasing levels of dynamism in modern streaming applications. Among dynamic dataflow MoCs, parametrized dataflow MoCs hold ...
Fractional Rate Dataflow Model for Efficient Code Synthesis
Automatic code synthesis from dataflow program graphs is a promising high-level design methodology for rapid prototyping of multimedia embedded systems. Memory efficient code synthesis from dataflow models has been an active research subject to reduce ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
May 2015
141 pages
June 2015149 pagesISBN:9781450332576DOI:10.1145/2670529- General Chair:
- Sam H. Noh,
- Program Chairs:
- Sebastian Fischmeister,
- Jason Xue
Copyright © 2015 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
Publication History
Published: 04 June 2015
Published in SIGPLAN Volume 50, Issue 5
Check for updates
Author Tags
Qualifiers
- Tutorial
- Research
- Refereed limited
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations5Total Citations
- 227Total Downloads
- Downloads (Last 12 months)2
- Downloads (Last 6 weeks)0
Reflects downloads up to 11 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in