Complexity scalability for real-time HEVC encoders

The high efficiency video coding (HEVC) standard achieves improved compression efficiency in comparison to previous standards at the cost of much higher computational complexity and consequently longer processing times, which may compromise real-time software-based video encoding, especially at high resolutions. This article addresses the problem of enabling complexity scalability in HEVC encoders by trading-off processing time for rate–distortion (R–D) performance in a controlled manner. The proposed method is based on dynamic constraining of HEVC coding treeblocks (CTBs) by limiting the prediction block (PB) shapes and the maximum tree depth used in each CTB, to decrease the number of R–D evaluations performed in the optimization process. The complexity-scalable encoder is capable of adjusting the processing time used in each group of pictures, according to a predefined target. The results show that processing times can be scaled down to 50 % with negligible R–D performance losses and down to 20 % at a maximum BD-PSNR decrease of 1.41 dB, which is acceptable in many applications and in power constrained devices. The simplicity of the scaling algorithm and the possibility of continuous adjustment of the scaling factor make it amenable to control real-time software-based HEVC video encoders.     

Evaluating scalability in heterogeneous systems

This paper presents a new expression for an isoefficiency function which can be applied both to homogeneous and heterogeneous systems. Using this new function, called H-isoefficiency, it is now possible to analyze the scalability of heterogeneous clusters. In order to show how this new metric can be used, a theoretical a priori analysis of the scalability of a Gauss Elimination algorithm is presented, together with a model evaluation which demonstrates the correlation between the theoretical analysis and the experimental results.     

Evaluating the scalability of distributed systems

Many distributed systems must be scalable, meaning that they must be economically deployable in a wide range of sizes and configurations. This paper presents a scalability metric based on cost-effectiveness, where the effectiveness is a function of the system's throughput and its quality of service. It is part of a framework which also includes a sealing strategy for introducing changes as a function of a scale factor, and an automated virtual design optimization at each scale factor. This is an adaptation of concepts for scalability measures in parallel computing. Scalability is measured by the range of scale factors that give a satisfactory value of the metric, and good scalability is a joint property of the initial design and the scaling strategy. The results give insight into the scaling capacity of the designs, and into how to improve the design. A rapid simple bound on the metric is also described. The metric is demonstrated in this work by applying it to some well-known idealized systems, and to real prototypes of communications software     

Analyzing scalability of parallel systems with unbalanced workload

This paper presents a new formulation of the isoefficiency function which can be applied to parallel systems executing balanced or unbalanced workloads. This new formulation allows analyzing the scalability of parallel systems under either balanced or unbalanced workloads. Finally, the validity of this new metric is evaluated using some synthetic benchmarks. The experimental results allow assessing the importance of considering the unbalanced workloads while analyzing the scalability of parallel systems.     

Achieving real-time object detection and tracking under extreme conditions

In this survey, we present a brief analysis of single camera object detection and tracking methods. We also give a comparison of their computational complexities. These methods are designed to accurately perform under difficult conditions such as erratic motion, drastic illumination change, and noise contamination.     

Redundancy and scalability for virtualized MES systems with programmable infrastructure

Virtualization of manufacturing execution system (vMES) workloads offers a set of design and operational advantages to enterprises, the most visible being improved resource utilization and flexibility of the overall solution. This paper explores redundancy and scalability, as other important operational advantages introduced by the use of private clouds for MES virtualization in the context of the programmable infrastructure (PI) concept. PI is a new architectural approach in which the computing infrastructure, represented by resources, networks, storage, becomes dynamic and is controlled by the application, in contrast with traditional architectures where the application has to adapt to a static infrastructure. For MES applications, the adoption of PI has the potential to add a new layer of flexibility and optimization by allowing quick configuration and re-configuration based on environmental changes, especially in the context of virtualization in private cloud where workloads can be provisioned and de-provisioned in real time. In this context, this paper presents the main redundancy and scalability requirements for the workloads identified in ISA-95.03 based solutions and discusses in detail the strategies to assure the redundancy and scalability requirements of these workloads both individually and at the system level. The main contributions of this paper are therefore the introduction of PI combined with private cloud virtualization at the MES layer in order to achieve redundancy and scalability of the control solution. The pilot implementation presented is based on PI concepts and is realized in practice using SOA BPEL and IBM CloudBurst REST APIs. The MES system considered for the pilot implementation adopts a multi-agent vMES architecture having COBASA-type functionality. The experimental results presented in this paper show the system response in a set of failure scenarios, with focus on the reconfiguration time of workloads, and the dynamic response to perturbations in the system.     

