My research in computer performance focuses on the use of queueing theory models to understand and predict system behavior. I have applied those tools in several areas: memory modeling, fair share and goal mode scheduling, understanding measured CPU queue lengths in Microsoft NT and Windows 2000 operating systems, Intel's hyper-threading architecture, and various virtualization disciplines. I like to build analytic models and validate them against measured data from real applications and from benchmarks I write.

Some of my work:

• A queueing theory primer for lay audiences. (Very old - 1987 - but still fun.)

• How Many Guests Can You Serve? - On the Number of Partitions (with Yiping Ding), To appear in the Proceedings of the 35th Computer Measurement Group Conference (December 2006).

  Here is Yiping Ding's conference presentation.

• Virtual performance won't do: Capacity planning for virtual systems (with Yiping Ding), Proceedings of the 34th Computer Measurement Group Conference (December 2005)

• Performance Implications of Hyper-Threading (with Yiping Ding and Arjun Kumar), Proceedings of the 32nd Computer Measurement Group Conference (December 2003)

  UMass Boston colloquium (powerpoint)

• Interpreting Windows NT Processor Queue Length Measurements (with Yiping Ding, William Flynn, Debbie Sheetz and Yefim Somin), Proceedings of the 31st Computer Measurement Group Conference (December 2002), vol. 2, pp 759-770.

• Fair Share Modeling for Large Systems: Aggregation, Hierarchical Decomposition and Randomization (with Yiping Ding and Anatoliy Rikun), Proceedings of the 30th Computer Measurement Group Conference (December 2001), pp. 808-818

• On the Performance Impact of Fair Share Scheduling (with Yiping Ding), Proceedings of the Computer Measurement Group Conference (December, 2000), pp.71-81.

  Presentation at the conference (Powerpoint).

  Fair share scheduling applet.

• Toronto AMS meeting presentation
  Priority Scheduling: an Application for the Permutahedron (ppt)

• Kingston University
  Fair Share Scheduling
  powerpoint , html

• UMass PhD club presentation
  HTML
  Powerpoint

Some references:

Carl A. Waldspurger and William E. Weihl. Lottery Scheduling: Flexible Proportional-Share Resource Management, Proceedings of the First Symposium on Operating Systems Design and Implementation (OSDI '94), pages 1-11, Monterey, California, November 1994
http://www/waldspurger.org/carl/papers/lottery-osdi94.ps.gz

The thesis on which this is based:
Carl A. Waldspurger
Lottery and Stride Scheduling: Flexible Proportional-Share Resource Management
http://www.waldspurger.org/carl/papers/phd-mit-tr667.ps.gz
http://citeseer.nj.nec.com/cachedpage/139485/1

Berkeley talk outline:
Lottery Scheduling: Flexible Proportional-Share Resource Management
Carl A. Waldspurger and William E. Weihl, MIT LCS
http://www.cs.berkeley.edu/~gribble/osprelims/F95/summaries/lottery.html http://www.cs.berkeley.edu/~gribble/osprelims/summaries/lottery_sched.html

Waldspurger's publications: http://www.waldspurger.org/carl/papers.html

Modelling the Behavior of Solaris Resource Manager
(Batch workloads only - essentially Neil Gunther's earlier CMG paper, using his PDQ packaged M/M/1 formulas. See http://www.perfdynamics.com/ )
http://www.sun.com/blueprints/0899/solaris4.pdf

Batch jobs are usually resource intensive. LSF Standard Edition allows you to manage the conflicting demands of users to ensure fair sharing of limited computing resources. You can configure shares for users and user groups, so users taking up fewer resources can get higher priority. Some jobs may even be suspended to make room for more urgent jobs.

Fair Share Scheduler. Teradata implements a priority-based fair share scheduler. Using a priority specified for users' sessions, CPU resources are allocated to grant each priority of work a fair share of the system. All work in all internal queues is managed by priority to expedite high-priority work. This facility is being enhanced in V2R3 to allow the definition of user classes and allocation of resources to these classes. It will be possible, for example, to specify that one group of users is confined to only 20 percent of the CPU resources of the system.

http://www.teradatareview.com/9801wltr.htm

Surplus Fair Scheduling: A Proportional-Share CPU Scheduling Algorithm for Symmetric Multiprocessors

In this paper, we present surplus fair scheduling (SFS), a proportional-share CPU scheduler designed for symmetric multiprocessors. We first show that the infeasibility of certain weight assignments in multiprocessor environments results in unfairness or starvation in many existing proportional-share schedulers. We present a novel weight readjustment algorithm to translate infeasible weight assignments to a set of feasible weights. We show that weight readjustment enables existing proportional-share schedulers to significantly reduce, but not eliminate, the unfairness in their allocations. We then present surplus fair scheduling, a proportional-share scheduler that is designed explicitly for multiprocessor environments. We implement our scheduler in the Linux kernel and demonstrate its efficacy through an experimental evaluation. Our results show that SFS can achieve proportionate allocation, application isolation and good interactive performance, albeit at a slight increase in scheduling overhead. We conclude from our results that a proportional-share scheduler such as SFS is not only practical but also desirable for server operating systems.

The Design, Implementation and Evaluation of SMART: A Scheduler for Multimedia Applications, J. Nieh, M. S. Lam. Proceedings of the Sixteenth ACM Symposium on Operating Systems Principles, Saint-Malo, France, October 1997.
http://www.cs.columbia.edu/~nieh/publications/sosp97_fordist.pdf
http://www.cs.columbia.edu/~nieh/publications/sosp97_cdrom/
A Fair Workload Allocation Policy for Heterogeneous Systems Leonidas Georgiadis, Christos Nikolaou, Alexander Thomasian