RESEARCH

My research interests include Real-Time Systems, Real-Time Scheduling, Fault Tolerance and Low-Power Computing . The main theme of my dissertation has been Reward-Based Scheduling , which offers a unified framework to address these issues simultaneously.

In the following, first the basic concepts of Reward-Based Real-Time Systems are briefly explained, along with Related Models . Then, the main contributions of my dissertation research are summarized in three sections: Periodic Reward-Based Scheduling , FT-Optimality and Dynamic Voltage Scaling for Low-Power Real-Time Systems .

Reward-Based Real-Time Computing

In a real-time system, each task (job) should be completed by a deadline. However, network congestions, dynamic conditions, faults or excessive user demand may easily lead to an overload state, where it is impossible to finish all the workload in a timely manner with perfect accuracy. Under this scenario, resorting to a technique which provides timely but approximate results is crucial for the robustness and/or graceful degradation of the system.

In a Reward-Based System, a task is logically decomposed into two parts: a mandatory part which runs first, producing an approximate result of acceptable quality; and an optional part which refines the mandatory part's output. A large number of today's applications, in fact, can assume this semantic distinction: An image or movie of imperfect visual quality, a skeleton plan, an approximate computation of the target's location can first be obtained by the mandatory part, and later refined by the optional part within the available computational capacity. While the mandatory part must be completed by the task's deadline, the optional execution can be aborted once the deadline arrives.

To quantify the refinement process, a reward function is associated with the execution of each optional part. The reward function will represent the characteristics of the application at hand: it is an increasing (or at least non-decreasing) function of the optional part's computation time. The behavior of most realistic applications (e.g. multi-media, image processing, real-time planning) are best captured by general concave and linear functions.

Related Models

There are a number of Real-time System Models proposed in the literature which provision for the timeliness versus precision trade-off. One of the first such models has been the seminal Imprecise Computation studies, developed by Jane Liu and her colleagues at UIUC, in the early and mid 90's.

IRIS (Increased Reward with Increased Service) research at University of Massachusetts-Amherst (Dey, Kurose, Towsley) was the first to elaborate on the concave reward functions, though only for aperiodic tasks.

Finally, Q-RAM (QoS based Resource Allocation Model) was developed at CMU (Lee, Rajkumar, Siewiorek and Lehoczky) mainly to deal with multi-dimensional QoS requirements of multi-media services. Their research also provided several efficient approximation algorithms for the inherently intractable discrete QoS problem.

Periodic Reward-Based Scheduling

In many real-time applications, tasks are invoked periodically, such as those who receive, process and/or transmit sensor data, audio/video or control signals. Despite the maturity of periodic scheduling research for Hard Real-Time Systems, optimal periodic reward-based scheduling problem was open prior to our work, since the early 90's. The apparent difficulty of periodic reward-based scheduling stems from the equally important requirements of meeting the hard deadlines of mandatory parts and scheduling the optional parts (whose total number of instances during the hyperperiod can be easily exponential) to maximize the total reward. In [4] and [10], for general concave reward functions, we showed: We also showed that, the optimality of identical service times per instance no longer holds for extended models (Fixed Priority Scheduling, deadlines less than the periods), in addition to the intractability of the problem once one drops the concavity assumption.

FT-Optimality

Although the RBS framework allows for timely yet approximate results, the mandatory parts have still hard deadlines and they should be completed within their timing constraints even in the presence of faults. Our work in Fault Tolerant Reward-Based Scheduling is motivated by the observation that the optional parts in the Reward-Based models create opportunities for recovery operations in case of the transient faults which affect the mandatory parts. However, scheduling the optional parts to merely maximize the total reward may leave no recovery time for the mandatory part(s) affected by faults. On the other hand, applying a hard real-time fault tolerance technique may yield unacceptably low reward. We developed the FT-Optimality (Fault Tolerant Optimality) framework to provision for faults while accruing as much reward as possible.

Nevertheless, the various characteristics of the task/fault model deeply affect the existence of efficient FT-Optimal scheduling algorithms. The dimensions that we considered in our studies are:

In [11], we focused on frame-based systems where tasks share a common, end-to-end deadline and the reward functions are general concave. We showed the optimality of: a least commitment strategy for tasks with linear precedence constraints and, the delaying of all optional parts at the end, for independent tasks. In addition, we provided an efficient algorithm for the computation of service times which provide the FT-Optimal schedule.

In [9], we investigated the multiple deadlines case for independent tasks. For one of the recovery techniques proposed ("Immediate Recovery"), we developed an optimal algorithm for linear reward functions; while the other one ("Delayed Recovery") is shown to be inherently intractable even under modest assumptions.

The contribution of [5] is twofold: First, we considered and solved the general problem of checking the tolerance to faults of a given RB schedule, even for multiple faults and for recovery blocks of (potentially) different lengths per task. Second, we presented an efficient FT-Optimal solution for the chain of RB tasks with different deadlines.

