research-article

WCET driven design space exploration of an object cache

Authors:

Benedikt Huber,

Wolfgang Puffitsch,

Martin SchoeberlAuthors Info & Claims

JTRES '10: Proceedings of the 8th International Workshop on Java Technologies for Real-Time and Embedded Systems

Pages 26 - 35

https://doi.org/10.1145/1850771.1850775

Published: 19 August 2010 Publication History

Abstract

In order to guarantee that real-time systems meet their timing specification, static execution time bounds need to be calculated. Not considering execution time predictability led to architectures which perform well in the average case, but require very pessimistic assumptions when bounding the worst-case execution time (WCET).

Computer architecture design is driven by simulations of standard benchmarks estimating the expected average case performance. The design decisions derived from this design methodology do not necessarily result in a WCET analysis-friendly design. Aiming for a time-predictable computer architecture, we propose to employ WCET analysis techniques for the design space exploration of processor architectures. We exemplify this approach by a WCET driven design of a cache for heap allocated objects.

Depending on the main memory properties (latency and bandwidth), different cache organizations result in the lowest WCET. The evaluation reveals that for certain cache configurations, the analyzed hit rate is comparable to the average case hit rate obtained by measurements. We believe that an early architecture exploration by means of static timing analysis techniques helps to identify configurations suitable for hard real-time systems.

References

[1]

Eric J. Bruno and Greg Bollella. Real-Time Java Programming: With Java RTS. Prentice Hall PTR, Upper Saddle River, NJ, USA, 2009.

Digital Library

[2]

A. Deutsch. A storeless model of aliasing and its abstractions using finite representations of right-regular equivalence relations. In Computer Languages, 1992., Proceedings of the 1992 International Conference on, pages 2--13, Apr 1992.

[3]

Christian Ferdinand and Reinhard Wilhelm. On predicting data cache behavior for real-time systems. In LCTES '98: Proceedings of the ACM SIGPLAN Workshop on Languages, Compilers, and Tools for Embedded Systems, pages 16--30, London, UK, 1998. Springer-Verlag.

Digital Library

[4]

Daniel Grund and Jan Reineke. Precise and efficient FIFO-replacement analysis based on static phase detection. In Proceedings of the 22nd Euromicro Conference on Real-Time Systems (ECRTS 2010), July 2010.

Digital Library

[5]

Stefana Nenova and Daniel Kästner. Worst-case timing estimation and architecture exploration in early design phases. In Niklas Holsti, editor, 9th Intl. Workshop on Worst-Case Execution Time (WCET) Analysis, Dagstuhl, Germany, 2009. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany.

[6]

David A. Patterson. Reduced instruction set computers. Commun. ACM, 28(1):8--21, 1985.

Digital Library

[7]

Wolfgang Puffitsch. Data caching, garbage collection, and the Java memory model. In Proceedings of the 7th International Workshop on Java Technologies for Real-Time and Embedded Systems (JTRES 2009), pages 90--99, New York, NY, USA, 2009. ACM.

Digital Library

[8]

Peter Puschner and Anton Schedl. Computing maximum task execution times -- a graph-based approach. Journal of Real-Time Systems, 13(1):67--91, Jul. 1997.

Digital Library

[9]

Martin Schoeberl. A Java processor architecture for embedded real-time systems. Journal of Systems Architecture, 54/1--2:265--286, 2008.

Digital Library

[10]

Martin Schoeberl. Time-predictable cache organization. In Proceedings of the First International Workshop on Software Technologies for Future Dependable Distributed Systems (STFSSD 2009), pages 11--16, Tokyo, Japan, March 2009. IEEE Computer Society.

Digital Library

[11]

Martin Schoeberl, Benedikt Huber, Walter Binder, Wolfgang Puffitsch, and Alex Villazon. Object cache evaluation. Technical report, Technical University of Denmark, 2010.

[12]

