Regarding the Optimality of Speedup Bounds of Mixed-Criticality Schedulability Tests
Regarding the Optimality of Speedup Bounds of Mixed-Criticality Schedulability Tests
复制标题
关于混合临界可调度性测试的加速界限的最优性
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Zhishan Guo
中科院分区：
文献类型：
--
作者：
Zhishan Guo
许多现有的关于混合关键度（MC）调度的研究（参见[7]的综述）都集中在处理维斯塔尔模型[15]上，其中提供了单个代码的不同WCET估计。这通常是用于确定最坏情况执行时间（WCET）界限的不同工具彼此或多或少保守的结果。已知[1]，在这种模型下的混合关键性（MC）调度是高度难处理的，使得多项式时间最优解是不可能的，除非P = NP。因此，加速比界被广泛应用于MC调度中，用于衡量给定的可并行性分析接近最优的程度。·可并行性测试的加速因子为s（s ≥ 1），如果任何任务集在给定平台上可通过任何算法并行，处理速度为1，则该测试将认为它在速度为s倍的平台上可并行。当然，在推导MC加速器和相关的可扩展性测试时，目标之一是识别/证明一个相对较小的加速比界限（接近1）。最小可能的加速比通常表示为给定MC调度问题的“最优加速比界”。然而，我们想指出的是：·调度器的最优性不应该根据最优加速边界来推导。
Much existing research on Mixed-Criticality (MC) scheduling (see [7] for a review) has focused on dealing with the Vestal model [15], where different WCET estimations of a single piece of code are provided. This is typically a consequence of different tools for determining worst case execution time (WCET) bounds being more or less conservative than each other. It is known [1] that mixed criticality (MC) scheduling under such model is highly intractable, such that polynomial-time optimal solution is impossible unless P = NP . As a result, speedup bound is widely used in MC scheduling for measuring how close to optimal is a given schedulability analysis. • A schedulability test has speedup factor of s(s ≥ 1), if any task set that is schedulable by any algorithm on a given platform with processing speed of 1, it will be deemed schedulable by this test upon a platform that is s times as fast. Of course when deriving MC schedulers and associated schedulability tests, one of the goals is to identify/prove a relative small speedup bound (that is closer to 1). A minimum possible speedup is often presented as the “optimal speedup bound” of a given MC scheduling problem. However, we would like to point out that: • Optimality of scheduler should not be derived against optimal speedup bounds.