Candidate: Jan Edler
Advisor: Allan Gottlieb

Practical Structures for Parallel Operating Systems

10:00 a.m., Tuesday, May 2, 1995
12th floor conference room, 719 Broadway


Large shared memory MIMD computers, with hundreds or thousands of processors, pose special problems for general purpose operating system design. In particular:

Serial bottlenecks that are insignificant for smaller machines can seriously limit scalability.

The needs of parallel programming environments vary greatly, requiring a flexible model for runtime support.

Frequent synchronization within parallel applications can lead to high overhead and bad scheduling decisions.

Because of these difficulties, the algorithms, data structures, and abstractions of conventional operating systems are not well suited to highly parallel machines.

We describe the Symunix operating system for the NYU Ultracomputer, a machine with hardware support for Fetch&Phi operations and combining of memory references. Avoidance of serial bottlenecks, through careful design of interfaces and use of highly parallel algorithms and data structures, is the primary goal of the system. Support for flexible parallel programming models relies on user-mode code to implement common abstractions such as threads and shared address spaces. Close interaction between the kernel and user-mode runtime layer reduces the cost of synchronization and avoids many scheduling anomalies.

Symunix first became operational in 1985 and has been extensively used for research and instruction on two generations of Ultracomputer prototypes at NYU. We present data gathered from actual multiprocessor execution to support our claim of practicality for future large systems.