51883995
Energy-efficient, utility accrual scheduling under resource constraints for mobile embedded systems
We present an energy-efficient real-time scheduling algorithm called the Resource-constrained Energy-Efficient Utility Accrual Algorithm (or ReUA). ReUA considers an application model where activities are subject to time/utility function-time constraints, resource dependencies including mutual exclusion constraints, and statistical performance requirements including probabilistically satisfied, activity (timeliness) utility bounds. Further, ReUA targets mobile embedded systems where system-level energy consumption is a major concern. For such a model, we consider the scheduling objectives of (1) satisfying statistical performance requirements, and (2) maximizing system-level energy efficiency, while respecting resource dependencies. Since the problem is NP-hard, ReUA allocates resources using statistical properties of application cycle demands and heuristically computes schedules with a polynomial-time cost. We analytically establish several timeliness and non-timeliness properties of the algorithm. Further, our simulation experiments illustrate ReUA's effectiveness.
6769302
A utility accrual scheduling algorithm for real-time activities with mutual exclusion resource constraints
This paper presents a uni-processor real-time scheduling algorithm called the generic utility scheduling algorithm (which we refer to simply as GUS). GUS solves a previously open real-time scheduling problem-scheduling application activities that have time constraints specified using arbitrarily shaped time/utility functions and have mutual exclusion resource constraints. A time/ utility function are a time constraint specification that describes an activity's utility to the system as a function of that activity's completion time. Given such time and resource constraints, we consider the scheduling objective of maximizing the total utility that is accrued by the completion of all activities. Since this problem is NP-hard, GUS heuristically computes schedules with a polynomial-time cost of O(n/sup 3/) at each scheduling event, where n is the number of activities in the ready queue. We evaluate the performance of GUS through simulation and by an actual implementation on a real-time POSIX operating system. Our simulation studies and implementation measurements reveal that GUS performs close to, if not better than, the existing algorithms for the cases that they apply. Furthermore, we analytically establish several properties of GUS.
2876560
Utility Accrual Real-Time Scheduling under Variable Cost Functions
We present a utility accrual real-time scheduling algorithm called CIC-VCUA for tasks whose execution times are functions of their starting times (and, potentially, other factors). We model such variable execution times using variable cost functions (or VCFs). The algorithm considers application activities that are subject to time/utility function time constraints, execution times described using VCFs, and mutual exclusion constraints on concurrent sharing of non-CPU resources. We consider the twofold scheduling objective of 1) assuring that the maximum interval between any two consecutive, successful completions of job instances in an activity must not exceed the activity period (an application-specific objective) and 2) maximizing the system's total accrued utility while satisfying mutual exclusion resource constraints. Since the scheduling problem is intractable, CIC-VCUA is a polynomial-time heuristic algorithm. The algorithm statically computes worst-case task sojourn times, dynamically selects tasks for execution based on their potential utility density, and completes tasks at specific times. We establish that CIC-VCUA achieves optimal timeliness during underloads, and tightly upper bounds inter and intratask completion times. Our simulation experiments confirm the algorithm's effectiveness and superiority
5941019
Utility accrual scheduling under joint utility and resource constraints
We extend time/utility functions and utility accrual model with the concept of joint utility functions (or JUFs) that allow an activity's utility to be described as a function of the completion times of other activities and their progress. We also specify the concept of progressive utility that generalizes the previously studied imprecise computational model, by describing an activity's utility as a function of its progress. Given such an extended utility accrual model, we consider the scheduling criterion of maximizing the weighted sum of completion time, progressive, and joint utilities. We present an algorithm called the combined utility accrual algorithm (or CUA)for this criterion. Experimental measurements with an implementation of CUA on a POSIX RTOS illustrate the effectiveness of JUFs in a class of applications of interest to us
15728349
Enhanced End-System Support for Multimedia Transmission over the Differentiated Services Network
Proposed as a scalable solution to provide Quality of Service (QoS) networks, Differentiated Services (DiffServ) architecture enables service providers to offer each customer a range of services that are differentiated on the basis of performance. However, up to now little work discusses how to provide effective communication support for multimedia applications over the differentiated services network. In this paper we present a new enhanced communication approach at the end system to support distributed multimedia applications. Two new mechanisms are highlighted in our approach: enhanced communication stack to support differentiation within one flow, and the network-awareness provision for applications at the end system. Our approach improves the capability of both error resilience and flexible rate control for transmitting compressed multimedia bitstreams, particularly those using scalable coding technologies. We also develop an object-based video transmission system as an application instance to take advantage of the enhanced communication approach. Experimental results demonstrate the effectiveness of our proposed methods.
2473089
Energy-efficient, utility accrual real-time scheduling under the unimodal arbitrary arrival model
We present an energy-efficient real-time scheduling algorithm called EUA*, for the unimodal arbitrary arrival model (or UAM). UAM embodies a "stronger" adversary than most arrival models. The algorithm considers application activities that are subject to time/utility function time constraints, UAM, and the multi-criteria scheduling objective of probabilistically satisfying utility lower bounds, and maximizing system-level energy efficiency. Since the scheduling problem is intractable, EUA* allocates CPU cycles, scales clock frequency, and heuristically computes schedules using statistical estimates of cycle demands, in polynomial-time. We establish that EUA* achieves optimal timeliness during under-loads, and identify the conditions under which timeliness assurances hold. Our simulation experiments illustrate EUA*'s superiority.
6756167
MAC-SCC: medium access control with a separate control channel for multihop wireless networks
The recent research has shown that the basic RTS/CTS approach is not efficient in multihop wireless networks. In this paper, we propose a novel medium access control protocol with a separate control channel (MAC-SCC). A distinct feature of MAC-SCC (compared with other multichannel MAC protocols) is to use two Network Allocation Vectors (NAVs) for the data channel and the control channel, respectively. The transmission of the next data frame can be pre-determined during the current transmission via the separate control channel, and thus the frame collision probability and bandwidth wasted during backoff can be reduced. The system throughput is quantified via simulation. The results show that MAC-SCC yields a throughput gain up to 60% under high traffic load and has a significant lower link failure probability.
18504704
Instruction Scheduling with Timing Constraints on a Single RISC Processor with 0/1 Latencies
In this paper, We propose a faster algorithm for the following instruction scheduling problem: Given a set of UET (Unit Execution Time) instructions with precedence constraints in the form of a DAG(Directed Acyclic Graph), latency constraints where latencies between any two instructions are restricted to be either 0 or 1, timing constraints in the form of individual integer release times and deadlines and a single RISC processor, find a feasible schedule which satisfies all constraints. The time complexity of our algorithm is O(n2 log n) + min{O(ne), O(n2.376)}, where n is the number of instructions and e is the number of edges in the precedence graph. Our algorithm is faster than the existing algorithm which runs in O(n3α(n)) time, where α(n) is the inverse of Ackermann function. In addition, our algorithm can be used to solve the maximum lateness minimization problem in O(n2 log2 n + min{ne, n2.376}) time.
8343325
Instruction Scheduling with Release Times and Deadlines on ILP Processors
ILP (instruction level parallelism) processors are being increasingly used in embedded systems. In embedded systems, instructions may be subject to timing constraints. An optimising compiler for ILP processors needs to find a feasible schedule for a set of time-constrained instructions. In this paper, we present a fast algorithm for scheduling instructions with precedence-latency constraints, individual integer release times and deadlines on an ILP processor with multiple functional units. The time complexity of our algorithm is O(n2 logd)+min{O(de), O(ne)}+min{O(ne), O(n2.376)}, where n is the number of instructions, e is the number of edges in the precedence graph and d is the maximum latency. Our algorithm is guaranteed to find a feasible schedule whenever one exists in the following special cases: 1) one functional unit, arbitrary precedence constraints, latencies in {0,1}, integer release times and deadlines; 2) two identical functional units, arbitrary precedence constraints, latencies of 0, integer release times and deadlines; 3) multiple identical functional units or multiple functional units of different types, monotone interval-ordered graph, integer release times and deadlines; 4) multiple identical functional units, in-forest, equal latencies, integer release times and deadlines. In case 1) our algorithm improves the existing fastest algorithm from O(n2 logn)+min{O(ne), O(n2.376)} to min{O(ne), O(n2.376)}. In case 2) our algorithm improves the existing fastest algorithm from O(ne+n2 logn) to min{O(ne), O(n2.376)}. In case 3) no polynomial time algorithm for multiple functional units of different types was known before
546715
Minimising the Energy Consumption of Real-Time Tasks with Precedence Constraints on a Single Processor
Energy-aware task scheduling is critical for real-time embedded systems. Although dynamic power has traditionally been a primary source of processor power consumption, leakage power is becoming increasingly important. In this paper, we present two optimal energy-aware polynomial-time algorithms for scheduling a set of tasks with release times, deadlines and precedence constraints on a single processor with continuous voltages. Our algorithms are guaranteed to minimise the total energy consumption of all tasks while minimising their maximum lateness under two power models: the dynamic power model where the dynamic power dominates the processor power consumption and the dynamic and leakage power model where both dynamic power and leakage power are significant sources of the processor power consumption. The time complexities of both algorithms are O(n3) , where n is the number of tasks
7613281
New results about the centroid of an interval type-2 fuzzy set, including the centroid of a fuzzy granule
The centroid of an interval type-2 fuzzy set (IT2 FS) provides a measure of the uncertainty of such a FS. Its calculation is very widely used in interval type-2 fuzzy logic systems. In this paper, we present properties about the centroid of an IT2 FS. We also illustrate many of the general results for a T2 fuzzy granule (FG) in order to develop some understanding about the uncertainty of the FG in terms of its vertical and horizontal dimensions. At present, the T2 FG is the only IT2 FS for which it is possible to obtain closed-form formulas for the centroid, and those formulas are in this paper.