Using variable-MHz microprocessors to efficiently handle uncertainty in real-time systems

ABSTRACT

Guaranteed performance is critical in real-time systems because correct operation requires tasks complete on time. Meanwhile, as software complexity increases and deadlines tighten, embedded processors inherit high-performance techniques such as pipelining, caches, and branch prediction. Guaranteeing the performance of complex pipelines is difficult and worst-case analysis often under-estimates the microarchitecture for correctness. Ultimately, the designer must turn to clock frequency as a reliable source of performance. The chosen processor has a higher frequency than is needed most of the time, to compensate for uncertain hardware enhancements --- partly defeating their intended purpose.We propose using microarchitecture simulation to produce accurate but not guaranteed-correct worst-case performance bounds. The primary clock frequency is chosen based on simulated-worst-case performance. Since static analysis cannot confirm simulated-worst-case bounds, the microarchitecture is also backed up by clock frequency reserves. When running a task, the processor periodically checks for interim microarchitecture performance failures. These are expected to be rare, but frequency reserves are available to guarantee the final deadline is met in spite of interim failures.Experiments demonstrate significant frequency reductions, e.g., -100 MHz for a peak 300 MHz processor. The more conservative worst-case analysis is, the larger the frequency reduction. The shorter the deadline, the larger the frequency reduction. And reserve frequency is generally no worse than the high frequency produced by conventional worst-case analysis, i.e., the system degrades gracefully in the presence of transient performance faults.

REFERENCES

• 1: R. Arnold, F. Mueller, D. Whalley, and M. Harmon. Bounding worst-case instruction cache performance. 15th Real-Time Systems Symposium, 1994.
• 2: D. Burger, T. Austin, and S. Bennett. Evaluating Future Microprocessors: The Simplescalar Toolset. Technical Report CS-TR-96-1308, Computer Sciences Department, University of Wisconsin - Madison, July 1996.
• 3: J. Engblom and A. Ermedahl. Modeling complex flows for worst-case execution time analysis. 21st Real-Time Systems Symposium, Nov. 2000.
• 4: J. Fisher, P. Faraboschi, and G. Desoli. Custom-fit processors: Letting applications define architectures. Technical Report HPL-96-144, HP Labs, Oct. 1996.
• 5: Kinshuk Govil , Edwin Chan , Hal Wasserman, Comparing algorithm for dynamic speed-setting of a low-power CPU, Proceedings of the 1st annual international conference on Mobile computing and networking, p.13-25, November 13-15, 1995, Berkeley, California, United States [doi>10.1145/215530.215546]
• 6: D. Grunwald, P. Levis, C. Morrey III, M. Neufeld, and K. Farkas. Policies for dynamic clock scheduling. Symp. on Operating Systems Design and Implementation, Oct. 2000.
• 7: Inki Hong , Miodrag Potkonjak , Mani B. Srivastava, On-line scheduling of hard real-time tasks on variable voltage processor, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.653-656, November 08-12, 1998, San Jose, California, United States [doi>10.1145/288548.289105]
• 8: I. Hong , G. Qu , M. Potkonjak , M. B. Srivastava, Synthesis Techniques for Low-Power Hard Real-Time Systems on Variable Voltage Processors, Proceedings of the IEEE Real-Time Systems Symposium, p.178, December 02-04, 1998
• 9: 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
• 10: Sung-Kwan Kim , Sang Lyul Min , Rhan Ha, Analysis of the Impacts of Overestimation Sources on the Accuracy of Worst Case Timing Analysis, Proceedings of the 20th IEEE Real-Time Systems Symposium, p.22, December 01-03, 1999
• 11: C. M. Krishna , Yann-Hang Lee, Voltage-Clock-Scaling Adaptive Scheduling Techniques for Low Power in Hard Real-Time Systems, Proceedings of the Sixth IEEE Real Time Technology and Applications Symposium (RTAS 2000), p.156, May 31-June 02, 2000
• 12: Yann-Hang Lee , C. M. Krishna, Voltage-Clock Scaling for Low Energy Consumption in Real-Time Embedded Systems, Proceedings of the Sixth International Conference on Real-Time Computing Systems and Applications, p.272, December 13-15, 1999
• 13: 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
• 14: 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
• 15: Jacob R. Lorch , Alan Jay Smith, Improving dynamic voltage scaling algorithms with PACE, Proceedings of the 2001 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.50-61, June 2001, Cambridge, Massachusetts, United States
• 16: Thomas Lundqvist , Per Stenström, Timing Anomalies in Dynamically Scheduled Microprocessors, Proceedings of the 20th IEEE Real-Time Systems Symposium, p.12, December 01-03, 1999
• 17: D. Mossé, H. Aydin, B. Childers, and R. Melhem. Compiler-assisted dynamic power-aware scheduling for real-time applications. Workshop on Compilers and Operating Systems for Low Power, Oct. 2000.
• 18: T. Pering, T. Burd, and R. Brodersen. The simulation of dynamic voltage scaling algorithms. Symp. on Low Power Electronics, 1995.
• 19: Youngsoo Shin , Kiyoung Choi , Takayasu Sakurai, Power optimization of real-time embedded systems on variable speed processors, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 20: M. Weiser, B. Welch, A. Demers, and S. Shenker. Scheduling for reduced cpu energy. 1st Symp. on Operating Systems Design and Implementation, Nov. 1994.
• 21: "EEMBC: Embedded Microprocessor Benchmark Consortium," http://www.eembc.org.
• 22: "C-lab: WCET Benchmarks," http://www.c-lab.de/home/en/download.html.