实时系统中弹性调度策略

弹性调度面向负载可变的实时系统,通过动态调整任务属性以满足系统的灵活性要求,是一种高效的任务调度策略。针对弹性调度研究中的成果及问题,概述了弹性调度的研究背景,从任务模型、调度模型以及调度算法三个方面对弹性调度的国内外研究进展进行综述,探讨当前研究中存在的问题,并对弹性调度未来研究工作进行分析和展望。     

Monitoring distributed real-time systems

This paper emphasizes the power ofmonitoring of distributed real-time systems as a promising tool for both scientific work and practical purposes. Starting out from a number of well-known problems with today's (industrial) real-time systems, a classification of remedial monitoring applications is given. The most important features of a monitoring system suitable for such purposes are discussed and related to the current research into monitoring of (general) distributed systems. Finally, some of the resulting conceptual issues underlying our prototype VTA monitoring system—currently being under development at our department—are presented.     

Analyzing partially-implemented real-time systems

Most analysis methods for real-time systems assume that all the components of the system are at roughly the same stage of development and can be expressed in a single notation, such as a specification or programming language. There are, however, many situations in which developers would benefit from tools that could analyze partially-implemented systems: those for which some components are given only as high-level specifications while others are fully implemented in a programming language. In this paper, we propose a method for analyzing such partially-implemented real-time systems. We consider real-time concurrent systems for which some components are implemented in Ada and some are partially specified using regular expressions and graphical interval logic (GIL), a real-time temporal logic. We show how to construct models of the partially-implemented systems that account for such properties as run-time overhead and scheduling of processes, yet support tractable analysis of nontrivial programs. The approach can be fully automated, and we illustrate it by analyzing a small example     

Achieving robustness at diagnosis of nonlinear systems

For the systems described by nonlinear dynamic models, consideration was given to the design of robust diagnostic observers. A logic-dynamic approach was proposed to solve this problem.     

Software fault tolerance in real-time systems

The paper proposes a technique for providing software fault tolerance in real-time applications demanding fast response and a high degree of reliability. It is shown that a reasonably flexible interprocess communication can be supported with only a small increase in complexity and overhead. The two most prominent features of the proposed scheme are (1) it attempts to exploit fault-avoidance techniques as much as possible to reduce the overhead of fault tolerance and (2) it controls the propagation of errors so as to enable efficient recovery. Formal proofs of the system operation are developed. Besides showing that the scheme works as expected, the arguments serve to highlight the assumptions needed for provably correct operation. Some issues relating to hardware fault tolerance are also considered.     

实时立体视觉系统中的深度映射

目的 为减少立体图像中由于水平视差过大引起的视觉疲劳。针对实时渲染的立体视觉系统,给出了一种非均匀深度压缩方法。方法 该方法在单一相机空间内,通过不同的投影变换矩阵生成双眼图像,水平视差由投影变换来控制。为减少深度压缩造成的模型变形而带来的瑕疵,将不同深度区域内物体施以不同的压缩比例;将相机轴距表示为深度的连续函数,通过相机轴距推导出在单一相机空间内获取双眼图像的坐标变换,将深度压缩转换为模型的坐标变换,从而保证压缩比例的连续变化。结果 实验结果表明,该方法能有效提高立体图像的质量。结论 该方法简单、高效,可应用于游戏、虚拟现实等实时立体视觉系统。     

Task scheduling in distributed real-time systems

