A Metric for Quantifying Similarity between Timing Constraint Sets in Real-Time Systems

作者：Yu Yue; Ren Shangping^*; Hu Xiaobo Sharon

来源：ACM Transactions on Design Automation of Electronic Systems, 2011, 16(3): 34.

DOI：10.1145/1970353.1970368

• Design
• Measurement
• Theory
• Verification
• Timing constraints
• timing constraint similarities
• quality of service
• real-time systems
• scheduling
• constraint satisfaction
• timing constraint feasibility region

Real-time systems are systems in which their timing behaviors must satisfy a specified set of timing constraints and they often operate in a real-world environment with scarce resources. As a result, the actual runtime performance of these systems may deviate from the design, either inevitably due to unpredictable factors or by intention in order to improve system's other Quality-of-Service (QoS) properties. In this article, we first introduce a new metric, timing constraint set similarity, to quantify the resemblance between two different timing constraint sets. Because directly calculating the exact value of the metric involves calculating the size of a polytope which is a # P-hard problem, we instead introduce an efficient method for estimating its bound. We further illustrate how this metric can be exploited for improving system predictability and for evaluating trade-offs between timing constraint compromises and the system's other QoS property gains.

• 出版日期2011-6