Virtual simple architecture (VISA): exceeding the complexity limit in safe real-time systems

ABSTRACT

Meeting deadlines is a key requirement in safe realtime systems. Worst-case execution times (WCET) of tasks are needed for safe planning. Contemporary worst-case timing analysis tools can safely and tightly bound execution time on in-order single-issue pipelines with caches and static branch prediction. However, this simple pipeline appears to be a complexity limit, due to the need for analyzability. This excludes a whole class of high-performance processors from many embedded systems.We reconcile the complexity/safety trade-off by decoupling worst-case timing analysis from the processor implementation, through a virtual simple architecture (VISA). A VISA is the timing specification of a hypothetical simple pipeline and is the basis for worst-case timing analysis. However, the underlying microarchitecture can be arbitrarily complex. A task is divided into multiple sub-tasks which provide a means to gauge progress on the complex pipeline. Each sub-task is assigned an interim deadline, or checkpoint, based on the latest allowable completion time of the sub-task on the hypothetical simple pipeline. If no checkpoints are missed, then the complex pipeline is as timely as the safe pipeline. If a checkpoint is missed, the pipeline switches to a simple mode of operation that directly implements the VISA so that execution time of unfinished sub-tasks is safely bounded. The significance of our approach is that we circumvent worst-case timing analysis of the complex pipeline, by dynamically confirming its behavior is bounded by worst-case timing analysis of a simpler proxy pipeline.The benefit of using a high-performance processor is that tasks finish much sooner than they would have on an explicitly-safe processor. The new slack in the schedule can be exploited for higher throughput or lower power. With the VISA approach, an arbitrarily complex SMT processor can safely run non-real-time tasks at the same time as a real-time task. Alternatively, frequency/voltage can be safely lowered to take up slack. We explore the latter application and show a VISA-compliant complex pipeline consumes 43--61% less power than an explicitly-safe pipeline.

REFERENCES

