[Colloq] Hiring Talk, Friday, Feb. 10, Sasha Fedorova- Harvard Univ.

[Rachel Kalweit]

College of Computer and Information Science Colloquium
Presents:
Alexandra (Sasha) Fedorova
Harvard University

Who will speak on:
Operating System Scheduling for Chip Multiprocessors

Friday, February 10, 2006
12:00pm
366 West Village H
Northeastern University

Abstract:
Chip multiprocessors run multiple application threads in parallel, and, 
in contrast with conventional processors, threads share many of the 
processor resources. The operating system, traditionally viewed as the 
arbitrator of machine resources, must schedule threads in a way that 
results in good utilization of the shared processor resources, for the 
sake of better performance and higher predictability. For my thesis I 
have developed three scheduling algorithms for chip multiprocessors: the 
cache-fair algorithm, the non-work-conserving algorithm, and the 
target-miss-rate algorithm.

In my talk I will describe the cache-fair algorithm. This algorithm 
addresses schedule-dependent performance variability, a phenomenon where 
an application's CPU performance depends on the threads with which it is 
scheduled. Schedule-dependent variability makes it difficult to forecast 
application. The shared second-level (L2) CPU cache is the source of 
schedule-dependent performance variability on chip multiprocessors with 
single-threaded processing cores. My algorithm uses an analytical model 
to estimate the L2 cache miss rate a thread would have if the cache were 
shared equally among all the threads, the fair miss rate. It then 
adjusts the thread's share of CPU cycles in proportion to its deviation 
from its fair miss rate. This reduces the effect of the 
schedule-dependent miss rate variability on the thread's runtime. In 
cases of significant variability the cache-fair algorithm reduces the 
schedule-dependent performance variability by at least a factor of two 
and sometimes by as much as a factor of seven. This algorithm has been 
implemented in a Solaris operating system, works without any advance 
knowledge about the workload and relies only on hardware performance 
counters typically available on modern processors.

Host: Matthias Felleisen