Time-predictable memory arbitration for a Java chip-multiprocessor

ABSTRACT

In this paper, we propose an approach to calculate worst-case execution times (WCET) of tasks running on a homogeneous Java multiprocessor. These processors access a shared main memory. Hence, the tasks running on different CPUs may influence the execution times of each other. Therefore, we implemented a time division multiple access arbiter that divides the memory access time into equal time slots, one time slot for each CPU. This memory arbitration allows calculating upper bounds for the execution time of Java bytecodes depending on the number of CPUs, the size of the time slot, and the memory access time. A WCET analysis tool can utilize these results and generate temporal, upper bounds for application tasks. We further explore how the size of the time slot and the number of CPUs in the system influence the WCET results. Furthermore, a real-world application task is used to compare the analyzed results with measured execution times. This paper describes the timing analysis of a time-predictable Java multiprocessor with shared memory.

REFERENCES

• 1: Alexandru Andrei , Petru Eles , Zebo Peng , Jakob Rosen, Predictable Implementation of Real-Time Applications on Multiprocessor Systems-on-Chip, Proceedings of the 21st International Conference on VLSI Design, p.103-110, January 04-08, 2008 [doi>10.1109/VLSI.2008.33]
• 2: A. Ermedahl and J. Engblom. Execution time analysis for embedded real-time systems. pages 35.1--35.17. Chapman & Hall/CRC - Taylor and Francis Group, August 2007.
• 3: John L. Hennessy , David A. Patterson, Computer Architecture, Fourth Edition: A Quantitative Approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2006
• 4: M. Joseph and P. K. Pandya. Finding response times in a real-time system. Comput. J, 29(5):390--395, 1986.
• 5: Hermann Kopetz, Real-Time Systems: Design Principles for Distributed Embedded Applications, Kluwer Academic Publishers, Norwell, MA, 1997
• 6: Yau-Tsun Steven Li , Sharad Malik, Performance analysis of embedded software using implicit path enumeration, Proceedings of the ACM SIGPLAN 1995 workshop on Languages, compilers, & tools for real-time systems, p.88-98, November 1995, La Jolla, California, United States
• 7: Tim Lindholm , Frank Yellin, Java Virtual Machine Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 8: C. L. Liu , James W. Layland, Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment, Journal of the ACM (JACM), v.20 n.1, p.46-61, Jan. 1973 [doi>10.1145/321738.321743]
• 9: C. Pitter and M. Schoeberl. Time predictable CPU and DMA shared memory access. In International Conference on Field-Programmable Logic and its Applications (FPL 2007), Amsterdam, Netherlands, August 2007.
• 10: C. Pitter and M. Schoeberl. Performance Evaluation of a Java Chip-Multiprocessor. In Proceedings of the IEEE Third Symposium on Industrial Embedded Systems (SIES 2008), Montpellier, France, June 2008.
• 11: F. Poletti, D. Bertozzi, L. Benini, and A. Bogliolo. Performance Analysis of Arbitration Policies for SoC Communication Architectures. Design Automation for Embedded Systems, 8:189--210(22), 200306/09.
• 12: Peter Puschner , Alan Burns, Guest Editorial: A Review of Worst-Case Execution-TimeAnalysis, Real-Time Systems, v.18 n.2-3, p.115-128, May 2000 [doi>10.1023/A:1008119029962]
• 13: Jakob Rosen , Alexandru Andrei , Petru Eles , Zebo Peng, Bus Access Optimization for Predictable Implementation of Real-Time Applications on Multiprocessor Systems-on-Chip, Proceedings of the 28th IEEE International Real-Time Systems Symposium, p.49-60, December 03-06, 2007 [doi>10.1109/RTSS.2007.13]
• 14: M. Schoeberl. A time predictable instruction cache for a Java processor. In On the Move to Meaningful Internet Systems 2004: Workshop on Java Technologies for Real-Time and Embedded Systems (JTRES 2004), volume 3292 of LNCS, pages 371--382, Agia Napa, Cyprus, October 2004. Springer.
• 15: M. Schoeberl. JOP: A Java Optimized Processor for Embedded Real-Time Systems. PhD thesis, Vienna University of Technology, 2005.
• 16: M. Schoeberl. SimpCon - a simple and efficient SoC interconnect. In Proceedings of the 15th Austrian Workhop on Microelectronics, Austrochip 2007, Graz, Austria, October 2007.
• 17: Martin Schoeberl, A Java processor architecture for embedded real-time systems, Journal of Systems Architecture: the EUROMICRO Journal, v.54 n.1-2, p.265-286, January, 2008 [doi>10.1016/j.sysarc.2007.06.001]
• 18: Martin Schoeberl , Rasmus Pedersen, WCET analysis for a Java processor, Proceedings of the 4th international workshop on Java technologies for real-time and embedded systems, October 11-13, 2006, Paris, France [doi>10.1145/1167999.1168033]
• 19: Lothar Thiele , Reinhard Wilhelm, Design for Timing Predictability, Real-Time Systems, v.28 n.2-3, p.157-177, November-December 2004 [doi>10.1023/B:TIME.0000045316.66276.6e]
• 20: Reinhard Wilhelm , Jakob Engblom , Andreas Ermedahl , Niklas Holsti , Stephan Thesing , David Whalley , Guillem Bernat , Christian Ferdinand , Reinhold Heckmann , Tulika Mitra , Frank Mueller , Isabelle Puaut , Peter Puschner , Jan Staschulat , Per Stenström, The worst-case execution-time problem—overview of methods and survey of tools, ACM Transactions on Embedded Computing Systems (TECS), v.7 n.3, p.1-53, April 2008 [doi>10.1145/1347375.1347389]
• 21: Wayne Wolf, High-Performance Embedded Computing: Architectures, Applications, and Methodologies, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2006

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Microprocessors and microcomputers

  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Run-time environments

Keywords:
Java, chip-multiprocessor, shared memory, worst-case execution time