Rational Interpolation for Real-Time System Analysis

在过去的几年里，嵌入式应用中的实时系统激增。许多这样的系统被用于生命关键和其他重要的应用程序，在这些应用程序中，如果计算机无法在某些最后期限前完成，可能会产生灾难性的后果。因此，需要准确地评估这种计算机的可靠性。实时系统中的故障可能由于定时以及诸如硬件故障等传统原因而发生。计时超限通常是计算机的各种元件之间复杂的一系列交互的结果，诸如个别应用程序任务、操作系统、调度算法、系统体系结构、组件瞬时和永久性故障特征等等。在不采取简化假设的情况下，很难在分析模型中考虑这种相互作用，这对模型的准确性和有效性提出了质疑。此外，验证分析模型的传统模拟非常困难，因为正在验证的故障率往往非常低：涉及低至0.000000001的系统故障率。早些时候，美国国家科学基金会资助的一个项目开发了有理插值法，并在可能的计算应用中展示了它的有效性。它创建了一个框架，在该框架中可以攻击各种困难的建模、控制和优化问题。结果表明，有理插值法是一个强有力的工具，可以用来补充其他可靠性和性能评估机制，特别是在预测极低的故障率方面。该项目将涉及基于实时系统的有理插补的技术和工具的开发。虽然重点将放在实时系统上，但结果预计也将有助于评估其他应用中的计算机，如随机算法。

Real-time systems in embedded application have proliferated over the past few years. Many such systems are being used in life-critical and other important applications, where the failure of the computer to meet some deadlines can have disastrous consequences. The need therefore exists to accurately evaluate the reliability of such computers. Failure in a real-time system can occur due to timing as well as to traditional causes such as hardware failure. Timing overruns are often the consequence of a complicated series of interactions between various elements of the computer, such as individual application tasks, the operating system, the scheduling algorithm, the system architecture, component transient and permanent failure characteristics among other things. It is hard to take account of such interactions in analytical models without resorting to simplifying assumptions which raise questions about the models' accuracy and validity. Furthermore, traditional simulation to validate analytical models is very difficult because the failure rates that are being validated tend to be very low: system failure rates as low as .000000001 are involved. An earlier NSF-funded project developed the Rational Interpolation technique, and showed its usefulness in may compute applications. It created a framework in which various difficult modeling, control, and optimization issues can be attacked. The results indicate that Rational Interpolation is a powerful tool that can be used to complement other mechanisms of reliability and performance evaluation, especially in predicting very low failure rates. This project will involve the development of techniques and tools based on Rational Interpolation for real-time systems. While the focus will be on real-time systems, the results are expected to be useful in evaluating computers in other applications as well, such as random algorithms.