14712997
Proactive QoS negotiation in asynchronous real-time distributed systems
We present a fast, proactive, quality of service (QoS) negotiation algorithm called Best Effort Negotiation (or BEN), for asynchronous real-time distributed systems. BEN considers an application model where trans-node application timeliness and fault-tolerance requirements are expressed using benefit functions, and anticipated workload and system failure rates during future time intervals are expressed using adaptation functions and reliability functions, respectively. Furthermore, BEN considers an adaptation model where subtasks of application tasks are replicated at run-time for tolerating failures as well as for sharing workload increases. Given such models, the objective of the algorithm is to maximize the sum of aggregate real-time and fault-tolerance benefits during the time window of adaptation functions. Since determining the optimal solution is computationally intractable, BEN heuristically computer sub-optimal resource allocations in polynomial-time. To determine how well BEN performs, we describe another algorithm called HLC, that is inspired by the well-known Hill Climbing heuristic. We show that HLC is significantly slower than BEN. However, our experimental studies reveal that the performance of BEN, in general, is as good as that of HLC.
6241696
A formally verified application-level framework for real-time scheduling on POSIX real-time operating systems
We present a framework, called meta scheduler, for implementing real-time scheduling algorithms. The meta scheduler is a portable middleware layer component designed for implementations over POSIX-compliant operating systems. It accommodates pluggable real-time scheduling algorithms while offering the flexibility of platform independence - the singular underlying OS requirement is the now nearly ubiquitous POSIX compliance. The versatility of pluggable schedulers positions the meta scheduler for deployment in an interoperable heterogeneous real-time environment. We present the design of the meta scheduler and outline its implementation. Furthermore, we present a mechanized correctness verification using the UPPAAL model checker. Prototype implementation of the meta scheduler over QNX Neutrino real-time operating system demonstrates high performance and a small footprint.
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.
13006853
Novel likelihood estimation technique based on boosting detector
This paper presents novel likelihood estimation to be used for particle filter based object tracking. The likelihood estimation is built upon cascade object detector trained with Gentle AdaBoost (GAB), in order to capture the probability of existence of object. Two strategies are adopted to construct the likelihood functions: probability-intra-stage (PIS) corresponding to real output of each weak classifier in the same stage, and probability-outer-stage (POS) corresponding to the depth reached in the cascade detector. Five kinds of likelihood functions are thus proposed based on the trained GAB detector. Our experiment shows the likelihood functions are able to characterize probabilistically the existence of object accurately, having much higher confidence value in object regions than that in background, and that the integral strategy of PIS and POS is the best choice.
6463215
Design and implementation of parallel video encoding strategies using divisible load analysis
The processing time needed for motion estimation usually accounts for a significant part of the overall processing time of the video encoder. To improve the video encoding speed, reducing the execution time for motion estimation process is essential. Parallel implementation of video encoding systems using either the software or the hardware approach has attracted much attention in the area of real time video coding. In this paper, we attempt to implement a video encoder on a bus network. Usually, for such a parallel system, the key concern is associated with partitioning and balancing of the computational load among the processors such that the overall processing time of the video encoder is minimized. With the use of the divisible load theory (DLT) paradigm, a strip-wise load partitioning/balancing scheme, a load distribution strategy, two implementation strategies are developed to exploit the data parallelism inherent in the video encoding process. The striking feature of our design is that,both the granularity of the load partitions and all the associated overheads caused during parallel video encoding process can be explicitly considered. This significantly contributes to the minimization of the overall processing time of the video encoder. Extensive experimental studies are carried out to test the effectiveness of the proposed strategies. The performance of the parallel video encoder is quantified using the metrics speedup and performance gain, respectively. The experimental results show that our strategies are effective for exploiting the available parallelism inherent in the video encoding process and provide a theoretical insight on how to analytically quantify and minimize the overall processing time of a parallel system. The proposed strategies can be easily extended and applied to improve other existing parallel systems.
46149042
Data reconciliation for real-time optimization of an industrial coke-oven-gas purification process
Online optimization is more and more used in the chemical industry to run a process near its optimum operating condition by providing real-time computed optimal set-points to the distributed control system. Process measurements are necessary for these applications to determine the actual state of the process and to increase the accuracy of the model with parameter estimation techniques. However, these measurements usually contain random as well as gross errors which have to be identified and eliminated before the measurements are used for online optimization. In this contribution, a data reconciliation approach was integrated into an online optimization framework for the ammonia hydrogen sulfide circulation scrubbing, a common industrial coke-oven-gas purification process. We used a rigorous rate-based model to describe this reactive absorption and desorption process. To increase the accuracy of the model, we estimated several process parameters using a sequential parameter estimation approach. Data reconciliation was performed based on simple component balances to achieve model-consistent data and to identify measurement biases. The model was then validated online on a pilot plant by connecting the estimation package through the process control system. Based on the online measured data, operating cost minimization was carried out and the computed optimal set-points realized real-time. A satisfactory agreement between measured data and optimization was achieved.
13285231
Analog and RF circuit macromodels for system-level analysis
Design and validation of mixed-signal integrated systems require system-level model abstractions. Generalized Volterra series based models have been successfully applied for analog and RF component macromodels, but their complexity can sometimes limit their utility for time-varying systems and large circuits with complex device models or numerous parasitics. In this paper we propose simple and efficient analog and RF circuit macromodels that provide accurate model abstractions for large, complex time-varying circuits over frequency bands of interest. By starting with the system-level block diagram model structures and focusing on the narrow RF bands, the proposed macromodels can efficiently capture the nonlinear behavior as well as the impact of RLC coupling parasitics via compact reduced-order model forms. While the macromodel can trade accuracy for simplicity in terms of the number of frequency expansion points, we find that expansion about one frequency point provides the accuracy required for system-level analysis of most RF and narrow-band analog components. The macromodel form corresponds to block diagram structures that are easily incorporated into our system-level simulation tool based on Simulink.
10769697
Advanced control flow in Java card programming
Java Card technology simplifies the development of smart card applications by providing a high-level programming language similar to Java. However, the master-slave programming model used in current Java Card platform creates control flow difficulties when writing complex card programs, making it inconvenient, tedious, and error-prone to implement Java Card applications. This paper examines these drawbacks of the master-slave model and proposes a concurrent thread model for developing future Java Card programs, which is much closer to conventional Java network programming. This paper also presents a code translation algorithm and a corresponding tool that makes it possible to write card programs in the concurrent thread model without losing compatibility with the existing Java Card API.