Publications

I am fortunate to have collaborated with the following people: James H. Anderson, Phil Holman, Sanjoy Baruah, Jasleen Sahni, John Carpenter, Shelby Funk, Aaron Block, Srinivas Kashyap, Supratim Deb, K.V.M. Naidu, Rajeev Rastogi.


Papers in Refereed Conferences, Journals and Workshops

(Click on [+] to see the abstracts.)

  • S. Kashyap, S. Deb, K.V.M. Naidu, R. Rastogi and A. Srinivasan. Efficient Gossip-Based Aggregate Computation, to appear in ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS) 2006.

      Abstract: There has been a growing interest in gossip-based protocols that employ randomized communication to ensure robust information dissemination. In this paper we present a novel gossip-based scheme using which all nodes in an n-node overlay network can compute the common aggregates of MIN, MAX, SUM, AVERAGE and RANK of their values using O(n loglog n) messages in O(log n loglog n) rounds of communication. To the best of ours knowledge, ours is the first result that shows how to compute these aggregates with high probability using only O(n loglog n) messages. In contrast, the best known gossip-based algorithm for computing these aggregates requires O(n log n) messages and O(log n) rounds. Thus, our algorithm allows system designers to trade off a small increase in round complexity with a significant reduction in message complexity. This can lead to dramatically lower network congestion and longer node lifetimes in wireless and sensor networks, where channel bandwidth and battery life are severely constrained.

  • J. Anderson, A. Block and A. Srinivasan. Quick Release Fair Scheduling, Proceedings of the 24th IEEE Real-time Systems Symposium, pages 130-141, 2003.

      Abstract: In prior work on multiprocessor fairness, efficient techniques with provable properties for reallocating spare processing capacity have been elusive. In this paper, we address this shortcoming by proposing a new notion of multiprocessor fairness, called quick-release fair (QRfair) scheduling, which is a derivative of Pfair scheduling that allows efficient allocation of spare capacity. Under QRfair scheduling, each task is specified by giving both a minimum and a maximum weight (i.e., processor share). The goal is to schedule each task (as the available spare capacity changes) at a rate that is (i) at least that implied by its minimum weight and (ii) at most that implied by its maximum weight. Our contributions are fourfold. First, we present a quick-release variant of the PD2 Pfair scheduling algorithm called PDQ. Second, we formally prove that the allocations of PDQ always satisfy (i) and (ii). Third, we consider the problem of defining maximum weights in a way that encourages a fair distribution of spare capacity. Fourth, we present results from extensive simulation experiments that show the efficacy of PDQ in allocating spare capacity.

  • A. Srinivasan and J. Anderson Efficient Scheduling of Soft Real-time Applications on Multiprocessors, Real-time Applications on Multiprocessors, Proceedings of the 15th Euromicro Conference on Real-Time Systems, pages 51-59, July 2003. (A journal version of this paper has appeared in Journal of Embedded Computing, Volume 1, Number 2, pages 285-302, 2005.)

      Abstract: In soft real-time applications, tasks are allowed to miss their deadlines. Thus, less-costly scheduling algorithms can be used at the price of occasional violations of timing constraints. This may be acceptable if reasonable tardiness bounds (i.e., bounds on the extent to which deadlines may be missed) can be guaranteed.

      In this paper, we consider soft real-time applications implemented on multiprocessors. Pfair scheduling algorithms are the only known means of optimally scheduling hard real-time applications on multiprocessors. For this reason, we consider the use of such algorithms here. In the design of Pfair scheduling algorithms, devising schemes to correctly break ties when several tasks have the same deadline is a critical issue. Such tie-breaking schemes entail overhead that may be unacceptable or unnecessary in soft real-time applications. In this paper, we consider the earliest pseudo-deadline first (EPDF) Pfair algorithm, which avoids this overhead by using no tie-breaking information. Our main contributions are twofold. First, we establish a condition for ensuring a tardiness of at most one quantum under EPDF. This condition is very liberal and should often hold in practice. Second, we present simulation results involving randomly-generated task sets, including those that do not satisfy our condition. In these experiments, deadline misses rarely occurred, and no misses by more than one quantum ever occurred.

  • A. Srinivasan and J. Anderson. Fair Scheduling of Dynamic Task Systems on Multiprocessors, Proceedings of the 11th International Workshop on Parallel and Distributed Real-Time Systems, held in conjunction with the International Parallel and Distributed Processing Symposium, April 2003. (A journal version of this paper has appeared in Journal of Systems and Software, Volume 77, Number 1, pages 67-80, April 2005.)

      Abstract: In dynamic real-time task systems, tasks that are subject to deadlines are allowed to join and leave the system. In previous work, Stoica et al. and Baruah et al. presented conditions under which such joins and leaves may occur in fair-scheduled uniprocessor systems without causing missed deadlines. In this paper, we extend their work by considering fair-scheduled multiprocessors. We show that their conditions are sufficient on M processors, under all known (dynamic-priority) Pfair scheduling algorithms, if the utilization of every subset of M-1 tasks is at most one. Further, for the general case in which task utilizations are not restricted in this way, we derive sufficient join/leave conditions for the PD2 Pfair algorithm. We also show that, in general, these conditions cannot be improved upon without causing missed deadlines.

  • A. Srinivasan, P. Holman, J. Anderson, and S. Baruah. The Case for Fair Multiprocessor Scheduling, Proceedings of the 11th International Workshop on Parallel and Distributed Real-Time Systems, held in conjunction with the International Parallel and Distributed Processing Symposium, April 2003.

      Abstract: Partitioning and global scheduling are two approaches for scheduling real-time tasks on multiprocessors. Though partitioning is sub-optimal, it has traditionally been preferred; this is mainly due to the fact that well-understood uniprocessor scheduling algorithms can be used on each processor. In recent years, global-scheduling algorithms based on the concept of proportionate fairness (Pfairness) have received considerable attention. Pfair algorithms are of interest because they are currently the only known method for optimally scheduling periodic, sporadic, and rate-based task systems on multiprocessors. In addition, there has been growing practical interest in scheduling with fairness guarantees. However, the frequency of context switching and migration in Pfair-scheduled systems has led to some questions concerning the practicality of Pfair scheduling.

      In this paper, we investigate this issue by comparing the PD2 Pfair algorithm to the EDF-FF partitioning scheme, which uses first fit (FF) as a partitioning heuristic and the earliest-deadline-first (EDF) algorithm for per-processor scheduling. We present experimental results that show that PD2 is competitive with, and in some cases outperforms, EDF-FF. These results suggest that Pfair scheduling is a viable alternative to partitioning. Furthermore, as discussed herein, Pfair scheduling provides many additional benefits, such as simple and efficient synchronization, temporal isolation, fault tolerance, and support for dynamic tasks.

  • A. Srinivasan, P. Holman, J. Anderson, S. Baruah, and J. Kaur. Multiprocessor Scheduling in Processor-based Router Platforms: Issues and Ideas, Proceedings of the 2nd Workshop on Network Processors, pages 48-62, February 2003. Held in conjunction with the 9th International Symposium on High-Performance Computer Architecture.

      Abstract: Two important trends are expected to guide the design of next-generation networks. First, with the commercialization of the Internet, providers will use value-added services to differentiate their service offerings from other providers; such services require the use of sophisticated resource scheduling mechanisms in routers. Second, to enable extensibility and the deployment of new services in a rapid and cost-effective manner, routers will be instantiated using programmable network processors. In this research, our goal is to develop sophisticated multiprocessor scheduling mechanisms that would enable networks that deploy such router platforms to provide service guarantees to applications. Existing multiprocessor scheduling techniques are either not applicable to router platforms due to their complexity or simplistic assumptions, or are not based on rigorous formalism, which is necessary to enable strong assertions about service guarantees. In this work, we propose to address these limitations. This paper presents our current ideas and planned future directions.

  • A. Srinivasan and S. Baruah. Deadline-based Scheduling of Periodic Task Systems on Multiprocessors, Information Processing Letters, Volume 84, Number 2, pages 93-98, Elsevier Science Press, November 2002.

      Abstract: We consider the problem of scheduling periodic task systems on multiprocessors and present a deadline-based scheduling algorithm for solving this problem. We show that our algorithm successfully schedules on m processors any periodic task system with utilization at most m^2/(2m-1).

  • A. Srinivasan, P. Holman, and J. Anderson. Integrating Aperiodic and Recurrent Tasks on Fair-scheduled Multiprocessors, Proceedings of the 14th Euromicro Conference on Real-Time Systems, pages 19-28, June 2002.

      Abstract: We propose two server implementations for multiplexing aperiodic and recurrent (i.e., periodic, sporadic, or rate-based) real-time tasks in fair-scheduled multiprocessor systems. This is the first paper to consider the problem of integrating support for aperiodic tasks within fair multiprocessor scheduling algorithms. We also provide admission-control tests for the scheduling of hard aperiodic tasks (which have deadlines). Further, we point out some of the additional complexities involved in server-based implementations on multiprocessors and present some ways to handle them. Most of these complexities arise because of the parallelism that exists in such systems. Finally, we provide experimental results that demonstrate the effectiveness of our implementations.

  • A. Srinivasan and J. Anderson. Optimal Rate-based Scheduling on Multiprocessors, Proceedings of the 34th ACM Symposium on Theory of Computing, pages 189-198, May 2002.(A journal version of this paper is going to appear in Journal of Computer and System Sciences.)

      Abstract: The PD2 Pfair/ERfair scheduling algorithm is the most efficient known algorithm for optimally scheduling periodic tasks on multiprocessors. In this paper, we prove that PD2 is also optimal for scheduling "rate-based" tasks whose processing steps may be highly jittered. The rate-based task model we consider generalizes the widely-studied sporadic task model.

  • J. Anderson and A. Srinivasan. Mixed Pfair/ERfair Scheduling of Asynchronous Periodic Tasks, Proceedings of the 13th Euromicro Conference on Real-Time Systems, pages 76-85, June 2001. (A journal version of this paper has appeared in Journal of Computer and System Sciences, Volume 68, Number 1, pages 157-204, Elsevier Science Press, February 2004.)

      Abstract: There has been much recent interest in multiprocessor Pfair and ERfair scheduling algorithms. Under Pfair scheduling, each task is broken into quantum-length subtasks, each of which must execute within a "window" of time slots. These windows divide each period of a task into potentially overlapping subintervals of approximately equal length. "Early-release" fair (ERfair) scheduling was recently proposed as a work-conserving variant of Pfair scheduling. Under ERfair scheduling, subtasks within the same job are allowed to execute before their Pfair windows.

      In this paper, we prove that a simplified variant of the PD Pfair algorithm, called PD2, is optimal for scheduling any mix of early-release and non-early-release asynchronous tasks on a multiprocessor. This result breaks new ground in two ways. First, we are the first to consider the problem of scheduling both early-release and non-early-release tasks under a common framework. Second, all prior work on optimal multiprocessor Pfair or ERfair scheduling algorithms has been limited to synchronous periodic task systems.

  • J. Anderson and A. Srinivasan. Pfair Scheduling: Beyond Periodic Task Systems, Proceedings of the 7th International Conference on Real-Time Computing Systems and Applications, pages 297-306, December 2000. (Longer version with full proofs.)

      Abstract: In this paper, we consider variants of Pfair and ERfair scheduling in which subtasks may be released late, i.e., there may be separation between consecutive windows of the same task. We call such tasks intra-sporadic tasks. There are two main contributions of this paper. First, we show the existence of a Pfair (and hence ERfair) schedule for any intra-sporadic task system whose utilization is at most the number of available processors. Second, we give a polynomial-time algorithm that is optimal for scheduling intra-sporadic tasks in a Pfair or ERfair manner on systems of one or two processors.

  • J. Anderson and A. Srinivasan. Early-Release Fair Scheduling, Proceedings of the 12th Euromicro Conference on Real-Time Systems, pages 35-43, June 2000.

      Abstract: We present a variant of Pfair scheduling, which we call early-release fair (ERfair) scheduling. Like conventional Pfair scheduling, ERfair scheduling algorithms can be applied to optimally schedule periodic tasks on a multiprocessor system in polynomial time. However, ERfair scheduling differs from Pfair scheduling in that it is work conserving. As a result, average job response times may be much lower under ERfair scheduling than under Pfair scheduling, particularly in lightly-loaded systems. In addition, runtime costs are lower under ERfair scheduling. This is because, in Pfair-scheduled systems, significant bookkeeping information is required to determine when a job of a task is and is not eligible for execution. In an ERfair system, this bookkeeping information is not required because, once released, a job continues to be eligible until it completes. To the best of our knowledge, ERfair scheduling is the first truly work-conserving scheduling discipline for periodic task systems that is optimal for multiprocessors.

Book Chapters

J. Anderson, P. Holman, and A. Srinivasan. Fair Multiprocessor Scheduling, appeared in Handbook of Scheduling: Algorithms, Models, and Performance Analysis, Joseph Y. Leung (editor), Chapman Hall/CRC, Boca Raton, Florida, pages 31-1 - 31-21, 2004.

J. Carpenter, S. Funk, P. Holman, A. Srinivasan, J. Anderson, and S. Baruah. A Categorization of Real-time Multiprocessor Scheduling Problems and Algorithms, appeared in Handbook of Scheduling: Algorithms, Models, and Performance Analysis, Joseph Y. Leung (editor), Chapman Hall/CRC, Boca Raton, Florida, pages 30-1 - 31-19, 2004.

A. Srinivasan, P. Holman, J. Anderson, S. Baruah, and J. Kaur. Multiprocessor Scheduling in Processor-based Router Platforms: Issues and Ideas, Network Processor Design: Issues and Practices Volume II , P. Crowley and H. Hadimioglu (editors), Morgan Kaufmann Publishers, San Francisco, California, pages 75-99, 2004.

Ph. D. Thesis

Efficient and Flexible Fair Scheduling of Real-time Tasks on Multiprocessors

Abstract

Proportionate fair (Pfair) scheduling is the only known way to optimally schedule periodic real-time task systems on multiprocessors in an on-line manner. Under Pfair scheduling, the execution of each task is broken into a sequence of quantum-length subtasks that must execute within intervals of approximately-equal lengths. This scheduling policy results in allocations that mimic those of an ideal "fluid" scheduler, and in periodic task systems, ensures that all deadlines are met.