Dynamic Voltage Scaling for Low-Power Real-Time Systems

With the advent of mobile and wireless computing, power-efficiency has become one of the paramount issues in Computer Science. Dynamic Voltage Scaling (DVS) techniques rely on dynamically reducing the supply voltage and the frequency on-the-fly; resulting in increase in latency and considerable power savings. Yet, for Real-Time Systems, care must be taken not to violate any timing constraints.

It is remarkable that the DVS problem, can be proven to be equivalent to the RBS problem for the static version, where each task is assumed to present its worst-case workload. We provided the optimal speed assignment algorithm for tasks with different power consumption characteristics in [8,3].

Nevertheless, in practice, tasks present frequently a workload which is far less than the worst-case. Consequently, keeping track and reclaiming the unused computation time by further slowing down the speed may provide considerable power savings. To this purpose, we developed the Dynamic Reclaiming Algorithm . To go one step further, one might adopt an aggressive approach. In fact, it is possible to have a spectrum of these techniques depending on the aggressiveness level. An exposition of all these algorithms, along with their feasibility proofs, can be found in [7] (for frame-based systems) and in [1] (for general periodic model).

PUBLICATIONS

  1. H. Aydin, R. Melhem, D. Mosse and P.M. Alvarez. Dynamic and Aggressive Power-Aware Scheduling Techniques for Real-Time Systems. To appear in the Proceedings of the 22nd IEEE Real-time Systems Symposium. London, England, December 2001.
  2. H. Aydin. Enhancing Performance and Fault Tolerance in Reward-Based Scheduling. Ph.D. Dissertation . University of Pittsburgh, August 2001.
  3. H. Aydin, R. Melhem, D. Mosse and P.M. Alvarez. Determining Optimal Processor Speeds for Periodic Real-Time Tasks with Different Power Characteristics. Proceedings of the 13th EuroMicro Conference on Real-Time Systems (ECRTS'01) . Delft, Netherlands, June 2001.
  4. H. Aydin, R. Melhem, D. Mosse and P. M. Alvarez. Optimal Reward-Based Scheduling for Periodic Real-Time Tasks. IEEE Transactions on Computers. Vol. 50, no. 2, pp. 111 - 130, February 2001.
  5. H. Aydin, R. Melhem and D. Mosse. Optimal Scheduling of Imprecise Computation Tasks in the Presence of Multiple Faults. Proceedings of the 8th International Conference on Real-Time Computing Systems and Applications (RTCSA'00), S. Korea, December 2000.
  6. P. M. Alvarez, H. Aydin, R. Melhem and D. Mosse. Scheduling Optional Computations in Fault-Tolerant Real-Time Systems. Proceedings of the 8th International Conference on Real-Time Computing Systems and Applications (RTCSA'00), S. Korea, December 2000.
  7. D. Mosse, H. Aydin, B. Childers and R. Melhem. Compiler-Assisted Dynamic Power-Aware Scheduling for Real-Time Applications. Workshop on Compilers and Operating Systems for Low-Power (COLP'00), Philadelphia, PA, October 2000.
  8. H. Aydin, R. Melhem and D. Mosse. Task-level Energy Minimization for Reconfigurable Embedded Systems. Proceedings of the 4th Annual Workshop on High Performance Embedded Computing (HPEC'00), Lexington, MA, September 2000.
  9. H. Aydin, R. Melhem and D. Mosse. Tolerating Faults while Maximizing Reward. Proceedings of the 12th Euromicro Conference on Real-Time Systems (EuroMicro'00), Stockholm, June 2000.
  10. H. Aydin, R. Melhem, D. Mosse and P.M. Alvarez. Optimal Reward-Based Scheduling for Periodic Real-Time Tasks. Proceedings of the 20th IEEE Real-Time Systems Symposium (RTSS'99), Arizona, December 1999.
  11. H. Aydin, R. Melhem and D. Mosse. Incorporating Error Recovery into the Imprecise Computation Model. Proceedings of the 7th International Conference on Real-Time Computing Systems and Applications (RTCSA'99), Hong Kong, December 1999.
  12. H. Aydin, R. Melhem and D. Mosse. A Polynomial-Time Algorithm to Solve Reward-Based Scheduling Problem, Technical Report 99-10. Department of Computer Science, University of Pittsburgh, April 1999.
  13. H. Aydin, R. Melhem and D. Mosse. Incorporating Error Recovery into the Imprecise Computation Model. Technical Report 98-09. Department of Computer Science, University of Pittsburgh, May 1998.
  14. H. Aydin. A hierarchical non-linear planner for simple domains. M.Sc. thesis. Control and Computer Engineering Department, Istanbul Technical University, February 1994.