# Browsing by Subject "Real-time data processing"

Now showing 1 - 5 of 5

- Results Per Page
1 5 10 20 40 60 80 100

- Sort Options
Ascending Descending

Item Design of real-time virtual resource architecture for large-scale embedded systems(2004) Feng, Xiang; Mok, Aloysius Ka-Lau.Show more Embedded computers have become pervasive and complex. Every microwave oven has one. The Volvo S80 has more than fifty. A Boeing 777-300 has hundreds. Meanwhile, more and more embedded systems are inter-connected to perform so- phisticated functions on their hosts such as the air information management sys- tems on modern aircrafts. However, due to real-time and fault-tolerance concerns, embedded systems are traditionally implemented on dedicated hardware. This ap- proach entails at least three serious consequences: firstly, profligate and rigid usage of resources necessitated by the binding of subsystems to hardware platforms; sec- ondly, significantly more difficult system integration because individually developed and tested systems are not guaranteed to work in combination; thirdly, the lack of higher-level system control because conceptually indivisible functions are isolated on the hardware level. These problems have caused not only financial loss such as unusable systems due to the high cost of unjustified resource redundancy and integration failures, but also the loss of human lives as exemplified by a number of fatal accidents induced by the third problem. It is critical that system engineers have a solid basis for addressing these fundamental design problems in large-scale real-time embedded systems. An ideal solution should achieve a complete separa- tion of concerns so that: (1) each task group may be executed as if it had access to its own dedicated resource, (2) there is minimal interaction between the resource level scheduler and the task level scheduler, and (3) in case of hardware failure, task groups could easily migrate to other resources. Towards this end, in this dissertation we introduce the notion of a Real-Time Virtual Resource (RTVR) which operates at a fraction of the rate of the shared physical resource and whose rate of operation varies with time but is bounded. Tasks within the same task group are scheduled by a task level scheduler that is specialized to the real-time requirements of the tasks in the group. The scheduling problems on both task level and resource level are analyzed. We specifically investigate RTVRs on the integer domain. For the case of regular resource partitioning, we show that the utilization bounds of both fixed- priority scheduling and dynamic-priority scheduling remain unchanged from those for dedicated resources. We determine the utilization bounds for the more general case of irregular partitioning. In particular, both types of partitions can be effi- ciently constructed by exploiting compositionality properties vis-a-vis the regularity measure. We further extend the applicability of the RTVR in several directions. First, we propose a hierarchical real-time virtual resource model that permits resource partitioning to be extended to multiple levels. Through this model, partitions on each level are scheduled as if they had access to a dedicated resource. Interference between neighboring partition levels is also minimized. Second, we apply RTVR to gang scheduling which is a popular scheduling technique used in parallel systems. We show that the clean isolation between resource-level and task-level scheduling makes RTVR an ideal candidate for implementing the gang scheduling solution in the real-time systems environment. Third, RTVRs in distributed environments are also discussed and end-to-end delay of a series of RTVRs is calculated. Finally, we investigate the resource locking issues in RTVR and present a resource server solution which has a highly efficient admission test. We also present an optimization scheme called Partition Coalition which is based on the server solution and which can substantially reduce the blocking time due to resource locking. These results provide a foundation for implementing RTVR on small-scale multiprocessor or processor cluster systems that are increasingly available. Based on the previous theoretical framework, we implement RTVRs on the Linux 2.4 kernel. The first RTVR implementation uses a static resource level sched- uler which can be applied to systems with predefined application task sets. The second implementation has a novel dynamic resource level scheduler under which task groups can join and leave dynamically. We further virtualize network devices. Several experiments are conducted to measure system performance in various as- pects such as the effect of the scheduling quantum size, interrupt request response time and scheduling overhead. The experiments demonstrate that RTVRs can be efficiently implemented while satisfying their theoretical properties.Show more Item Integration of hard real-time schedulers(2004) Wang, Weirong; Mok, Aloysius Ka-Lau.Show more Over the last few decades, numerous research results have been obtained on scheduling specific real-time workloads to run on dedicated resources. In the last few years, research in scheduler composition on shared resources has attracted increasing attention for the following reasons. The capacities of resources in real-time embedded systems, such as processors, communications channels, have been growing rapidly. These hardware advances create possibilities for more complex and integrated functionalities that share the same resources. Heterogeneous workloads are now allocated to shared resources in contemporary designs. The complexity of the scheduler is accordingly increased. Approaches in scheduler composition have been proposed as a divide-and-conquer strategy to deal with the complexity of scheduler design for these integrated systems. Most of the scheduler composition approaches that have been proposed an be treated within a framework of two-layers: coordinator and components. This dissertation overs our contributions in these two layers, namely, Class-based Component Composition (CCC) approach in the layer of coordinating mechanisms and pre-scheduling in the layer of component construction. We propose CCC for composing independent components in an open environment. CCC uses a workload classification scheme to guarantee that the supply of shared resource always meets the hard-real-time constraints for on-budget workloads. It also aims to achieve a balance over multiple design objectives including composition overhead, overload handling and accommodating the range of real-time applications. A pre-schedule is a static schedule that does not require constant and completely predictable rate of resource supply. We present a sound, complete, and PTIME basic pre-scheduler based on Linear Programming (LP). Since in finitely small slices of time are not implementable in time-domain multiplexing for resources with non-negligible context switch overheads, it is desirable to de ne and solve the pre-scheduling problem on the domain of integers. We construct a rational-to-integral pre-schedule transformer based on a novel technique which we all "round-and-compensate". This transformer is sound, complete and runs in PTIME. We also present an extension of the basic pre-scheduler for solving precedence constraints, and show two examples on how to do resource supply analysis in our framework.Show more Item Joint source-channel distortion modeling for image and video communication(2006) Sabir, Muhammad Farooq; Bovik, Alan C. (Alan Conrad), 1958-; Heath, Robert W., Jr, 1973-Show more Real-time image and video communication is becoming common in commercial wireless systems. Images and videos have high bandwidth and low latency requirements. Therefore, joint source-channel coding (JSCC) has become very important for wireless image and video communication, especially for real-time applications. An important component of practical JSCC schemes is a distortion estimate that can predict the quality of compressed images and videos at various source coding rates and channel bit error rates. The usual approach in the JSCC literature for quantifying the distortion due to quantization and channel errors is to estimate it via simulations or rate-distortion curves. Where these methods are accurate, they are not feasible for real-time applications because of their computational complexity. For real-time applications, distortion should be estimated using low complexity distortion models. In this dissertation, a distortion model for image transmission is proposed. This model predicts the amount of distortion introduced in a set of images due to quantization and channel errors in a joint manner. The effects of important image coding techniques such as differential coding, entropy coding and run-length coding are taken into account by this model. Results show that this model predicts the distortion with high accuracy. Another model for transmission of video sequences is also proposed in this dissertation. This model predicts the amount of distortion in the coded video sequences due to quantization and channel bit errors. The effects of distortion propagation to subsequent frames due to motion estimation and prediction are also modeled by this distortion model. Distortion is predicted with high accuracy by this model. Unequal power allocation for image and video communication is another research area closely related to JSCC. As an application of the distortion models proposed in this dissertation, I also propose an unequal power allocation scheme for transmission of images over multiple-input multiple-output (MIMO) systems. Data streams of unequal importance are transmitted over separate antennas using unequal power such that the distortion is minimized under a power constraint. Results show that this scheme achieves high quality gains as compared to equal power allocation.Show more Item Real time computed tomographic reconstruction(1995-08) Zheng, Xiaolu, 1964-; Not availableShow more Item Specification and analysis of timing properties in real-time systems(1988) Jahanian, Farnam; Mok, Aloysius Ka-LauShow more This dissertation proposes a formalism for the specification and verification of timing properties of real-time systems. Reasoning about properties of a real-time system requires one to consider both relative and absolute timing of events. Relative timing concerns the order in which events occur, such as mutual exclusion and precedence constraint properties. Absolute timing concerns the stringent timing restrictions imposed on a system, such as a response time deadline or a minimum elapsed time between occurrences of two events. The approach is based on Real Time Logic (RTL), a logic invented primarily for the specification of both relative and absolute timing of events. The notion of an event occurrence is central to RTL; an event occurrence marks a point in time which is of significance to the behavior of a system. Hence, concurrency is modeled as a partial ordering of the event occurrences in the system. A system specification and a property to be verified can be expressed as arithmetical relations on algebraic expressions involving the event occurrences. To verify the property with respect to the system specification, we prove that the property is a theorem derivable from the specification. Relationship of RTL to Presburger Arithmetic is discussed and a verification technique based on inequality provers is explored. The dissertation also introduces a specification language, Modechart, for real-time systems. The semantics of Modechart is described in terms of RTL formulas. In Modechart, we make use of the concept of modes which can be thought of as partitioning the state space of a system. Intuitively, modes can be viewed as control information that impose structure on the operation of a system. Modes are arranged hierarchically. Furthermore, modes at the same level of hierarchy can be related in one of two ways: in series or in parallel. A transition can be specified between two modes in series, but no transition is allowed between modes in parallel. The language allows sporadic/periodic actions in modes as well as constructs for specifying timing constraints such as delays and deadlines on mode transitions. Verification procedures are introduced for showing a Modechart specification satisfies a property expressed as an RTL formula.Show more