Scratch-pad memory allocation without compiler support for java applications

ABSTRACT

This paper presents the first scratch-pad memory allocation scheme that requires no compiler support for interpreted-language based applications. A scratch-pad memory(SPM) is a fast compiler-managed SRAM that replaces the hardware-managed cache. Its uses are motivated by its better realtime guarantees as compared to cache and by its significantly lower overheads in energy consumption, area and access time. Interpreted languages are languages such as Java that are interpreted by a runtime environment instead of being executed directly on hardware.

All existing memory allocation schemes for SPM require compiler analysis to develop the allocation strategy. Specifically, existing allocation schemes for Java-based applications determine the allocations at compile-time. They then annotate the Java bytecodes with these allocation decisions for the Java Virtual Machine (JVM) to implement the actual allocation at runtime. These existing allocation schemes tie the resulting bytecode to specific SPM sizes, therefore preventing the applications from being portable to different SPM sizes. Further, existing methods do not work for unmodified third-party byte codes produced by compilers other than their specialized compilers.

In this paper, we propose the first ever SPM allocation schemethat is completely implemented inside the JVM. Our method requires no compiler support and works for unmodified byte codes from any source. Moreover, unlike existing methods, it preserves the portability of bytecode to any SPM size. We investigate our method on the Sun Hotspot JVM on which we achieve a 27.8% improvement on runtime and 21.8% on energy saving versus not using the SPM - the only existing alternative for unmodified bytecodes.

REFERENCES

