Reducing memory requirements of nested loops for embedded systems

ABSTRACT

Most embedded systems have limited amount of memory. In contrast, the memory requirements of code (in particular loops) running on embedded systems is significant. This paper addresses the problem of estimating the amount of memory needed for transfers of data in embedded systems. The problem of estimating the region associated with a statement or the set of elements referenced by a statement during the execution of the entire set of nested loops is analyzed. Aquantitative analysis of the number of elements referenced is presented; exact expressions for uniformly generated references and a close upper and lower bound for non-uniformly generated references are derived. In addition to presenting an algorithm that computes the total memory required, we discuss the effect of transformations on the lifetimes of array variables, i.e., the time between the first and last accesses to a given array location. A detailed analysis on the effect of unimodular transformations on data locality including the calculation of the maximum window size is discussed. The termmaximum window sizeis introduced and quantitative expressions are derived to compute the window size. The smaller the value of the maximum window size, the higher the amount of data locality in the loop.

REFERENCES

• 1: Florin Balasa , Francky Catthoor , Hugo De Man, Background memory area estimation for multidimensional signal processing systems, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.3 n.2, p.157-172, June 1995 [doi>10.1109/92.386218]
• 2: 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
• 3: Philippe Clauss, Counting solutions to linear and nonlinear constraints through Ehrhart polynomials: applications to analyze and transform scientific programs, Proceedings of the 10th international conference on Supercomputing, p.278-285, May 25-28, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237578.237617]
• 4: Eddy de Greef , Francky Catthoor , Hugo de Man, Array Placement for Storage Size Reduction in Embedded Multimedia Systems, Proceedings of the IEEE International Conference on Application-Specific Systems, Architectures and Processors, p.66, July 14-16, 1997
• 5: C. Eisenbeis, W. Jalby, D. Windheiser and F. Bodin. A strategy for array management in local memory. Advances in Languages and Compilers for Parallel Computing, MIT Press, pp. 130-151, 1991.
• 6: Z. Fang and M. Lu. A solution to cache thrashing problem in RISC based parallel processing systems. Proc. 1991 International Conf. Parallel Processing, August 1991.
• 7: Jeanne Ferrante , Vivek Sarkar , W. Thrash, On Estimating and Enhancing Cache Effectiveness, Proceedings of the Fourth International Workshop on Languages and Compilers for Parallel Computing, p.328-343, August 07-09, 1991
• 8: K. Gallivan , W. Jalby , D. Gannon, On the problem of optimizing data transfers for complex memory systems, Proceedings of the 2nd international conference on Supercomputing, p.238-253, June 1988, St. Malo, France [doi>10.1145/55364.55388]
• 9: Dennis Gannon , William Jalby , Kyle Gallivan, Strategies for cache and local memory management by global program transformation, Journal of Parallel and Distributed Computing, v.5 n.5, p.587-616, October 1988 [doi>10.1016/0743-7315(88)90014-7]
• 10: F. Irigoin , R. Triolet, Supernode partitioning, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.319-329, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73588]
• 11: Ken Kennedy , Kathryn S. McKinley, Optimizing for parallelism and data locality, Proceedings of the 6th international conference on Supercomputing, p.323-334, July 19-24, 1992, Washington, D. C., United States [doi>10.1145/143369.143427]
• 12: Monica D. Lam , Edward E. Rothberg , Michael E. Wolf, The cache performance and optimizations of blocked algorithms, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.63-74, April 08-11, 1991, Santa Clara, California, United States
• 13: Chunho Lee , Miodrag Potkonjak , William H. Mangione-Smith, MediaBench: a tool for evaluating and synthesizing multimedia and communicatons systems, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.330-335, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 14: Wei Li , Keshav Pingali, A Singular Loop Transformation Framework Based on Non-Singular Matrices, Proceedings of the 5th International Workshop on Languages and Compilers for Parallel Computing, p.391-405, August 03-05, 1992
• 15: William Pugh, Counting solutions to Presburger formulas: how and why, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.121-134, June 20-24, 1994, Orlando, Florida, United States
• 16: Ashok Sudarsanam , Sharad Malik, Simultaneous reference allocation in code generation for dual data memory bank ASIPs, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.5 n.2, p.242-264, April 2000 [doi>10.1145/335043.335047]
• 17: M. E. Wolf , M. S. Lam, A Loop Transformation Theory and an Algorithm to Maximize Parallelism, IEEE Transactions on Parallel and Distributed Systems, v.2 n.4, p.452-471, October 1991 [doi>10.1109/71.97902]
• 18: Michael E. Wolf , Monica S. Lam, A data locality optimizing algorithm, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.30-44, June 24-28, 1991, Toronto, Ontario, Canada
• 19: Michael Joseph Wolfe , Carter Shanklin , Leda Ortega, High Performance Compilers for Parallel Computing, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 20: Ying Zhao , Sharad Malik, Exact memory size estimation for array computations without loop unrolling, Proceedings of the 36th ACM/IEEE conference on Design automation, p.811-816, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.310074]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

Additional Classification:
  C. Computer Systems Organization

  J. Computer Applications
  J.2 PHYSICAL SCIENCES AND ENGINEERING
      Subjects: Electronics

General Terms:
Design, Experimentation, Measurement, Performance, Theory