CheckerCore: enhancing an FPGA soft core to capture worst-case execution times

ABSTRACT

Embedded processors have become increasingly complex, resulting in variable execution behavior and reduced timing predictability. On such processors, safe timing specifications expressed as bounds on the worst-case execution time (WCET) are generally too loose due to conservative assumptions about complex architectural features, timing anomalies and programmatic complexities. Hence, exploiting the latest architectures may not be an option for embedded systems with hard real-time constraints where deadline misses cannot be tolerated.

This work addresses these shortcomings by contributing CheckerCore. CheckerCore is a mode-enhanced SPARC v8 soft core processor synthesized on an FPGA. During regular execution the core adheres to its original specifications. But when operating in a special time-checking configuration, CheckerCore executes programs irrespective of inputs and steers execution intentionally along selected control flow paths. Such execution allows systematic derivation of worst-case execution time (WCET) bounds. This paper presents the overall design and implementation of CheckerCore and also illustrates its use in deriving accurate WCET bounds for a set of embedded benchmarks. Overall, CheckerCore proposes a realistic processor core enhancement that encapsulate processor details without revealing them to users while supporting safe bounding of WCETs. To the best of our knowledge, this is the first contribution of a WCET-enhancing microarchitectural feature besides full processor encapsulations.

REFERENCES

• 1: A. Anantaraman, K. Seth, K. Patil, E. Rotenberg, and F. Mueller. Enforcing safety of real-time schedules on contemporary processors using a virtual simple architecture (VISA). In IEEE Real-Time Systems Symposium, pages 114--125, Dec. 2004.
• 2: T. Austin, E. Larson, and D. Ernst. Simplescalar: an infrastructure for computer system modeling. Computer, 35(2):59--67, Feb 2002.
• 3: G. Bernat, A. Colin, and S. Petters. WCET analysis of probabilistic hard real-time systems. In IEEE Real-Time Systems Symposium, Dec. 2002.
• 4: V. Braberman, M. Felder, and M. Marre. Testing timing behavior of real--time software. 1997.
• 5: S. Edgar and A. Burns. Statistical analysis of WCET for scheduling. In 22nd IEEE Real-Time Systems Symposium, pages 215--224, 2001.
• 6: R. W. et al. The worst-case execution time problem overview of methods and survey of tools. ACM Transactions on Embedded Computing Systems, 7(3):1--53, Apr. 2008.
• 7: S. M. et. al. Parascale: Expoliting parametric timing analysis for real-time schedulers and dynamic voltage scaling. In IEEE Real-Time Systems Symposium, pages 233--242, Dec. 2005.
• 8: A. Gaisler. Leon3 product sheet. http://www.gaisler.com/doc/leon3_product_sheet.pdf, September 2008.
• 9: X. S. Hu, Z. Tao, and E. H. M. Sha. Estimating probabilistic timing performance for real-time embedded systems. Very Large Scale Integration (VLSI) Systems, IEEE Transactions on, 9(6):833--844, 2001. 1063--8210.
• 10: T. Lundqvist. A WCET Analysis Method for Pipelined Microprocessors with Cache Memories. PhD thesis, Chalmers University, 2002.
• 11: T. Lundqvist and P. Stenstrom. An integrated path and timing analysis method based on cycle-level symbolic execution. Real-Time Systems, 17(2/3):183--208, Nov. 1999.
• 12: P. Magnusson, M. Christensson, J. Eskilson, D. Forsgren, G. Hallberg, J. Hogberg, F. Larsson, A. Moestedt, and B. Werner. Simics: A full system simulation platform. Computer, 35(2):50--58, Feb 2002.
• 13: S. Mohan and F. Mueller. Hybrid timing analysis of modern processor pipelines via hardware/software interactions. In IEEE Real-Time Embedded Technology and Applications Symposium, pages 285--294, 2008.
• 14: S. Mohan and F. Mueller. Merging state and preserving timing anomalies in pipelines of high-end processors. In IEEE Real-Time Systems Symposium, Dec. 2008.
• 15: H. Ramaprasad and F. Mueller. Tightening the bounds on feasible preemption points. In IEEE Real-Time Systems Symposium, pages 212--222, Dec. 2006.
• 16: G. D. Veciana, M. Jacome, and J.-H. Guo. Assessing probabilistic timing constraints on system performance. Design Automation for Embedded Systems, 5(1):61--81, 2000.
• 17: G. D. Veciana, M. F. Jacome, and J.-H. Guo. Hierarchical algorithms for assessing probabilistic constraints on system performance. In IEEE/ACM Design Automation Conference (DAC), pages 251--256, 1998.
• 18: J. Wegener and F. Mueller. A comparison of static analysis and evolutionary testing for the verification of timing constraints. Real--Time Systems, 21(3):241--268, Nov. 2001.
• 19: J. Whitham. Real-time Processor Architectures for Worst Case Execution Time Reduction. PhD thesis, University of York, May 2008.

INDEX TERMS

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

General Terms:
Design, Experimentation

Keywords:
FPGA, LEON3, SPARC, WCET, checkercore, embedded system, real-time, shadow pipeline, worst-case-execution-time