Imprecise task scheduling and overload management using OR-ULD

This paper evaluates the OR-ULD (Overload Resolution using Utility Loss Density) algorithm for imprecise computation workloads, where tasks are decomposed into one mandatory task and one optional task. OR-ULD is a value-driven overload resolution algorithm running in O(n log n) time, where n is the number of tasks. The algorithm is invoked only in case of transient overloads. By representing error using value functions, we get a general model for representing quality tradeoffs. Our performance studies show that OR-ULD overall performs better than the MF (Mandatory First) algorithm in reducing the total error and the total weighted error. In addition, OR-ULD minimizes the number of discarded optional tasks. The approach provides the flexibility that enables multiple strategies to be used to resolve overloads, e.g., overloads may be resolved by replacing transactions with contingency transactions, and non-critical regular transactions may be dropped or postponed