Martin Schoeberl, Thomas B. Preusser, and Sascha Uhrig. The embedded Java benchmark suite JemBench. In Proceedings of the 8th International Workshop on Java Technologies for Real-time and Embedded Systems (JTRES 2010), Prague, Czech Republic, August 2010. ACM Press.

Digital Library

[13]

Martin Schoeberl, Wolfgang Puffitsch, and Benedikt Huber. Towards time-predictable data caches for chip-multiprocessors. In Proceedings of the Seventh IFIP Workshop on Software Technologies for Future Embedded and Ubiquitous Systems (SEUS 2009), number LNCS 5860, pages 180--191. Springer, November 2009.

Digital Library

[14]

Martin Schoeberl, Wolfgang Puffitsch, Rasmus Ulslev Pedersen, and Benedikt Huber. Worst-case execution time analysis for a Java processor. Software: Practice and Experience, 40/6:507--542, 2010.

Digital Library

[15]

Sascha Uhrig and Jörg Wiese. jamuth: an IP processor core for embedded Java real-time systems. In Proceedings of the 5th International Workshop on Java Technologies for Real-time and Embedded Systems (JTRES 2007), pages 230--237, New York, NY, USA, 2007. ACM Press.

Digital Library

[16]

N. Vijaykrishnan and N. Ranganathan. Supporting object accesses in a Java processor. Computers and Digital Techniques, IEE Proceedings-, 147(6):435--443, 2000.

[17]

Ifor Williams and Mario Wolczko. An object-based memory architecture. In Proceedings of the Fourth International Workshop on Persistent Object Systems, pages 114--130, Martha's Vineyard, MA (USA), September 1990.

[18]

Ifor W. Williams. Object-Based Memory Architecture. PhD thesis, Department of Computer Science, University of Manchester, 1989.

[19]

Greg Wright, Matthew L. Seidl, and Mario Wolczko. An object-aware memory architecture. Sci. Comput. Program, 62(2):145--163, 2006.

Digital Library

[20]

Martin Zabel, Thomas B. Preusser, Peter Reichel, and Rainer G. Spallek. Secure, real-time and multi-threaded general-purpose embedded Java microarchitecture. In Prceedings of the 10th Euromicro Conference on Digital System Design Architectures, Methods and Tools (DSD 2007), pages 59--62, Lübeck, Germany, Aug. 2007.

Digital Library

Cited By

Schoeberl MPuffitsch WHepp SHuber BProkesch D(2018)PatmosReal-Time Systems10.1007/s11241-018-9300-454:2(389-423)Online publication date: 1-Apr-2018
https://dl.acm.org/doi/10.1007/s11241-018-9300-4
Zabel MPreußer TSpallek RSchoeberl MWellings A(2012)Increasing the efficiency of an embedded multi-core bytecode processor using an object cacheProceedings of the 10th International Workshop on Java Technologies for Real-time and Embedded Systems10.1145/2388936.2388952(88-97)Online publication date: 24-Oct-2012
https://dl.acm.org/doi/10.1145/2388936.2388952
Schoeberl M(2012)Is time predictability quantifiable?2012 International Conference on Embedded Computer Systems (SAMOS)10.1109/SAMOS.2012.6404196(333-338)Online publication date: Jul-2012
https://doi.org/10.1109/SAMOS.2012.6404196
Show More Cited By

Recommendations

WCET-driven cache-aware code positioning
CASES '11: Proceedings of the 14th international conference on Compilers, architectures and synthesis for embedded systems

Code positioning is a well-known compiler optimization aiming at the improvement of the instruction cache behavior. A contiguous mapping of code fragments in memory avoids overlapping of cache sets and thus decreases the number of cache conflict misses.
...
WCET analysis of instruction cache hierarchies

With the advent of increasingly complex hardware in real-time embedded systems (processors with performance enhancing features such as pipelines, caches, multiple cores), most embedded processors use a hierarchy of caches. While much research has been ...
Worst-case execution time analysis-driven object cache design

Hard real-time systems need a time-predictable computing platform to enable static worst-case execution time (WCET) analysis. All performance-enhancing features need to be WCET analyzable. However, standard data caches containing heap-allocated data are ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