Though Pfair scheduling algorithms hold much promise, prior to our work, research on this topic was limited in that only static systems consisting of synchronous periodic tasks were considered. My dissertation thesis is that the Pfair scheduling framework for the on-line scheduling of real-time tasks on multiprocessors can be made more flexible by allowing the underlying task model to be more general than the periodic model and by allowing dynamic task behaviors. Further, this flexibility can be efficiently achieved.

Towards the goal of improving the efficiency of Pfair scheduling algorithms, we develop the PD2 Pfair algorithm, which is the most efficient optimal Pfair scheduling algorithm devised to date. Through a series of counterexamples, we show that it is unlikely that a more efficient optimal Pfair algorithm exists. We also introduce the concept of ERfair scheduling, which is a work-conserving extension of Pfair scheduling. In addition, we study the non-optimal earliest-pseudo-deadline-first (EPDF) Pfair algorithm, which is more efficient than PD2, and present several scenarios under which it is preferable to PD2.

We address the flexibility issue by developing the intra-sporadic (IS) task model and by considering the scheduling of dynamic task systems. The well-known sporadic model generalizes the periodic model by allowing jobs to be released late. The IS model generalizes this notion further by allowing late as well as early subtask releases. Such a generalization is useful for modeling applications in which the instantaneous rate of releases differs greatly from the average rate of releases (e.g., an application that receives packets over a network). We prove that PD2 is optimal for scheduling static IS task systems on multiprocessors. In dynamic task systems, tasks are allowed to join and leave, i.e., the set of tasks is allowed to change. This flexibility also allows us to model systems in which the weights of tasks may change. We present sufficient conditions under which joins and leaves can occur under PD2 without causing missed deadlines. Further, we show that these conditions are tight.

Finally, we also provide schemes for multiplexing the scheduling of aperiodic tasks and real-time IS tasks. These approaches aim at improving the response times of aperiodic tasks while ensuring that the real-time IS tasks meet their deadlines. We also provide bounds on aperiodic response times under these schemes; these bounds can be used to obtain admission-control tests for aperiodic tasks with deadlines.



Home