Sapha: Static Approximate Phase Analysis.

These pages describe work carried out on design implementation, and applications of a technique that we call static approximate phase analysis. The PI is Hridesh Rajan and much of the work is carried out by Tyler Sondag.

News

March 2011: Invited talk on phase-based tuning at SMART '11.

December 2010: Paper on Frances-A tool accepted for CCSC 2011.

November 2010: Paper on phase-guided tuning accepted for CGO 2011.

August 2010: Paper on cache analysis accepted for RTSS 2010.

January 2010: Tutorial on Frances tool accepted for CCSC 2010.

October 2009: Paper on Frances tool accepted for SIGCSE 2010.

Fairness

Fairness is measured by looking at max-flow [2], max-stretch [2], and average process time. A brief description of each follows:

  • max-flow: longest measured execution time
  • max-stretch: largest slowdown of an individual job
  • average time: average process run-time
Compared to the stock Linux scheduler, variations of our technique improve upon all of these metrics.

Figure 1: Fairness for variations of our technique. Shaded results show improvement.


  1. These results are shown in our latest technical report.
  2. Michael A. Bender, Soumen Chakrabarti, and S. Muthukrishnan. Flow and stretch metrics for scheduling continuous job streams. In Annual symposium on Discrete algorithms, 1998.