• 1: R. Arnold. Bounding instruction cache performance. M. S. Thesis, Dept. of CS, Florida State Univ., Dec. 1996.
• 2: R. Arnold, F. Mueller, D. B. Whalley, and M. Harmon. Bounding worst-case instruction cache performance. Real-Time Systems Symp., Dec. 1994.
• 3: Todd M. Austin, DIVA: a reliable substrate for deep submicron microarchitecture design, Proceedings of the 32nd annual ACM/IEEE international symposium on Microarchitecture, p.196-207, November 16-18, 1999, Haifa, Israel
• 4: I. Bate, P. Conmy, T. Kelly, and J. McDermid. Use of modern processors in safety critical applications. The Computer Journal, 44(6):531--543, 2001.
• 5: David Brooks , Vivek Tiwari , Margaret Martonosi, Wattch: a framework for architectural-level power analysis and optimizations, Proceedings of the 27th annual international symposium on Computer architecture, p.83-94, June 2000, Vancouver, British Columbia, Canada
• 6: D. Burger, T. Austin, and S. Bennett. Evaluating future microprocessors: The simplescalar toolset. Tech. Rep. CS-TR-96-1308, CS Dept., Univ. of Wisc. - Madison, July 1996.
• 7: Alexander G. Dean , John Paul Shen, Hardware to Software Migration with Real-Time Thread Integration, Proceedings of the 24th Conference on EUROMICRO, p.10243, August 25-27, 1998
• 8: J. Engblom. On hardware and hardware models for embedded real-time systems. IEEE Workshop on Real-Time Embedded Systems, Dec. 2001.
• 9: T. Hand. Real-time systems need predictability. Computer Design (RISC Supplement), pp. 57--59, Aug. 1989.
• 10: M. Harmon, T. P. Baker, and D. B. Whalley. A retargetable technique for predicting execution time. Real-Time Systems Symp., Dec. 1992.
• 11: Christopher A. Healy , Robert D. Arnold , Frank Mueller , Marion G. Harmon , David B. Walley, Bounding Pipeline and Instruction Cache Performance, IEEE Transactions on Computers, v.48 n.1, p.53-70, January 1999 [doi>10.1109/12.743411]
• 12: C. A. Healy , D. B. Whalley , M. G. Harmon, Integrating the timing analysis of pipelining and instruction caching, Proceedings of the 16th IEEE Real-Time Systems Symposium (RTSS '95), p.288, December 05-07, 1995
• 13: Christopher J. Hughes , Jayanth Srinivasan , Sarita V. Adve, Saving energy with architectural and frequency adaptations for multimedia applications, Proceedings of the 34th annual ACM/IEEE international symposium on Microarchitecture, December 01-05, 2001, Austin, Texas
• 14: Yerang Hur , Young Hyun Bae , Sung-Soo Lim , Sung-Kwan Kim , Byung-Do Rhee , Sang Lyul Min , Chang Yun Park , Minsuk Lee , Heonshik Shin , Chong Sang Kim, Worst case timing analysis of RISC processors: R3000/R3010 case study, Proceedings of the 16th IEEE Real-Time Systems Symposium (RTSS '95), p.308, December 05-07, 1995
• 15: Sung-Kwan Kim , Sang Lyul Min , Rhan Ha, Efficient worst case timing analysis of data caching, Proceedings of the 2nd IEEE Real-Time Technology and Applications Symposium (RTAS '96), p.230, June 10-12, 1996
• 16: Y.-T. S. Li , S. Malik , A. Wolfe, Efficient microarchitecture modeling and path analysis for real-time software, Proceedings of the 16th IEEE Real-Time Systems Symposium (RTSS '95), p.298, December 05-07, 1995
• 17: Y.-T. S. Li , S. Malik , A. Wolfe, Cache modeling for real-time software: beyond direct mapped instruction caches, Proceedings of the 17th IEEE Real-Time Systems Symposium (RTSS '96), p.254, December 04-06, 1996
• 18: S.-S. Lim, Y. H. Bae, G. T. Jang, B.-D. Rhee, S. L. Min, C. Y. Park, H. Shin, and C. S. Kim. An accurate worst case timing analysis for RISC processors. Real-Time Sys. Symp., Dec. 1994.
• 19: 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]
• 20: Thomas Lundqvist , Per Stenström, An Integrated Path and Timing Analysis Method based onCycle-Level Symbolic Execution, Real-Time Systems, v.17 n.2-3, p.183-207, Nov. 1999 [doi>10.1023/A:1008138407139]
• 21: S. McFarling. Combining branch predictors. Technical Report TN-36, WRL, June 1993.
• 22: T. Mitra and A. Roychoudhury. A Framework to Model Branch Prediction for WCET Analysis. 2nd Workshop on Worst Case Execution Time Analysis (WCET), June 2002.
• 23: Frank Mueller, Static cache simulation and its applications, Florida State University, Tallahassee, FL, 1995
• 24: F. Mueller. Generalizing timing predictions to set-associative caches. EuroMicro Workshop on Real-Time Sys., June 1997.
• 25: Frank Mueller, The 3rd ACM SIGPLAN workshop on languages, compilers, and tools for real-time systems, ACM SIGPLAN Notices, v.32 n.11, p.15-16, Nov. 1997 [doi>10.1145/270941.270944]
• 26: Frank Mueller, Timing Analysis for Instruction Caches, Real-Time Systems, v.18 n.2-3, p.217-247, May 2000 [doi>10.1023/A:1008145215849]
• 27: F. Mueller, D. B. Whalley, and M. Harmon. Predicting instruction cache behavior. ACM Workshop on Language, Compiler, and Tool Support for Real-Time Systems, June 1994.
• 28: D. Niehaus, E. Nahum, J. Stankovic, and K. Ramamritham. Architecture and O/S support for predictable real-time systems. Spring internal document, March 1992.
• 29: Chang Yun Park, Predicting program execution times by analyzing static and dynamic program paths, Real-Time Systems, v.5 n.1, p.31-62, March 1993 [doi>10.1007/BF01088696]
• 30: P. Puschner. Zeitanalyse von Echtzeitprogrammen. Ph.D. Thesis, Dept. of CS, Technical University Vienna, Dec. 1993.
• 31: Peter P. Puschner , Anton V. Schedl, Computing Maximum Task Execution Times — A Graph-BasedApproach, Real-Time Systems, v.13 n.1, p.67-91, July 1997 [doi>10.1023/A:1007905003094]
• 32: P. Puschner. Is worst-case execution-time analysis a nonproblem? --- towards new software and hardware architectures. 2nd EuroMicro Int'l Workshop on WCET Analysis, June 2002.
• 33: P. Puschner , Ch. Koza, Calculating the maximum, execution time of real-time programs, Real-Time Systems, v.1 n.2, p.159-176, Sep. 1989 [doi>10.1007/BF00571421]
• 34: J. Rawat. Static analysis of cache analysis for real-time programming. M. S. Thesis, Iowa State Univ., 1995.
• 35: Eric Rotenberg, Using variable-MHz microprocessors to efficiently handle uncertainty in real-time systems, Proceedings of the 34th annual ACM/IEEE international symposium on Microarchitecture, December 01-05, 2001, Austin, Texas
• 36: H. Theiling , C. Ferdinand, Combining Abstract Interpretation and ILP for Microarchitecture Modelling and Program Path Analysis, Proceedings of the IEEE Real-Time Systems Symposium, p.144, December 02-04, 1998
• 37: Dean M. Tullsen , Susan J. Eggers , Henry M. Levy, Simultaneous multithreading: maximizing on-chip parallelism, Proceedings of the 22nd annual international symposium on Computer architecture, p.392-403, June 22-24, 1995, S. Margherita Ligure, Italy
• 38: Joachim Wegener , Frank Mueller, A Comparison of Static Analysis and Evolutionary Testing for the Verification of Timing Constraints, Real-Time Systems, v.21 n.3, p.241-268, November 2001 [doi>10.1023/A:1011132221066]
• 39: Randall T. White , Christopher A. Healy , David B. Whalley , Frank Mueller , Marion G. Harmon, Timing Analysis for Data Caches and Set-Associative Caches, Proceedings of the 3rd IEEE Real-Time Technology and Applications Symposium (RTAS '97), p.192, June 09-11, 1997
• 40: Randall T. White , Frank Mueller , Chris Healy , David Whalley , Marion Harmon, Timing Analysis for Data and Wrap-Around Fill Caches, Real-Time Systems, v.17 n.2-3, p.209-233, Nov. 1999 [doi>10.1023/A:1008190423977]
• 41: Wayne Yamamoto , Mario Nemirovsky, Increasing superscalar performance through multistreaming, Proceedings of the IFIP WG10.3 working conference on Parallel architectures and compilation techniques, p.49-58, June 27-29, 1995, Limassol, Cyprus
• 42: N. Zhang , A. Burns , M. Nicholson, Pipelined processors and worst case execution times, Real-Time Systems, v.5 n.4, p.319-343, Oct. 1993 [doi>10.1007/BF01088834]
• 43: http://developer.intel.com/design/intelxscale/benchmarks.htm
• 44: "C-lab: WCET Benchmarks," http://www.c-lab.de/home/en/download.html.