• 1: aiT: Worst Case Execution Time Analyzers. AbsInt Angewandte Informatik GmbH. 2004. http://www.absint.com/ait.
• 2: Federico Angiolini , Francesco Menichelli , Alberto Ferrero , Luca Benini , Mauro Olivieri, A post-compiler approach to scratchpad mapping of code, Proceedings of the 2004 international conference on Compilers, architecture, and synthesis for embedded systems, September 22-25, 2004, Washington DC, USA [doi>10.1145/1023833.1023869]
• 3: ARM968E-S 32-bit Embedded Core. Arm, Revised March 2004. http://www.arm.com/products/CPUs/ARM968E-S.html.
• 4: Oren Avissar , Rajeev Barua , Dave Stewart, Heterogeneous memory management for embedded systems, Proceedings of the 2001 international conference on Compilers, architecture, and synthesis for embedded systems, November 16-17, 2001, Atlanta, Georgia, USA [doi>10.1145/502217.502223]
• 5: Oren Avissar , Rajeev Barua , Dave Stewart, An optimal memory allocation scheme for scratch-pad-based embedded systems, ACM Transactions on Embedded Computing Systems (TECS), v.1 n.1, p.6-26, November 2002 [doi>10.1145/581888.581891]
• 6: 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]
• 7: M. BOHR, B. Doyle, J. Kavalieros, D. Barlage, A. Murthy, M. Doczy, R. Rios, T. Linton, R. Arghavani, B. Jin, S. Datta, and S. Hareland. Intelt's 90 nm technology: Mooret's law and more, September 2002. Document Number: {IR-TR-2002-10}.
• 8: Angel Dominguez , Sumesh Udayakumaran , Rajeev Barua, Heap data allocation to scratch-pad memory in embedded systems, Journal of Embedded Computing, v.1 n.4, p.521-540, December 2005
• 9: J. Edler and M. Hill. Dineroiv cache simulator. Revised 2004. http://www.cs.wisc.edu/ markhill/DineroIV/.
• 10: Intel wireless flash memory (W30). Intel Corporation. http://www.intel.com/design/flcomp/datashts/290702.htm.
• 11: GetJar. Java nokia series 60 software. http://www.getjar.com/software/Java/Nokia_Series_60.
• 12: Google. Google mobile gmail. http://www.google.com/mobile/mail/index.html.
• 13: 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
• 14: Handango. Java application for cell phone. http://www.handango.com/.
• 15: John L. Hennessy , David A. Patterson, Computer architecture (2nd ed.): a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 16: Jason D. Hiser , Jack W. Davidson, EMBARC: an efficient memory bank assignment algorithm for retargetable compilers, Proceedings of the 2004 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems, June 11-13, 2004, Washington, DC, USA
• 17: Chad M. Huneycutt , Joshua B. Fryman , Kenneth M. Mackenzie, Software Caching using Dynamic Binary Rewriting for Embedded Devices, Proceedings of the 2002 International Conference on Parallel Processing (ICPP'02), p.621, August 18-21, 2002
• 18: S. M. Inc. Java SE HotSpot at a Glance. http://java. sun.com/javase/technologies/hotspot/.
• 19: Informit. Java on pocket pc devices. http://www.informit.com/articles/article.asp?=344816&rl=1.
• 20: J. Janzen. Calculating Memory System Power for DDR SDRAM. In DesignLine Journal, volume 10(2). Micron Technology Inc., 2001. http://www.micron.com/publications/designline.html.
• 21: J. P. Lewis and U. Neumann. Performance of Java versus C++. Computer Graphics and Immersive Technology Lab, University of Southern California, Jan 2003. Updated 2004. http://www.idiom.com/~zilla/Computer/javaCbenchmark.html.
• 22: S. Kim, S. Tomar, N. Vijaykrishnan, M. Kandemir, and M. Irwin. Energy-efficient java execution using local memory and object co-location. In Proceedings of Computers and Digital Techniques, pages 33--42. IEEE, 2004.
• 23: Carl S. Lebsack , J. Morris Chang, Using Scratchpad to Exploit Object Locality in Java, Proceedings of the 2005 International Conference on Computer Design, p.381-386, October 02-05, 2005 [doi>10.1109/ICCD.2005.111]
• 24: Tim Lindholm , Frank Yellin, Java Virtual Machine Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 25: S. Microsystems. Java se embedded overview. http://java.sun.com/javase/embedded/overview.jsp.
• 26: 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]
• 27: Csaba Andras Moritz , Matthew Frank , Saman P. Amarasinghe, FlexCache: A Framework for Flexible Compiler Generated Data Caching, Revised Papers from the Second International Workshop on Intelligent Memory Systems, p.135-146, November 12, 2000
• 28: N. Nguyen, A. Dominguez, and R. Barua. Memory allocation for embedded systems with a compile-time-unknown scratch-pad size. To appear in the ACM Transactions on Embedded Computing Systems (TECS), 2007. http://www.ece.umd.edu/~barua/nguyen-TECS-2007.pdf.
• 29: Preeti Ranjan Panda , Nikil D. Dutt , Alexandru Nicolau, On-chip vs. off-chip memory: the data partitioning problem in embedded processor-based systems, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.5 n.3, p.682-704, July 2000 [doi>10.1145/348019.348570]
• 30: Compilation Challenges for Network Processors. Industrial Panel, ACM Conference on Languages, Compilers and Tools for Embedded Systems (LCTES), June 2003. Slides at http://www.cs.purdue.edu/s3/LCTES03/.
• 31: P. Shivakumar and N. Jouppi. Cacti 3.2. Revised 2004. http://research.compaq.com/wrl/people/jouppi/CACTI.html.
• 32: J. Sjodin, B. Froderberg, and T. Lindgren. Allocation of Global Data Objects in On-Chip RAM. Compiler and Architecture Support for Embedded Computing Systems, December 1998.
• 33: Jan Sjödin , Carl von Platen, Storage allocation for embedded processors, Proceedings of the 2001 international conference on Compilers, architecture, and synthesis for embedded systems, November 16-17, 2001, Atlanta, Georgia, USA [doi>10.1145/502217.502221]
• 34: Stefan Steinke , Nils Grunwald , Lars Wehmeyer , Rajeshwari Banakar , M. Balakrishnan , Peter Marwedel, Reducing energy consumption by dynamic copying of instructions onto onchip memory, Proceedings of the 15th international symposium on System Synthesis, October 02-04, 2002, Kyoto, Japan [doi>10.1145/581199.581247]
• 35: 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
• 36: Use of Local Memory for Efficient Java Execution, Proceedings of the International Conference on Computer Design: VLSI in Computers & Processors, p.468, September 23-26, 2001
• 37: TuxMobil. Free java applications for (linux) pdas and mobile cell phones. http://tuxmobil.org/pda_linux_apps_java.html.
• 38: Sumesh Udayakumaran , Rajeev Barua, Compiler-decided dynamic memory allocation for scratch-pad based embedded systems, Proceedings of the 2003 international conference on Compilers, architecture and synthesis for embedded systems, October 30-November 01, 2003, San Jose, California, USA [doi>10.1145/951710.951747]
• 39: Sumesh Udayakumaran , Angel Dominguez , Rajeev Barua, Dynamic allocation for scratch-pad memory using compile-time decisions, ACM Transactions on Embedded Computing Systems (TECS), v.5 n.2, p.472-511, May 2006 [doi>10.1145/1151074.1151085]
• 40: Manish Verma , Lars Wehmeyer , Peter Marwedel, Cache-Aware Scratchpad Allocation Algorithm, Proceedings of the conference on Design, automation and test in Europe, p.21264, February 16-20, 2004
• 41: Manish Verma , Lars Wehmeyer , Peter Marwedel, Dynamic overlay of scratchpad memory for energy minimization, Proceedings of the 2nd IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis, September 08-10, 2004, Stockholm, Sweden [doi>10.1145/1016720.1016748]
• 42: Lars Wehmeyer , Urs Helmig , Peter Marwedel, Compiler-optimized usage of partitioned memories, Proceedings of the 3rd workshop on Memory performance issues: in conjunction with the 31st international symposium on computer architecture, p.114-120, June 20-20, 2004, Munich, Germany [doi>10.1145/1054943.1054959]
• 43: L. Wehmeyer and P. Marwedel. Influence of onchip scratchpad memories on wcet prediction. In Proceedings of the 4th International Workshop on Worst-Case Execution Time (WCET) Analysis, 2004.
• 44: Lars Wehmeyer , Peter Marwedel, Influence of Memory Hierarchies on Predictability for Time Constrained Embedded Software, Proceedings of the conference on Design, Automation and Test in Europe, p.600-605, March 07-11, 2005 [doi>10.1109/DATE.2005.183]
• 45: S. Wilton and N. Jouppi. Cacti: An enhanced cache access and cycle time model. In IEEE Journal of Solid-State Circuits, 1996.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.1 Semiconductor Memories
          Subjects: Dynamic memory (DRAM)

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.1 Semiconductor Memories
          Subjects: Static memory (SRAM)
      B.3.2 Design Styles
          Subjects: Cache memories

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

  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Code generation; Compilers

  E. Data
  E.2 DATA STORAGE REPRESENTATIONS
      Subjects: Linked representations

General Terms:
Algorithms, Design, Management, Performance

Keywords:
JIT, JVM, compiler, embedded systems, java, memory allocation, scratch-pad