A fast algorithm for scheduling imprecise computations with timing constraints to minimize weighted error
A fast algorithm for scheduling imprecise computations with timing constraints to minimize weighted error
复制标题
一种快速算法，用于调度具有时间约束的不精确计算，以最小化加权误差
DOI：
10.1109/real.2000.896019
复制
发表时间：
2000
期刊：
影响因子：
--
通讯作者：
Ching
中科院分区：
文献类型：
--
作者：
W. Shih;Che;Ching
在不精确的计算模型中，安排不同权重的任务非常困难。不精确计算模型中的每个任务在逻辑上分解为强制性子任务和可选子任务。必须在截止日期之前完全执行强制性子任务，以产生可接受的结果；可选的子任务是在强制性子任务后开始以完善结果的。任务结果中的错误是通过可选子任务的未执行部分的处理时间来衡量的。本文提出了一种快速算法，用于安排不准确的计算，并在UniProcessor系统上的时序限制。所提出的算法可以通过时间复杂性O（n log/sup 2/n）获得不同加权任务的最佳时间表。
Scheduling tasks with different weights in the imprecise computation model is rather difficult. Each task in the imprecise computation model is logically decomposed into a mandatory subtask and an optional subtask. The mandatory subtask must be completely executed before a deadline to produce an acceptable result; the optional subtask begins after the mandatory subtask to refine the result. The error in the results of a task is measured by the processing time of the unexecuted portion of the optional subtask. This paper proposes a fast algorithm for scheduling imprecise computation with timing constraints on uniprocessor systems. The proposed algorithm can obtain the optimal schedule for different weighted tasks with time complexity O(n log/sup 2/n).