Adaptive Source-Level Data Assignment to Dual Memory Banks
Article No.: 20, Pages 1 - 22
Abstract
Dual memory banks provide extra memory bandwidth to DSP applications and enable simultaneous access to two operands if the data is partitioned appropriately. Fully automated and compiler integrated approaches to data partitioning and memory bank assignment have, however, found little acceptance by DSP software developers. In this article we present a novel source-level approach that is more programmer friendly. Our scheme is based on soft graph coloring and highly adaptive heuristics generated by genetic programming. We have evaluated our scheme on an Analog Devices TigerSHARC TS-101 DSP and achieved speedups of up to 57% on 13 UTDSP benchmarks.
References
[1]
ACE. 1998. DSP-C, an extension to ISO/IEC IS 9899:1990. Tech. rep., ACE Associated Compiler Experts bv.
[2]
Beemster, M., van Someren, H., Wakker, W., and Banks, W. 2005. The Embedded C extension to C. http://www.ddj.com/cpp/184401988.
[3]
Bhattacharyya, S., Leupers, R., and Marwedel, P. 2000. Software synthesis and code generation for signal processing systems. IEEE Trans. Circ. Syst. II: Anal. Dig. Signal Process. 47, 9.
[4]
Cavazos, J. and O’Boyle, M. F. P. 2005. Automatic tuning of inlining heuristics. In Proceedings of the ACM/IEEE Conference on Supercomputing (SC’05). IEEE Computer Society, Los Alamitos, CA, 14.
[5]
Cooper, K. D. and Waterman, T. 2003. Investigating adaptive compilation using the MIPSpro compiler. In Proceedings of the Symposium of the Los Alamos Computer Science Institute.
[6]
Cramer, N. L. 1985. A representation for the adaptive generation of simple sequential programs. In Proceedings of the International Conference on Genetic Algorithms and Their Applications (ICGA’85). 183--187.
[7]
Falk, H. and Verma, M. 2004. Combined data partitioning and loop nest splitting for energy consumption minimization. In Software and Compilers for Embedded Systems, Lecture Notes in Computer Science, vol. 3199, Springer, 137--151.
[8]
Fitzpatrick, S. and Meertens, L. 2001. An experimental assessment of a stochastic, anytime, decentralized, soft colourer for sparse graphs. In Proceedings of the International Symposium on Stochastic Algorithms (SAGA’01). 49--64.
[9]
Frederiksen, A., Christiansen, R., Bier, J., and Koch, P. 2000. An evaluation of compiler-processor interaction for DSP applications. In Proceedings of the 34th IEEE Asilomar Conference on Signals, Systems, and Computers.
[10]
Fursin, G., O’Boyle, M., and Knijnenburg, P. 2002. Evaluating iterative compilation. In Proceedings of the 15th Workshop on Languages and Compilers for Parallel Computing.
[11]
Gréwal, G., Coros, S., Morton, A., and Banerji, D. 2006. A multi-objective integer linear program for memory assignment in the DSP domain. In Proceedings of the IEEE Workshop on Memory Performance Issues (WMPI’06). 21--28.
[12]
Gréwal, G., Wilson, T., and Morton, A. 2003. An EGA approach to the compile-time assignment of data to multiple memories in digital-signal processors. SIGARCH Comput. Archit. News 31, 1, 49--59.
[13]
JTC1/SC22/WG14. 2004. Programming languages - C - extensions to support embedded processors. Tech. rep., ISO/IEC.
[14]
Ko, M.-Y. and Bhattacharyya, S. S. 2003. Data partioning for DSP software synthesis. In Proceedings of the International Workshop on Software and Compilers for Embedded Systems (SCOPES’03). 344--358.
[15]
Koza, J. 1992. Genetic Programming: On the Programming of Computers by Means of Natural Selection. The MIT Press.
[16]
Lee, C. G. 1998. UTDSP benchmark suite. http://www.eecg.toronto.edu/~corinna/DSP/infrastructure/UTDSP.html.
[17]
Leupers, R. 1998. Novel code optimization techniques for DSPs. In Proceedings of the 2nd European DSP Education and Research Conference.
[18]
Leupers, R. and Kotte, D. 2001. Variable partioning for dual memory bank DSPs. In Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP’01). Vol. 2. 1121--1124.
[19]
Luke, S. and Panait, L. 2002. Lexicographic parsimony pressure. In Proceedings of the Genetic and Evolutionary Computation Conference. 829--836.
[20]
Murray, A. and Franke, B. 2008. Fast source-level data assignment to dual memory banks. In Proceedings of the 11th International Workshop on Software and Compilers for Embedded Systems (SCOPES’08). 43--52.
[21]
Murray, A. and Franke, B. 2009. Using genetic programming for source-level data assignment to dual memory banks. In Proceedings of the 3rd Workshop on Statistical and Machine Learning Approaches to Architectures and Compilation (SMART’09). 75--89.
[22]
Rugina, R. and Rinard, M. 1999. Pointer analysis for multithreaded programs. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implemenation. 77--90.
[23]
Saghir, M. A. R., Chow, P., and Lee, C. G. 1996. Exploiting dual data-memory banks in digital signal processors. In Proceedings of the 7th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS-VII). 234--243.
[24]
Sipkovà, V. 2003. Efficient variable allocation to dual memory banks of DSPs. In Proceedings of the 7th International Workshop on Software and Compilers for Embedded Systems (SCOPES’03). 359--372.
[25]
Stephenson, M., Martin, M., O’Reilly, U.-M., and Amarasinghe, S. 2003a. Meta optimization: Improving compiler heuristics with machine learning. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implemenation (PLDI’03). 77--90.
[26]
Stephenson, M., O’Reilly, U.-M., Martin, M. C., and Amarasinghe, S. 2003b. Genetic programming applied to compiler heuristic optimization. In Proceedings of the 6th European Conference on Genetic Programming.
[27]
Timmer, A., Strik, M., van Meerberger, J., and Jess, J. 1995. Conflict modelling and instruction scheduling in code generation for in-house DSP cores. In Proceedings of the Design Automation Conference (DAC’95).
[28]
Wilson, R. P., French, R. S., Wilson, C. S., Amarasinghe, S. P., Anderson, J. M., Tjiang, S. W. K., Liao, S.-W., Tseng, C.-W., Hall, M. W., Lam, M. S., and Hennessy, J. L. 1994. SUIF: An infrastructure for research on parallelizing and optimizing compilers. SIGPLAN Not. 29, 12, 31--37.
Index Terms
- Adaptive Source-Level Data Assignment to Dual Memory Banks
Recommendations
Combining source-to-source transformations and processor instruction set extensions for the automated design-space exploration of embedded systems
LCTES '07: Proceedings of the 2007 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systemsIndustry's demand for flexible embedded solutions providing high performance and short time-to-market has led to the development of configurable and extensible processors. These pre-verified application-specific processors build on proven baseline cores ...
Combining source-to-source transformations and processor instruction set extensions for the automated design-space exploration of embedded systems
Proceedings of the 2007 LCTES conferenceIndustry's demand for flexible embedded solutions providing high performance and short time-to-market has led to the development of configurable and extensible processors. These pre-verified application-specific processors build on proven baseline cores ...
Fast source-level data assignment to dual memory banks
SCOPES '08: Proceedings of the 11th international workshop on Software & compilers for embedded systemsDue to their streaming nature memory bandwidth is critical for most digital signal processing applications. To accommodate for these bandwidth requirements digital signal processors are typically equipped with dual memory banks that enable simultaneous ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © 2012 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
Publication History
Published: 01 June 2012
Accepted: 01 April 2010
Revised: 01 December 2009
Received: 01 June 2009
Published in TECS Volume 11S, Issue 1
Check for updates
Author Tags
Qualifiers
- Research-article
- Research
- Refereed
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 177Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 16 Nov 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