13992284
CPU scheduling for statistically-assured real-time performance and improved energy efficiency
We present a CPU scheduling algorithm, called Energy-efficient Utility Accrual Algorithm (or EUA), for battery-powered, embedded real-time systems. We consider an embedded software application model where repeatedly occurring application activities are subject to deadline constraints specified using step time/utility functions. For battery-powered embedded systems, system-level energy consumption is also a primary concern. We consider CPU scheduling that (1) provides assurances on individual and collective application timeliness behaviors and (2) maximizes system-level timeliness and energy efficiency. Since the scheduling problem is intractable, EUA heuristically computes CPU schedules with a polynomial-time cost. Several properties of EUA are analytically established, including timeliness optimality during under-load situations and statistical assurances on timeliness behavior. Further, our simulation results confirm EUA's superior performance.
388246
On the joint utility accrual model
Summary form only given. We extend Jensen's 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.
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.
61408369
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
7266719
Two processor scheduling with real release times and deadlines
In a hard real-time system, critical tasks are subject to timing constraints such as release times and deadlines. All timing constraints must be satisfied when tasks are executed. Nevertheless, given a set of tasks, finding a feasible schedule which satisfies all timing constraints is NP-complete even on one processor.In this paper, we study the following special non-pre-emptive two processor scheduling problem: Given a set of UET (Unit Execution Time) tasks with arbitrary precedence constraints, individual real release times and deadlines, find a feasible schedule on two identical processors whenever one exists. The complexity status of this problem has been open for a long time. we propose the first polynomial algorithm for this problem. Our algorithm is underpinned by the key consistency notion: successor-tree-consistency. The time complexity of our algorithm is O(n4), where n is the number of tasks.
10888393
Subsequence matching on structured time series data
Subsequence matching in time series databases is a useful technique, with applications in pattern matching, prediction, and rule discovery. Internal structure within the time series data can be used to improve these tasks, and provide important insight into the problem domain. This paper introduces our research effort in using the internal structure of a time series directly in the matching process. This idea is applied to the problem domain of respiratory motion data in cancer radiation treatment. We propose a comprehensive solution for analysis, clustering, and online prediction of respiratory motion using subsequence similarity matching. In this system, a motion signal is captured in real time as a data stream, and is analyzed immediately for treatment and also saved in a database for future study. A piecewise linear representation of the signal is generated from a finite state model, and is used as a query for subsequence matching. To ensure that the query subsequence is representative, we introduce the concept of subsequence stability, which can be used to dynamically adjust the query subsequence length. To satisfy the special needs of similarity matching over breathing patterns, a new subsequence similarity measure is introduced. This new measure uses a weighted L1 distance function to capture the relative importance of each source stream, amplitude, frequency, and proximity in time. From the subsequence similarity measure, stream and patient similarity can be defined, which are then used for offline and online applications. The matching results are analyzed and applied for motion prediction and correlation discovery. While our system has been customized for use in radiation therapy, our approach to time series modeling is general enough for application domains with structured time series data.
10467092
Marshalgen: A Package for Semi-Automatic Marshaling of Objects
Marshaling or serialization of objects is an important component of both distributed and parallel computing. Current systems impose a significant burden on the programmer for describing the marshaling of complex, recursive data structures. Marshalgen provides a semi-automatic process for marshaling in C and C++. Marshalgen avoids the need for complex IDLs and auxiliary routines. It is based on annotations of the existing source code.
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
8588311
Perceptually lossless medical image coding
A novel perceptually lossless coder is presented for the compression of medical images. Built on the JPEG 2000 coding framework, the heart of the proposed coder is a visual pruning function, embedded with an advanced human vision model to identify and to remove visually insignificant/irrelevant information. The proposed coder offers the advantages of simplicity and modularity with bit-stream compliance. Current results have shown superior compression ratio gains over that of its information lossless counterparts without any visible distortion. In addition, a case study consisting of 31 medical experts has shown that no perceivable difference of statistical significance exists between the original images and the images compressed by the proposed coder.