JTRES '10: Proceedings of the 8th International Workshop on Java Technologies for Real-Time and Embedded Systems

August 2010

183 pages

ISBN:9781450301220

DOI:10.1145/1850771

Conference Chair:
Tomas Kalibera
Charles University
,
Program Chair:
Jan Vitek
Purdue University

Copyright © 2010 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 19 August 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Funding Sources

Seventh Framework Programme

Conference

JTRES '10

JTRES '10: JTRES '10 -Proceedings of the 8th International Workshop on Java Technologies for Real-time and Embedded Systems

August 19 - 21, 2010

Prague, Czech Republic

Acceptance Rates

Overall Acceptance Rate 50 of 70 submissions, 71%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
102
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 06 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Schoeberl MPuffitsch WHepp SHuber BProkesch D(2018)PatmosReal-Time Systems10.1007/s11241-018-9300-454:2(389-423)Online publication date: 1-Apr-2018
https://dl.acm.org/doi/10.1007/s11241-018-9300-4
Zabel MPreußer TSpallek RSchoeberl MWellings A(2012)Increasing the efficiency of an embedded multi-core bytecode processor using an object cacheProceedings of the 10th International Workshop on Java Technologies for Real-time and Embedded Systems10.1145/2388936.2388952(88-97)Online publication date: 24-Oct-2012
https://dl.acm.org/doi/10.1145/2388936.2388952
Schoeberl M(2012)Is time predictability quantifiable?2012 International Conference on Embedded Computer Systems (SAMOS)10.1109/SAMOS.2012.6404196(333-338)Online publication date: Jul-2012
https://doi.org/10.1109/SAMOS.2012.6404196
van Amesfoort AVarbanescu ASips H(2012)Parallel application characterization with quantitative metricsConcurrency and Computation: Practice & Experience10.1002/cpe.188224:5(445-462)Online publication date: 1-Apr-2012
https://dl.acm.org/doi/10.1002/cpe.1882
Grelck Cvan Deurzen THerhut SScholz S(2012)Asynchronous adaptive optimisation for generic data-parallel array programmingConcurrency and Computation: Practice & Experience10.1002/cpe.184224:5(499-516)Online publication date: 1-Apr-2012
https://dl.acm.org/doi/10.1002/cpe.1842
Huber BPuffitsch WSchoeberl M(2012)Worst-case execution time analysis-driven object cache designConcurrency and Computation: Practice & Experience10.1002/cpe.176324:8(753-771)Online publication date: 1-Jun-2012
https://dl.acm.org/doi/10.1002/cpe.1763
Stilkerich MThomm IWawersich CSchröder-Preikschat W(2012)Tailor-made JVMs for statically configured embedded systemsConcurrency and Computation: Practice & Experience10.1002/cpe.175524:8(789-812)Online publication date: 1-Jun-2012
https://dl.acm.org/doi/10.1002/cpe.1755
Ravn ASchoeberl M(2012)Safety-critical Java with cyclic executives on chip-multiprocessorsConcurrency and Computation: Practice & Experience10.1002/cpe.175424:8(772-788)Online publication date: 1-Jun-2012
https://dl.acm.org/doi/10.1002/cpe.1754
Schoeberl MBinder WVillazon A(2011)Design Space Exploration of Object Caches with Cross-ProfilingProceedings of the 2011 14th IEEE International Symposium on Object/Component/Service-Oriented Real-Time Distributed Computing10.1109/ISORC.2011.34(213-221)Online publication date: 28-Mar-2011
https://dl.acm.org/doi/10.1109/ISORC.2011.34
Schoeberl M(2011)A Time-Predictable Object CacheProceedings of the 2011 14th IEEE International Symposium on Object/Component/Service-Oriented Real-Time Distributed Computing10.1109/ISORC.2011.22(99-105)Online publication date: 28-Mar-2011
https://dl.acm.org/doi/10.1109/ISORC.2011.22
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten