scott@cs.rochester.edu (08/14/89)
Contacts:
Michael L. Scott Thomas J. LeBlanc
scott@cs.rochester.edu leblanc@cs.rochester.edu
(716) 275-7745 (716) 275-5426
Department of Computer Science
University of Rochester
Rochester, NY 14627
The Psyche project at the University of Rochester is an attempt to
support truly general-purpose parallel computing on large shared-memory
multiprocessors. We define "general-purpose" to mean that the
applications programmer must be able to do anything for which the
underlying hardware is physically well-suited. Our current work
focuses on the development of an operating system that will support
the full range of parallel programming models in a single programming
environment.
Through five years of hands-on experience with a 128-node
multiprocessor, we have become increasingly convinced that no single
model of process state or style of communication can be appropriate for
all applications. Traditional approaches ranging all the way from the
most tightly-coupled shared-memory model to the most loosely-coupled
form of message passing have applications for which they are
conceptually attractive. Our goal is to allow each application, and in
fact each *part* of an application, to be written under the model most
appropriate for its own particular needs.
The Psyche user interface is based on passive data abstractions called
"realms." Each realm includes data and code. The code constitutes a
protocol for manipulating the data and for scheduling processes running
in the realm. The intent is that the data should not be accessed
except by obeying the protocol. To facilitate data sharing, Psyche
uses uniform addressing for realms -- each realm has the same virtual
address from the point of view of every process that uses it. Which
realms are actually accessible to a process depends on the protection
domain in which that process is executing. Each protection domain is
associated with a particular "root" realm, and includes any other
realms for which access rights have been demonstrated to the kernel.
Depending on the degree of protection desired, an invocation of a realm
operation can be as fast as an ordinary procedure call or as safe as a
remote procedure call between protection domains. Unless the *caller*
insists on protection, the protected and optimized varieties of
invocation both look exactly like local subroutine calls. The kernel
implements protected invocations by catching and interpreting page
faults. Protected invocations cause the calling process to move
temporarily to the protection domain of the target realm.
Multiple models of process management are supported by moving most of
the responsibility for scheduling out of the kernel and into user
code. The user can ask that a certain number of virtual processors be
assigned to a protection domain. The kernel implements these virtual
processors (which we call "activations") via multiprogramming, but
otherwise stays out of process management. It provides each activation
with signals (software interrupts) when scheduling decisions might be
needed, including when
(1) a new process has moved into the activation's protection domain
by performing a protected invocation,
(2) the activation's current process has left the protection domain
by performing a protected invocation,
(3) an invocation has completed and the calling process has returned,
(4) a user-specified timeout has expired, or
(5) a program fault has occurred (arithmetic, protection, etc.).
We are interested in very-large scale parallelism, which implies that
memory access costs will be non-uniform. Much of our work to date has
focussed on the design of a virtual memory system that can balance the
needs of demand paging, automatic management of locality (the so-called
"NUMA problem") and Psyche-style realms and protection domains. As of
summer 1989 have been writing code for about a year. Our prototype
implementation runs on a BBN Butterfly Plus multiprocessor (the
hardware base for the GP1000 product line). Personnel include two
faculty members, two professional staff members, and eight students.
We are collaborating with members of the department's computer vision
and planning groups on a major project in real-time active vision and
robotics, sponsored in part by a recently-announced NSF institutional
infrastructure grant. Psyche forms the systems foundation for
high-level vision and planning functions in the robot lab. We expect
the resulting applications experience to provide valuable feedback on
our design. Our first robotics application (a balloon-bouncing
program) is now in the final stages of implementation.
References:
%A T. J. LeBlanc
%A M. L. Scott
%A C. M. Brown
%T Large-Scale Parallel Programming: Experience with the BBN Butterfly
Parallel Processor
%J Proceedings of the ACM SIGPLAN PPEALS 1988 \(em Parallel Programming:
Experience with Applications, Languages, and Systems
%C New Haven, CT
%D 19-21 July 1988
%P 161-172
%X Retrospective on early work with the Butterfly;
good background for understanding the motivation for Psyche
%A M. L. Scott
%A T. J. LeBlanc
%A B. D. Marsh
%T Design Rationale for Psyche, a General-Purpose Multiprocessor Operating
System
%J Proceedings of the 1988 International Conference on Parallel Processing
%C St. Charles, IL
%D 15-19 August 1988
%P 255-262, vol. II \(mi Software
%X Why we need a new kind of operating system to use shared-memory
multiprocessors well
%A M. L. Scott
%A T. J. LeBlanc
%A B. D. Marsh
%T A Multi-User, Multi-Language Open Operating System
%J Second Workshop on Workstation Operating Systems
%C Pacific Grove, CA
%D to appear, 27-29 September 1989
%X How Psyche combines the flexibility and efficiency of an open
operating system with the protection of a traditional O.S.
%A M. L. Scott
%A T. J. LeBlanc
%A B. D. Marsh
%T Implementation Issues for the Psyche Multiprocessor Operating System
%J Workshop on Experiences with Building Distributed and
Multiprocessor Systems
%C Ft. Lauderdale, FL
%D to appear, 5-6 October 1989
%X Issues that arise in structuring a large shared-memory kernel
%A T. J. LeBlanc
%A B. D. Marsh
%A M. L. Scott
%T Memory Management for Large-Scale NUMA Multiprocessors
%R Technical Report
%I Computer Science Department, University of Rochester
%D 1989
%X The design of a VM system to support demand paging, locality management,
and Psyche abstractions
%A M. L. Scott
%A T. J. LeBlanc
%A B. D. Marsh
%T Evolution of an Operating System for Large-Scale Shared-Memory
Multiprocessors
%R Technical Report
%I Computer Science Department, University of Rochester
%D 1989
%X The development of Psyche from first principles to concrete
mechanisms