Systematic intermediate sequence removal for reduced memory accesses

ABSTRACT

Modern software applications are growing in complexity and demand very intensive use of data. Therefore, a wide variety of data structures are utilized to facilitate the storage and access to these vast amounts of computed information. Additionally, the need for reliable software design and the development of large applications following the object-oriented paradigm increase the amount of dynamic buffers and redundant accesses to the data stored in these buffers. In this paper, we propose a systematic, design optimization methodology to remove these intermediate dynamic buffers, thereby reducing the memory accesses of the targeted applications without altering the input-output behaviour of the algorithms. The reduction is focused on sequences and is especially relevant for embedded systems, which have limited on-chip communication bandwidth and the energy consumption of the memory subsystem is high, due to the energy consumption associated with each memory access. The effectiveness of the proposed methodology is assessed in a 3D reconstruction multimedia application and shows a significant reduction in memory accesses. In addition, the general trends for memory improvement and the scalability of our approach are supported as well by a parameterized benchmark set.

REFERENCES

• 1: Sitij Agrawal , William Thies , Saman Amarasinghe, Optimizing stream programs using linear state space analysis, Proceedings of the 2005 international conference on Compilers, architectures and synthesis for embedded systems, September 24-27, 2005, San Francisco, California, USA [doi>10.1145/1086297.1086315]
• 2: Deborah J. Armstrong, The quarks of object-oriented development, Communications of the ACM, v.49 n.2, p.123-128, February 2006 [doi>10.1145/1113034.1113040]
• 3: Luca Benini , Giovanni de Micheli, System-level power optimization: techniques and tools, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.5 n.2, p.115-192, April 2000 [doi>10.1145/335043.335044]
• 4: J. Beyer. Cbench: Compiler benchmark, 2006. http://cbench.sourceforge.net.
• 5: Gianfranco Bilardi , Keshav Pingali, Algorithms for computing the static single assignment form, Journal of the ACM (JACM), v.50 n.3, p.375-425, May 2003 [doi>10.1145/765568.765573]
• 6: Francky Catthoor , Eddy de Greef , Sven Suytack, Custom Memory Management Methodology: Exploration of Memory Organisation for Embedded Multimedia System Design, Kluwer Academic Publishers, Norwell, MA, 1998
• 7: E. De Greef. Storage Size Reduction for Multimedia Applications. PhD thesis, Katholieke Universiteit Leuven, January 1998.
• 8: D. Renz et al. Implementing lazy streams in c++. Morehead Electronic Journal of Applicable Mathematics, 4, May 2005.
• 9: Andrew Gill , John Launchbury , Simon L. Peyton Jones, A short cut to deforestation, Proceedings of the conference on Functional programming languages and computer architecture, p.223-232, June 09-11, 1993, Copenhagen, Denmark [doi>10.1145/165180.165214]
• 10: S. M. Inc. The collections framework, 2005. http://java.sun.com/docs/books/tutorial/collections/.
• 11: Mahmut Kandemir , J. Ramanujam , Alok Choudhary, Improving Cache Locality by a Combination of Loop and Data Transformations, IEEE Transactions on Computers, v.48 n.2, p.159-167, February 1999 [doi>10.1109/12.752657]
• 12: M. Leeman et al. Methodology for refinement and optimisation of dynamic memory management for embedded systems in multimedia applications. In SIPS, August 2003.
• 13: M. Leeman , D. A. Alonso, Intermediate variable elimination in a global context for a 3D multimedia application, Proceedings of the 2003 International Conference on Multimedia and Expo, p.73-76, July 06-09, 2003
• 14: Micron Technology, Inc. 128MSDRAM. http://www.micron.com/dram.
• 15: Steven S. Muchnick, Advanced compiler design and implementation, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 16: David R. Musser , Gilmer J. Derge , Atul Saini, STL tutorial and reference guide, second edition: C++ programming with the standard template library, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2001
• 17: Glassgow haskell compiler. http://www.haskell.org/ghc/.
• 18: P. R. Panda , F. Catthoor , N. D. Dutt , K. Danckaert , E. Brockmeyer , C. Kulkarni , A. Vandercappelle , P. G. Kjeldsberg, Data and memory optimization techniques for embedded systems, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.6 n.2, p.149-206, April 2001 [doi>10.1145/375977.375978]
• 19: Marc Pollefeys , Reinhard Koch , Maarten Vergauwen , Luc J. Van Gool, Metric 3D Surface Reconstruction from Uncalibrated Image Sequences, Proceedings of the European Workshop on 3D Structure from Multiple Images of Large-Scale Environments, p.139-154, June 06-07, 1998
• 20: Fabien Quilleré , Sanjay Rajopadhye, Optimizing memory usage in the polyhedral model, ACM Transactions on Programming Languages and Systems (TOPLAS), v.22 n.5, p.773-815, Sept. 2000 [doi>10.1145/365151.365152]
• 21: Praveen Raghavan , Andy Lambrechts , Murali Jayapala , Francky Catthoor , Diederik Verkest, Distributed loop controller architecture for multi-threading in uni-threaded VLIW processors, Proceedings of the conference on Design, automation and test in Europe: Proceedings, March 06-10, 2006, Munich, Germany
• 22: A. Santos. Compilation by Transformation in Non-Strict Functional Languages. PhD thesis, 1995.
• 23: SGI. Standard template library, 2006. http://www.sgi.com/tech/stl/.
• 24: Target jr, 2002. http://www.targetjr.org.
• 25: D. van Arkel et al. Fusion in practice. In In Implementation of Functional Languages, (LNCS), 2002.
• 26: Peter Vanbroekhoven , Gerda Janssens , Maurice Bruynooghe , Henk Corporaal , Francky Catthoor, Advanced copy propagation for arrays, Proceedings of the 2003 ACM SIGPLAN conference on Language, compiler, and tool for embedded systems, June 11-13, 2003, San Diego, California, USA
• 27: Philip Wadler, Deforestation: Transforming Programs to Eliminate Trees, Proceedings of the 2nd European Symposium on Programming, p.344-358, March 21-24, 1988