Events - Colloquia & Seminars

CCIS Colloquium Spring 2006

Operating System Scheduling for Chip Multiprocessors

Speaker: Alexandra (Sasha) Fedorova (Harvard University)

Date: Friday, February 10, 2006

Talk: 12:00 pm, 366 WVH

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.