Exploiting shared scratch pad memory space in embedded multiprocessor systems

ABSTRACT

In this paper, we present a compiler strategy to optimize data accesses in regular array-intensive applications running on embedded multiprocessor environments. Specifically, we propose an optimization algorithm that targets the reduction of extra off-chip memory accesses caused by inter-processor communication. This is achieved by increasing the application-wide reuse of data that resides in the scratch-pad memories of processors. Our experimental results obtained on four array-intensive image processing applications indicate that exploiting inter-processor data sharing can reduce the energy-delay product by as much as 33.8% (and 24.3% on average) on a four-processor embedded system. The results also show that the proposed strategy is robust in the sense that it gives consistently good results over a wide range of several architectural parameters.

REFERENCES

• 1: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 2: S. Amarasinghe, J. Anderson, M. Lam, and C. Tseng. The SUIF compiler for scalable parallel machines. In Proc. 7th SIAM Conference on Parallel Processing for Scientific Computing, 1995.
• 3: Utpal K. Banerjee, Dependence Analysis for Supercomputing, Kluwer Academic Publishers, Norwell, MA, 1988
• 4: Luca Benini , Alberto Macii , Enrico Macii , Massimo Poncino, Increasing Energy Efficiency of Embedded Systems by Application-Specific Memory Hierarchy Generation, IEEE Design & Test, v.17 n.2, p.74-85, April 2000 [doi>10.1109/54.844336]
• 5: Blue Wave Systems. http://www.bluews.com/
• 6: Rajesh Bordawekar , Alok Choudhary , J. Ramanujam, Automatic optimization of communication in compiling out-of-core stencil codes, Proceedings of the 10th international conference on Supercomputing, p.366-373, May 25-28, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237578.237638]
• 7: 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
• 8: Anantha P. Chandrakasan , William J. Bowhill , Frank Fox, Design of High-Performance Microprocessor Circuits, Wiley-IEEE Press, 2000
• 9: Dinero IV Trace-Driven Uniprocessor Cache Simulator. URL: http://www.cs.wisc.edu/~markhill/DineroIV/
• 10: Jennifer Eyre , Jeff Bier, DSP Processors Hit the Mainstream, Computer, v.31 n.8, p.51-59, August 1998 [doi>10.1109/2.707617]
• 11: 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]
• 12: R. Gonzales and M. Horowitz. Energy dissipation in general purpose microprocessors. IEEE Journal of Solid-State Circuits, pages 1277--1284, Sep. 1996
• 13: M. Kandemir , N. Vijaykrishnan , M. J. Irwin , W. Ye, Influence of compiler optimizations on system power, Proceedings of the 37th conference on Design automation, p.304-307, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337425]
• 14: M. Kandemir , J. Ramanujam , J. Irwin , N. Vijaykrishnan , I. Kadayif , A. Parikh, Dynamic management of scratch-pad memory space, Proceedings of the 38th conference on Design automation, p.690-695, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.379049]
• 15: David J. Kolson , Alexandru Nicolau , Nikil Dutt, Minimization of memory traffic in high-level synthesis, Proceedings of the 31st annual conference on Design automation, p.149-154, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196316]
• 16: Mobile Computing Devices: A New Era in Personal Computing, August 2000. Computer Market Dynamics. Report Number CMC00-005MC.
• 17: Preeti Ranjan Panda , Nikil D. Dutt , Alexandru Nicolau, Efficient Utilization of Scratch-Pad Memory in Embedded Processor Applications, Proceedings of the 1997 European conference on Design and Test, p.7, March 17-20, 1997
• 18: Preeti Ranjan Panda , Nikil D. Dutt , Alexandru Nicolau, Architectural exploration and optimization of local memory in embedded systems, Proceedings of the 10th international symposium on System synthesis, p.90-97, September 17-19, 1997, Antwerp, Belgium
• 19: Wen-Tsong Shiue , Chaitali Chakrabarti, Memory exploration for low power, embedded systems, Proceedings of the 36th ACM/IEEE conference on Design automation, p.140-145, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309902]
• 20: N. Vijaykrishnan , M. Kandemir , M. J. Irwin , H. S. Kim , W. Ye, Energy-driven integrated hardware-software optimizations using SimplePower, Proceedings of the 27th annual international symposium on Computer architecture, p.95-106, June 2000, Vancouver, British Columbia, Canada
• 21: Lei Wang , Waibhav Tembe , Santosh Pande, A Framework for Loop Distribution on Limited On-Chip Memory Processors, Proceedings of the 9th International Conference on Compiler Construction, p.141-156, March 25-April 02, 2000
• 22: Michael Joseph Wolfe , Carter Shanklin , Leda Ortega, High Performance Compilers for Parallel Computing, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 23: Y. Zhang, Y. Chen, W. Ye, and M. J. Irwin. System-level interconnect power modeling. In Proc. the 11th International ASIC Conference, 1998.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

General Terms:
Algorithms, Management, Performance

Keywords:
access patterns, compiler optimizations, data tiles, embedded multiprocessors, energy consumption, memories, scratch pad