Tightly-coupled multiprocessor UNIX

[edler at cmcl2.UUCP]

The NYU Ultracomputer project has done two implementations of unix
for our current prototype hardware.  While the current hardware consists
of 8 10Mhz 68010 processors on a bus, the "real" architecture we are
working on would be thousands of (more powerful) processors with
thousands of memory modules and an interconnection network*.  Central to the
software architecture is the "Fetch&Add" operation and its proposed hardware
implementation, which has several properties important for avoiding
serial bottlenecks.

The first implementation, running since spring 1983, is a simple master/slave
implementation based on v7 unix.  Only one processor can do anything
really meaningful in the kernel; others can run processes in user mode only.
This requires only modest changes to the system, but when there are many
processors the master will surely become a bottleneck.

The second implementation, running since late spring 1984, is fully symmetric
and also based on v7 unix.  The only distinguished processor is the one
that maintains the system time of day.  As you might imagine, this version
required more substantial changes to the kernel.  Gone are the old
sleep/wakeup routines, and many of the data structures are changed
extensively.  Linear searches of important tables are eliminated.  Much
effort is put into eliminating critical sections: remember we are thinking
about thousands of processors; with such a machine even tiny critical
sections can become bottlenecks.

I don't want to sound like we have solved everything yet: we have lots of
ideas that are not yet fully implemented.  For example, although our current
facilities for parallel applications are effective, they are rather crude.
We expect continued rapid progress over the next few years.

I would be glad to discuss multiprocessor unix issues in greater detail.

	Jan Edler
	New York University
	Ultracomputer Group
	251 Mercer Street
	New York, NY 10012
	(212) 460-7314
	edler at nyu-cmcl2.arpa
	cmcl2!edler

* Here are a couple of references for more information:

Gottlieb, Grishman, Kruskal, McAuliffe, Rudolph, Snir: "The NYU Ultracomputer
-- Designing an MIMD Parallel Machine", IEEE Transactions on Computers,
vol C-32, #2 (Feb 1983).

Gottlieb, Lubachevsky, Rudolph: "Basic Techniques for the Efficient
Coordination of Very Large Numbers of Cooperating Sequential Processors",
ACM TOPLAS, vol 5, #2 (April 1983).