An approach to the flow shop scheduling of the computation process in distributed realtime systems is considered. This approach is based on the concept of a solvable class of systems for which simple optimal scheduling algorithms exist.     

Value-based scheduling in real-time database systems

In a real-time database system, an application may assign avalue to a transaction to reflect the return it expects to receive if the transaction commits before its deadline. Most research on real-time database systems has focused on systems where all transactions are assigned the same value, the performance goal being to minimize the number of missed deadlines. When transactions are assigned different values, the goal of the system shifts to maximizing the sum of the values of those transactions that commit by their deadlines. Minimizing the number of missed deadlines becomes a secondary concern. In this article, we address the problem of establishing a priority ordering among transactions characterized by both values and deadlines that results in maximizing the realized value. Of particular interest is the tradeoff established between these values and deadlines in constructing the priority ordering. Using a detailed simulation model, we evaluate the performance of several priority mappings that make this tradeoff in different, but fixed, ways. In addition, a bucket priority mechanism that allows the relative importannce of values and deadlines to be controlled is introduced and studied. The notion of associating a penalty with transactions whose deadlines are not met is also briefly considered.When this work was done he was with the Computer Sciences Department, University of Wisconsin-Madison.     

Specifying real-time properties in autonomic systems

Increasingly, computer software must adapt dynamically to changing conditions. The correctness of adaptation cannot be rigorously addressed without precisely specifying the requirements for adaptation. In many situations, these requirements involve absolute time, in addition to a logical ordering of events. This paper introduces an approach to formally specifying such timing requirements for adaptive software. We introduce TA-LTL, a timed adaptation-based extension to linear temporal logic, and use this logic to specify three timing properties associated with the adaptation process: safety, liveness, and stability. A dynamic adaptation scenario involving interactive audio streaming software is used to illustrate the timed temporal logic. A number of related papers and technical reports of the Software Engineering and Network Systems Laboratory can be found at the following URL: http://www.cse.msu.edu/sens.     

Resource reclaiming in multiprocessor real-time systems

Most real-time scheduling algorithms schedule tasks with regard to their worst case computation times. Resources reclaiming refers to the problem of utilizing the resources left unused by a task when it executes in less than its worst case computation time, or when a task is deleted from the current schedule. Dynamic resource reclaiming algorithms that are effective, avoid any run time anomalies, and have bounded overhead costs that are independent of the number of tasks in the schedule are presented. Each task is assumed to have a worst case computation time, a deadline, and a set of resource requirements. The algorithms utilize the information given in a multiprocessor task schedule and perform online local optimization. The effectiveness of the algorithms is demonstrated through simulation studies     

Deadlock prevention in concurrent real-time systems

To meet consistency requirements found in concurrent applications, a process must be guaranteed that it will be able to use all resources in a set ofpassive resources (such as shared data structures). To provide predictable execution time required in real-time systems, a process also needs guaranteed access to at least one of a set ofactive resources (such as processors) associated with each passive resource. As such, a concurrent real-time-process has AND-OR resource requirements. If locking is used to provide exclusive access to resources, deadlock is possible since processes can request additional resources while holding other resources. Deadlock detection and recovery techniques and deadlock avoidance techniques typically involve preempting resources or terminating processes, and are therefore inappropriate for real-time systems that require the execution time of processes to be predictable. This paper describes a general resource request condition that we proveprevents deadlock in AND-OR systems. It also describes how we use this AND-OR deadlock prevention technique in a concurrent real-time system.This work is supported in part by the following grants: ONR N000014-89-J-1131 and ARO DAAG-29-84-k-0061.     

Issues in building dynamic real-time systems

The issues involved in building dynamic, hard real-time systems, in which resource availability and requirements are not fixed, are discussed. It is shown that the problem of ensuring timing correctness in dynamic real-time systems has three aspects: resource requirements, resource availability, and guarantees. These issues overlap, and a single mechanism or technique may address several issues. The R-Shell, an object-oriented framework that structures resources in a class hierarchy so that they can be selected or substituted dynamically is described