University of Houston • University of Houston-Clear Lake • ISSO Annual Report Y2007• 81-82
FOLLOW-UP REPORT — INNOVATIONS AND NEW DEVELOPMENTS
Progress on three projects:
Quality of service and systems for spacecraft and rovers
Abstract—These three projects are closely related to the ultimate goal of building fully verified space vehicles and systems that are: (1) reliable, (2) adaptive, (3) energy-efficient, (4) schedule-optimized, and (5) capable of high quality of service.
1. Optimizing Quality of Service in Adaptive Optics Systems and other (m, k)-firm Real-Time Spacecraft Control Systems
Adaptive optics systems used in surveillance satellites, air, and spacecraft and in astronomical observatories provide high-resolution imaging but have not yet achieved their full potential. In these applications, light from an astronomical object such as a star and, similarly, from a ground object such as a car, is distorted by Earth’s atmosphere. An adaptive optics system employs a high-speed control computer with an array of digital signal processors to periodically adjust a deformable lens or mirror based on the periodic input from a wavefront sensor. The control task must calculate, a thousand times per second, how much and where to deform the lens or mirror to compensate for atmospheric distortion (i.e., wavefront error). The corrected light is then passed through another lens, focusing it into a high-resolution image.
It is clear that the quality of service (QoS) stability over time is critical since increasing the reward following a low-reward interval is undesirable. However, current adaptive optics systems, as well as many other control system applications, have not fully addressed this issue. This project aims to optimize this QoS stability by maximizing the guaranteed performance while maintaining a schedulable task set in periodic firm real-time systems such as adaptive optics systems.
Results
We have introduced the problem of maximizing the guaranteed quality of service while maintaining the schedulability of a task set in an (m,k)-firm real-time system. We proved that the problem is NP-hard and proposed a simple heuristic solution—by greedily increasing the QoS level of the tasks with the maximum “reward ratio” as long as all other tasks have their minimum service level. Our preliminary study has evaluated the solution using the granularity of quality of service rewards, effective processor utilization, total accumulated reward, and instability as performance measures. We like the simplicity of the heuristics and the good performance in minimizing the instability in an overloaded system.
2. Building and verifying
fault-tolerant autonomous real-time systems for space applications
In many NASA missions, autonomous systems and their embedded autonomy software must perform correctly for an extended period of time and make real-time decisions that meet both logical and timing requirements. Furthermore, the autonomy software must tolerate implementation and environment-induced faults. Developing and verifying these systems is especially difficult because of the large (often infinite) state space and execution sequences as well as the uncertainties in the environment in which these systems operate. One focus of NASA’s automated reasoning thrust is to “enhance the autonomous decision-making capabilities of robotic explorers, spacecraft, and mission management systems.” The objectives of this project are to address two key technology areas in the automated reasoning category: (1) adding scalable fault-tolerance in the decision-making autonomy software of a real-time autonomous system; and (2) augmenting the capability of formal verification strategies by providing an alternative based on scalable rulebase analysis to model checking and theorem proving.
Results
Since our approach can transform subsets of the code into self-stabilizing equivalents with different code modifications depending on their syntactic/semantic forms, it is scalable to increasingly large and complex autonomy software systems. Coupled with the compositional analysis/verification strategy that identifies these syntactic/semantic code subsets (described in the second half of the proposal), our overall approach further scales to deriving and verifying highly fault-tolerant autonomy software systems. Ongoing work evaluates this strategy on the modified Ganglia simulation platform.
3. Optimizing System Reward in Battery-Powered Spacecraft and Rovers
Rechargeable batteries are used to operate many spacecraft and autonomous rovers, so their operational periods are limited by their battery supplies. How to use this battery-supplied energy efficiently is a critical issue. Most existing energy-conserving techniques are based on dynamic voltage scaling (DVS) and consider only timing or energy constraints. In a more realistic scenario, we should simultaneously consider three constraints: time, energy, and reward (quality of service). This project investigates two static methods (greedy and dynamic programming) and an on-line method for selecting tasks to optimize system reward while meeting timing constraints and conserving energy. We use simulation experiments to compare the performance of these methods with existing techniques. We study three static methods to select tasks from the task sets: (1) simplified REW-Pack, (2) greedy, and (3) REW-Pack. We compare the reward gained by these three methods. We found that our greedy method often yields a larger total reward value than the REW-Pack. In addition, the greedy method is more efficient than REW-Pack.
Results
In this project, we have developed a static method to schedule an overloaded, battery-powered system. We compare our methods to a previous method. We compare the performance of these four methods in many situations. Our conclusion is as follows: the greedy method often performs better than REW-Pack, especially when the system has limited energy storage capacity and a greater number of processor frequencies and tasks to be performed. In a future project, we plan to develop a combined method that is more suitable in more situations. We will also investigate the best scheduling choice for each system environment.
This project implements power-saving methods and investigates their performance via simulation. In particular, we have compared our static methods with REW-Pack, the only existing technique that deals with all three constraints (time, energy, and reward) but does not perform well in overloaded systems. We believe that our algorithms are more suitable when the energy limit is higher, there is a larger set of processor frequencies, or there is a larger number of tasks.
Publications
Allen, T.L. and Cheng, A.M.K. Real-time, dynamic calculations of polynomial coefficients for use in telemetry. IEEE-CS Real-Time and Embedded Technology and Applications Symposium WIP Session (April 2007).
Andrei, S. and Cheng, A.M.K. Verifying linear real-time logic specifications. IEEE-CS Real-Time Systems Symposium, Tucson, AZ, 333-342 (Dec. 2007).
Lin, J., Chen, Y., and Cheng, A.M.K. On-line burst header scheduling in optical burst switching networks. IEEE Advanced Information Networking Applications (AINA), Japan, (2008) (to appear).
Cheng, A.M.K. Applying (m,k)-firm scheduling to medical and medication systems. Workshop on Software and Systems for Medical Devices and Services (SMDS), in conjunction with IEEE-CS Real-Time Systems Symposium, Tucson, AZ (Dec. 2007).
Cheng, A.M.K. and Wang, Y. A dynamic voltage scaling algorithm for dynamic workloads. J. VLSI Signal Processing—Systems for Signal, Image and Video Technology, published online first (July 2007).
Cheng, A.M.K. and Ras, J. The implementation of the priority ceiling protocol in Ada 2005. ACM Ada Letters 27 (1) published online (April 2007).
Cheng, A.M.K. and Ras, J. The implementation of the priority ceiling protocol in Ada-2005 using a shared memory programming model. IEEE-CS Real-Time and Embedded Technology and Applications Symposium WIP Session (April 2007).
Cheng, A.M.K. and Shang, F. Priority-driven coding and transmission of progressive JPEG images for real-time applications. J. VLSI Signal Processing—Systems for Signal, Image and Video Technology 47, 169-182, published online first (2007).
Cheng, A.M.K. and Zhang, Z. Improving web server performance with adaptive proxy caching in soft real-time mobile applications. J. VLSI Signal Processing—Systems for Signal, Image and Video Technology 47, 103-117, published online first (2007).
Presentations
Cheng, A.M.K. Building safe and secure embedded real-time systems. Invited Speaker, Lamar University, Department of Computer Science, July 30 (2007).
Cheng, A.M.K. Debugging and verification of real-time and embedded systems. Invited Speaker, National Taiwan University, Department of Computer Science and Information Engineering, July 10 (2007).
Cheng, A.M.K. Debugging and verifying of RTL-specified real-time systems. Invited Speaker, Hong Kong University of Science and Technology, Department of Computer Science and Engineering, July 5 (2007).
Cheng, A.M.K. Verification of real-time systems and intrusion detection (recorded in MP4 video). Invited Speaker, seminar series of the Center for Education and Research in Information Assurance and Security (CERIAS), Purdue University, West Lafayette, IN, March 28 (2007).
Proposals
Cheng, A.M.K. Automatic debugging and verification of RTL-specified embedded and real-time systems, NSF, $599,377 (Dec. 2006–Nov. 2009) (submitted).
Institute for Space Systems Operations - Y2007 Annual Report
Copyright © 2008