[Colloq] REMINDER: Hiring Talk, TODAY, 12pm, Alexandra 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



_______________________________________________
Colloq mailing list
Colloq at lists.ccs.neu.edu
https://lists.ccs.neu.edu/bin/listinfo/colloq