WCET analysis for a Java processor

ABSTRACT

In this paper we propose a solution for a worst-case execution time (WCET) analyzable Java system: a combination of a time predictable Java processor and a tool that performs WCET analysis of Java bytecode. We present a Java processor, called JOP, designed for time-predictable execution of real-time tasks. JOP is an implementation of the Java virtual machine (JVM) in hardware. The execution time of bytecodes, the instructions of the JVM, is known cycle accurate for JOP. Therefore, JOP simplifies the low-level WCET analysis. A method cache, that fills whole Java methods into the cache, is analyzable with respect to the WCET. The WCET analysis tool is based on integer linear programming. The tool performs the low-level analysis at the bytecode level and integrates the method cache analysis for a two block cache.

References

1. C. Artho and A. Biere. Subroutine inlining and bytecode abstraction to simplify static and dynamic analysis. Electronic Notes in Theoretical Computer Science, 141(1):109--128, December 2005.
2. I. Bate, G. Bernat, G. Murphy, and P. Puschner. Low-level analysis of a portable Java byte code WCET analysis framework. In Proc. 7th International Conference on Real-Time Computing Systems and Applications, pages 39--48, Dec. 2000.
3. G. Bernat, A. Burns, and A. Wellings. Portable worst-case execution time analysis using java byte code. In Proc. 12th EUROMICRO Conference on Real-time Systems, Jun 2000.
4. G. Bollella, J. Gosling, B. Brosgol, P. Dibble, S. Furr, and M. Turnbull. The Real-Time Specification for Java. Java Series. Addison-Wesley, June 2000.
5. M. Dahm. Byte code engineering with the BCEL API. Technical report, Freie Universitat Berlin, April 2001.
6. DCT. Lightfoot 32-bit Java processor core. data sheet, September 2001.
7. S. Dey, P. Sanchez, D. Panigrahi, L. Chen, C. Taylor, and K. Sekar. Using a soft core in a SOC design: Experiences with picoJava. IEEE Design and Test of Computers, 17(3):60--71, July 2000.
8. J. Gaisler. A portable and fault-tolerant microprocessor based on the SPARC v8 architecture. In DSN '02: Proceedings of the 2002 International Conference on Dependable Systems and Networks, page 409, Washington, DC, USA, 2002. IEEE Computer Society.
9. T. R. Halfhill. Imsys hedges bets on Java. Microprocessor Report, August 2000.
10. D. S. Hardin. Real-time objects on the bare metal: An efficient hardware realization of the Javatm virtual machine. In Proceedings of the Fourth International Symposium on Object-Oriented Real-Time Distributed Computing, page 53. IEEE Computer Society, 2001.
11. Imsys. Im1101c (the cjip) technical reference manual/v0.25, 2004.
12. J. Kreuzinger, U. Brinkschulte, M. Pfeffer, S. Uhrig, and T. Ungerer. Real-time event-handling and scheduling on a multithreaded Java microcontroller. Microprocessors and Microsystems, 27(1):19--31, 2003.
13. Y.-T. S. Li and S. Malik. Performance analysis of embedded software using implicit path enumeration. In LCTES '95: Proceedings of the ACM SIGPLAN 1995 workshop on Languages, compilers, & tools for real-time systems, pages 88--98, New York, NY, USA, 1995. ACM Press.
14. Y.-T. S. Li, S. Malik, and A. Wolfe. Efficient microarchitecture modeling and path analysis for real-time software. In RTSS'95: Proceedings of the 16th IEEE Real-Time Systems Symposium (RTSS '95), page 298, Washington, DC, USA, 1995. IEEE Computer Society.
15. T. Lindholm and F. Yellin. The Java Virtual Machine Specification. Addison-Wesley, Reading, MA, USA, second edition, 1999.
16. T. Lundqvist and P. Stenström. Timing anomalies in dynamically scheduled microprocessors. In RTSS '99: Proceedings of the 20th IEEE Real-Time Systems Symposium, page 12, Washington, DC, USA, 1999. IEEE Computer Society.
17. J. M. O'Connor and M. Tremblay. picoJava-I: The Java virtual machine in hardware. IEEE Micro, 17(2):45--53, 1997.
18. P. Puschner and G. Bernat. Wcet analysis of reusable portable code. In ECRTS '01: Proceedings of the 13th Euromicro Conference on Real-Time Systems, page 45, Washington, DC, USA, 2001. IEEE Computer Society.
19. P. Puschner and A. Burns. A review of worst-case execution-time analysis (editorial). Real-Time Systems, 18(2/3):115--128, 2000.
20. P. Puschner and A. Burns. Writing temporally predictable code. In WORDS'02: Proceedings of the The Seventh IEEE International Workshop on Object-Oriented Real-Time Dependable Systems (WORDS 2002), page 85, Washington, DC, USA, 2002. IEEE Computer Society.
21. P. Puschner and C. Koza. Calculating the maximum execution time of real-time programs. Real-Time Syst., 1(2):159--176, 1989.
22. P. Puschner and A. Schedl. Computing maximum task execution times -- a graph-based approach. Journal of Real-Time Systems, 13 (1):67--91, Jul. 1997.
23. 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.
24. M. Schoeberl. Evaluation of a Java processor. In Tagungsband Austrochip 2005, pages 127--134, Vienna, Austria, October 2005.
25. M. Schoeberl. JOP: A Java Optimized Processor for Embedded Real-Time Systems. PhD thesis, Vienna University of Technology, 2005.
26. M. Schoeberl. Real-time garbage collection for Java. In Proceedings of the 9th IEEE International Symposium on Object and Component-Oriented Real-Time Distributed Computing (ISORC 2006), pages 424--432, Gyeongju, Korea, April 2006.
27. M. Schoeberl. A time predictable Java processor. In Proceedings of the Design, Automation and Test in Europe Conference (DATE 2006), pages 800--805, Munich, Germany, March 2006.
28. A. C. Shaw. Reasoning about time in higher-level language software. IEEE Trans. Softw. Eng., 15(7):875--889, 1989.

Index Terms

• Software and its engineering

  • Software notations and tools

    • Compilers