Dynamic scratch-pad memory management for irregular array access patterns

ABSTRACT

There exist many embedded applications such as those executing on set-top boxes, wireless base stations, HDTV, and mobile handsets that are structured as nested loops and benefit significantly from a software managed memory. Prior work on scratchpad memories (SPMs) focused primarily on applications with regular data access patterns. Unfortunately, some embedded applications do not fit in this category and consequently conventional SPM management schemes will fail to produce the best results for them. In this work, we propose a novel compilation strategy for data SPMs for embedded applications that exhibit irregular data access patterns. Our scheme divides the task of optimization between compiler and runtime. The compiler processes each loop nest and insert code to collect information at runtime. Then, the code is modified in such a fashion that, depending on the collected information, it dynamically chooses to use or not to use the data SPM for a given set of accesses to irregular arrays. Our results indicate that this approach is very successful with the applications that have irregular patterns and improves their execution cycles by about 54% over a state-of-the-art SPM management technique and 23% over the conventional cache memories. Also, the additional code size overhead incurred by our approach is less than 5% for all the applications tested.

REFERENCES

• 1: Arm11 family. http://www.arm.com/products/CPUs/families/ARM11Family.html.
• 2: Intel application processors. http://developer.intel.com/design/pca/applicationsprocessors/.
• 3: M. J. Absar , F. Catthoor, Compiler-Based Approach for Exploiting Scratch-Pad in Presence of Irregular Array Access, Proceedings of the conference on Design, Automation and Test in Europe, p.1162-1167, March 07-11, 2005 [doi>10.1109/DATE.2005.97]
• 4: S. P. Amarasinghe, J. M. Anderson, M. S. Lam, and C. W. Tseng. The SUIF compiler for scalable parallel machines. In the Seventh SIAM Conference on Parallel Processing for Scientific Computing, Feb. 1995.
• 5: T. M. Austin and D. Burger. The simplescalar architectural research tool set. http://www.cs.wisc.edu/~mscalar/simplescalar.html.
• 6: Energy and Performance Improvements in Microprocessor Design Using a Loop Cache, Proceedings of the 1999 IEEE International Conference on Computer Design, p.378, October 10-13, 1999
• 7: 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 ]
• 8: P. Francesco, P. Marchal, D. Atienza, L. Benini, F. Catthoor, and J. M. Mendias. An integrated hardware/software approach for runtime scratchpad management. pages 238--243, 2004.
• 9: Erik G. Hallnor , Steven K. Reinhardt, A fully associative software-managed cache design, Proceedings of the 27th annual international symposium on Computer architecture, p.107-116, June 2000, Vancouver, British Columbia, Canada
• 10: 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]
• 11: Lea Hwang Lee , Bill Moyer , John Arends, Instruction fetch energy reduction using loop caches for embedded applications with small tight loops, Proceedings of the 1999 international symposium on Low power electronics and design, p.267-269, August 16-17, 1999, San Diego, California, United States [doi>10.1145/313817.313944]
• 12: 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
• 13: John W. Sias , Hillery C. Hunter , Wen-mei W. Hwu, Enhancing loop buffering of media and telecommunications applications using low-overhead predication, Proceedings of the 34th annual ACM/IEEE international symposium on Microarchitecture, December 01-05, 2001, Austin, Texas
• 14: S. Steinke , L. Wehmeyer , B. Lee , P. Marwedel, Assigning Program and Data Objects to Scratchpad for Energy Reduction, Proceedings of the conference on Design, automation and test in Europe, p.409, March 04-08, 2002
• 15: L. Wang, W. Tembe, and S. Pande. Optimizing on-chip memory usage through loop restructuring for embedded processors. In 9th International Conference on Compiler Construction, Mar. 2000.
• 16: Michael Joseph Wolfe , Carter Shanklin , Leda Ortega, High Performance Compilers for Parallel Computing, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 17: Michael Wolfe, Parallelizing compilers, ACM Computing Surveys (CSUR), v.28 n.1, p.261-262, March 1996 [doi>10.1145/234313.234417]