Research

In my Ph.D. dissertation, I examine certain real-time scheduling problems that have a variety of constraints. These systems, including radar systems, do not lend themselves to straight-forward analysis to guarantee schedulability. Efficient tests for schedulability are important for several reasons, but one of great importance in large and dynamic real-time systems is the ability to perform run-time system optimization. To enable rapid system re-optimization when there are changes in the operating environment, phase transitions play a vital role.

Phase transitions have been identified in many combinatorial optimization problems such as 3-SAT, the Traveling Salesman Problem and Number Partitioning. A phase transition is a property of some NP-hard problems to shift from a situation where almost all problems can be solved easily to a situation where almost no problem has a solution. The two situations are parameterized by a measure of hardness.

The existence of phase transitions in very general real-time scheduling problems suggests a simple interface between mathematical programming (optimization) and constraint programming. I explore this thesis and demonstrate the use of phase transitions in solving hard problems in a real-time environment.

References RTAS 2003, RTSS 2003, RTSS 2004, RTSJ 2006

A specific case of the multiprocessor real-time scheduling problem involves the pre-allocation of tasks to processors. This case, known as the partitioned scheduling model, is significant because of its ease of implementation. Techniques to allocate tasks to processors have been extensively studied but the need for fault-tolerance (via replication) has not been given much consideration. We propose a fully-polynomial time approximation scheme for allocation that takes into account the replication requirements of tasks.

Another thrust of research in partitioned multiprocessor real-time scheduling is concerned with the determination of utilization bounds for guaranteeing the schedulability of a given task set. It has been shown that 50% is a tight utilization bound for this partitioned multiprocessor scheduling. However, the existence of a phase transition for this problem indicates that setting a higher utilization bound is "good enough" for most problems in the sense that very few task sets satisfy the bound obtained from the phase transition but are unschedulable.

Real-time system design is exceedingly complicated because of the need to meet function requirements (performing the tasks expected of the system) and non-functional requirements (timing requirements). System architects spend many hours producing high-level designs that conform to the expected timing behavior. To ameliorate some of the difficulties faced by system architects, my colleagues and I have developed techniques for automating aspects of system design.

We have developed a linear programming formulation to solve routing and scheduling problems for communication in bus-based networks. In this work, we suggest restricted multi-path routing as an approach to dealing with the intractability of the route selection problem. [RTSS 2004]

Many conventional real-time systems need to process huge volumes of sensor data. To handle these heavy network loads, they are built using high-performance routers and switches, which are hard to characterize in terms of deterministic packet switching delays. We investigated scheduling algorithms used by typical switches and routers. After deriving bounds for packet latencies, we have developed an algorithm for the design of networks using high-speed switches. The design consideration was to reduce network cost while ensuring that all messages meet their timing requirements.

Spare CASH

Many real-time systems, especially multimedia systems, can afford to skip a few instances of periodic tasks. In such systems, skips can help improve the overall quality of service, more so when aperiodic tasks need to be scheduled. Aperiodic tasks may be infrequent control activities that require short response times. The Spare CASH mechanism reduces the response times of aperiodic tasks while providing periodic tasks with the bandwidths reserved for them. The major contribution is an efficient combination of reservation and resource reclamation.

References ECRTS 2005, Technical Report