Data partitioning for maximal scratchpad usage

ABSTRACT

The energy consumption for Mobile Embedded Systems is a limiting factor because of today's battery capacities. The memory subsystem consumes a large chunk of the energy, necessitating its efficient utilization. Energy efficient scratchpads are thus becoming common, though unlike caches they require to be explicitly utilized. In this paper, an algorithm integrated into a compiler is presented which analyzes the application, partitions an array variable whenever its beneficial, appropriately modifies the application and selects the best set of variables and program parts to be placed onto the scratchpad. Results show an energy improvement between 5.7% and 17.6% for a variety of applications against a previously known algorithm.

REFERENCES

• 1: ARM. Advanced RISC Machines Ltd. www.arm.com.
• 2: AT91M40400 ATMEL Corporation. www.atmel.com.
• 3: Rajeshwari Banakar , Stefan Steinke , Bo-Sik Lee , M. Balakrishnan , Peter Marwedel, Scratchpad memory: design alternative for cache on-chip memory in embedded systems, Proceedings of the tenth international symposium on Hardware/software codesign, May 06-08, 2002, Estes Park, Colorado [doi>10.1145/774789.774805]
• 4: encc. University of Dortmund, Computer Science Dep., ls12-www.cs.uni-dortmund.de/research/encc.
• 5: David A. Patterson , John L. Hennessy, Computer architecture: a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1990
• 6: Intel. Mobile Power Guidelines 2000. Technical Report 1.0, Intel Corporation, Dec. 1998.
• 7: 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]
• 8: 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
• 9: C. Ferdinand, F. Martin, R. Wilhelm, Applying compiler techniques to cache behaviour prediction. In Proc. of Workshop on Languages, Compilers and Tools for Real-Time Systems Las Vegas, Nevada, page 37--46, Jun. 1997
• 10: George L. Nemhauser , Laurence A. Wolsey, Integer and combinatorial optimization, Wiley-Interscience, New York, NY, 1988
• 11: 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
• 12: Preeti Ranjan Panda , Alexandru Nicolau , Nikil Dutt, Memory Issues in Embedded Systems-on-Chip: Optimizations and Exploration, Kluwer Academic Publishers, Norwell, MA, 1998
• 13: Robert Sedgewick, Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1984
• 14: Tajana Šimunić , Luca Benini , Giovanni De Micheli, Cycle-accurate simulation of energy consumption in embedded systems, Proceedings of the 36th ACM/IEEE conference on Design automation, p.867-872, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.310090]
• 15: J. Sjödin, B. Fröderberg, and T. Lindgren. Allocation of global data objects in on-Chip RAM. In Proc. Workshop on Compiler and Architectural Support for Embedded Computer Systems, Washington DC, Dec. 1998.
• 16: S. Steinke, M. Knauer, L. Wehmeyer, and P. Marwedel. An accurate and fine grain instruction-level energy model supporting software optimizations. In PATMOS 01, Yverdon-Les-Bains, Switzerland, Sep. 2001.
• 17: Synopsys. Power products reference manual V3.5. synopsys, 1996.
• 18: Vivek Tiwari, Logic and system design for low power consumption, 1996
• 19: Vivek Tiwari , Sharad Malik , Andrew Wolfe , Mike Tien-Chien Lee, Instruction level power analysis and optimization of software, Journal of VLSI Signal Processing Systems, v.13 n.2-3, p.223-238, Aug./Sept. 1996 [doi>10.1007/BF01130407]
• 20: S. J. E. Wilton and N. P. Jouppi. CACTI: An enhanced cache access and cycle time model. IEEE Journal of Solid-State Circuits, 31(5):677--688, May 1996.
• 21: M. E. Wolf and M. S. Lam A loop transformation theory and an algorithm to maximise parallelism In Proc. of the 3rd Workshop on Programming Languages and Compilers for Parallel Computing Aug. 1990
• 22: Alistair Moffat , Radford M. Neal , Ian H. Witten, Arithmetic coding revisited, ACM Transactions on Information Systems (TOIS), v.16 n.3, p.256-294, July 1998 [doi>10.1145/290159.290162]