Subject: Re: mpp kernel interface

From: [email-masked] (Larry McVoy)
Date: Wed, 15 May 1996 15:43:19 -0700

: With 30 people now on this list there must be someone else who wants
: to say something ...

I'm going to try.  I'm probably going to do a half assed job, as I am 
feeling a bit sick today.  But I'll give it a go.

: It really depends on how we end up using this stuff. Does anyone out
: there have any experience with implementing things like remote fork,
: remote paging, remote files/sockets etc? What sorts of interfaces are
: useful for doing stuff like that?

I have a few ideas.  Lots of them are stolen from the UCAL Locus project, 
Jim Bob says check it out.

First, this is mostly a naming problem.  Wrap your brain around that.  We
need to have clear in our heads exactly how everything is named. Once
you can draw that picture, the implementation becomes straight forward.
After you read through this, you may or may not be in basic agreement.
If we ever converge, I will volunteer to write "man pages" for each of
the chunks of work so that we have a well documented TODO list.  It is
as close as I've ever gotten to a spec.

Things we need to name

	hosts
	cluster
	processes
	devices
	files
	sockets

other things

	cluster {join,leave}
	SMP vs cluster?

The hard one is sockets.  I've never seen a good solution to that.
I'll come back to that.  First, I want to go through the other ones and
offer suggestions.

Hosts are just hosts, nothing changes there.

Clusters are a mapping of "cluster_name" -> "list of hosts".  Think
of getclustbyname().  I did this for SparcClusters, it worked pretty
well.  The cluster is the name that you use to get to your cluster.
This implies that you wack rlogin/telnet and/or you wack DNS to 
to translate from the cluster name to the hostname to the IP address
of that host.  DNS is the easiest place.

Processes have two major chunks of work, the PID name space and how you
do remote processes.  For the PID name space, make pid_t a 32 bit int,
make the top 16 bits the host part, and the bottom 16 bits the pid part.
(We need to come back to the host part when we discuss process migration.)
A host part of "0" means "this host".  So a "kill -HUP 1" will always
restart init.

Remote processes.  This part gets fun, fun, fun.  Think of how we have
files as objects in the kernel, in C++ terms, an inode is a class with all
virtual methods - each instance of the class implments its own methods.
We need to do that for processes.  For every operation we currently
do on a process, we need to make that a function call.  You want this
layer to be very thin, it can't be a performance hit for local processes
or we blew it.  The intances of the process class I imagine are at
least "local", "remote", "local debugged", "remote debugged".  I can
also image using this to implement "local or remote, gang scheduled".
See how that works?  I'm hand waving like crazy here.  I'm not positive
the debugging stuff works in this layer, but I would love it if all the
System V /proc crap was buried in an optional instance of the process
class.  I believe that you can make the non debugged instance faster.

Devices I sort of punt on.  For device access, I would just use the 
remote mag tape protocol (or something very, very similar) so that all
of the locking, etc., still works - since you ship all the requests to
the system w/ the device, that kernel can implement the locks.  Any
issues here?

Files.  I have also punted on this.  I have never gotten that excited about
a cache coherent distributed file system, though others certainly do.  It's
not because I don't think it is useful.  I believe it can be done and that
we have the talent right here on this list to do it.  So I'll bow out of
commenting on it, other than to say make sure mmap works right.

Sockets.  This is a hard problem.  Some people think that a socket
should stick around after the CPU that created the socket has crashed.
I don't know how to do that efficiently, so I punt.  The only thing I
would suggest in the socket domain is (a) make gethostbyname("cluster")
be translated into a getclustbyname("cluster") so that you can think of
the cluster as one host (DNS or someone is round robining the host you
actually get), and (b) manage the routing tables within the cluster far
more dynamically that routing tables are corrently managed.  The latter
means that you notice immediately when a CPU leaves the cluster and
update your routing tables to route around that dead CPU.

Cluster {join,leave}  This turns out to be a thorny area.  You gotta get it
right, too.  You want the cluster to keep working in the face of a crashed
node.  You also want nodes to be taken out and added back into the cluster
for whatever reasons.  There's a whole set of protocol issues here that I'm 
too sick to describe, trust me that we have a lot of work in this area.

SMP vs cluster.  Lots of people wonder about this - do you do one, both, 
neither?  The smartest people I know, have all concluded the same thing:
you do 4 way SMP nodes, and cluster those to scale beyond the 4 CPUs.
The reasoning is as follows: when you are creating processes, you 
are striping them across the cluster (if you have a coherent distributed
mmap, rfork() is not that hard, seems worse than it is, but as a first
pass, just do rexec(), that will scale parallel make which is a great
test case).  It turns out from cache affinity studies that you really
want to avoid moving processes from one CPU/cache/memory to another.
It screws up your performance.  On the other hand, if you get unlucky
with your striping alg and land a couple of long running processes on
the same node, it is nice to have more than one CPU there to handle the
load.  Another way to state this: you need to balance your load.  If
you try and statically balance it at fork and/or exec time, you will
make mistakes because you don't have enough info at that point to do 
perfect scheduling job.  If you are sending jobs to SMPs instead of
uniprocessers, the SMPs can do a reasonable job of dynamically scheduling
the load.  And a 4 way SMP is a good first order approximation of an
infinitely large SMP, it is rare that you'll screw up so badly that 
you need more than 4 processors to smooth out the load.

So why am I beating on this issue so hard?  Because I don't want a 
fine grained threaded SMP kernel.  Threading the kernel that much introduces
way too much of a performance penalty for the simple case of "run this
one job".  Also consider that the SMP kernel may well form the basis for
a fully preemptable uniprocessor kernel.  I do not want to sacrafice more
than 1% performance on the uniprocessor to get preemption.  Solaris and
IRIX both suck at this - you pay big time for that checklist item.  

If you walk into the SMP arena with the model that you "fork" your system
every 4 processors, then you don't have to work so hard to get scaling.
Coarse grained, non intrusive locking will work just fine for 4 processors
and you leave the rest to the cluster.  Cool?

Finally - when doing all of this stuff, please do a 100Mbit ethernet based
version as well as the AP version.  If you come at it from a network point
of view, a whole bunch of problems will _not_ happen in the AP version.
When you have all that nice hardware, you tend to use it and it can
screw up the architecture such that a network based cluster won't work.
On the other hand, if you do a network based cluster, you are guarenteed
that you have a partioned solution.  As you try and make all of those
kernels work on that one big shared memory, you'll find that partitioning
is a big performance win.  Coming from a network cluster, you'll get that
without having to work for it - the other way frequently is harder.

That's enough for now, how about some comments?

--lm

---

From: Alan Cox <[email-masked]>
Date: Thu, 16 May 1996 10:09:17 +0100 (BST)

> : With 30 people now on this list there must be someone else who wants

I've not actually seen anything from the list (should be going to ukuu)

> 	SMP vs cluster?

Why vs, why not AND. An SMP box is just a couple of well connected nodes.

> I'll come back to that.  First, I want to go through the other ones and

There are several approaches to this. One is to treat it like a device so
you open a socket on a given machine and it like the device doesnt walk. The
other is to bend IP mobile to the needs. That would probably want something
like an old 486 as a network FEP.

> A host part of "0" means "this host".  So a "kill -HUP 1" will always

We can also do this for devices so you can mknod a printer on a different 
node.

> the system w/ the device, that kernel can implement the locks.  Any

The vfs issues fairly controlled requests to the FS layer, and the device
layer also is fairly clean. The MOSIX project intercepted stuff at this
level --- so a remote device turns the request into a message. The system
also accounted messages so a process like a find would migrate across cpus
as it changed the disk it was searching.

> commenting on it, other than to say make sure mmap works right.

mmap is foul. SYS5 shared memory is just as bad too. 

> should stick around after the CPU that created the socket has crashed.

If you are having a single apparent IP address this is true for TCP, you can
on spotting a down host just send an RST and go into TIME_WAIT to preserve
the corruption protection properties of TCP.

> without having to work for it - the other way frequently is harder.

It also means more people can play

---

From: Andrew Tridgell <[email-masked]>
Date: Fri, 17 May 1996 00:20:34 +1000

Larry,

I think what you describe is really a blueprint for a "throughput"
machine, a machine that gets its parallelism mostly from the fact that
you will be running lots of independent jobs on it at once. The
alternative is a "parallel" machine, which aims to get optimal
performance even when just running one or two programs.

For example, a throughput machine is an ideal departmental
server. Lots of people doing edits/compiles with some heavy computation
thrown in now and then. Its the sort of thing that clusters of
workstations normally do.

A "parallel" machine is what supercomputer centres often have. They
run just one or two jobs at once, but they are big jobs, like climate
modelling or fluid dynamics simulations. They use huge amounts of ram
(many GB) for the one process and require very tight communications
using specialised parallel libraries.

Our research group is really centered around parallel systems, with
algorithms that scale to thousands of cpus. Unfortunately our budget
only stretches to 16 cpus on the AP+ at the moment, but we can also
run on much larger systems like we did this week by connecting to the
"Parallel Computing Research Facility" at Fujitsu in Japan.

This approach has a number of implications:

- we're not as worried about the ability to dynamically enter/leave a
"cluster". This makes algorithms simpler and faster as they can use
data structures that assume that the number of cpus and their layout
stays static.

- we're not as worried about recovering/continuing if a cpu
crashes. If all user jobs are running on all cpus then it doesn't make
much sense to try to recover when one goes down, as it kills all user
jobs anyway, so you might as well shutdown (crash), replace the part
and startup again. Its not as though this is a common experience for
us anyway. I don't think we've had a hardware fault on our 128 cpu
ap1000 yet, after several years of operation.

- we're worried about getting the very best bandwidth/latency out of
the communications network, while still providing all the lovely
operating system services that Linux provides.

- we're worried about providing efficient parallel filesystem, memory
and networking abstractions, scalable to lots of processors.

> A host part of "0" means "this host".  So a "kill -HUP 1" will always

ok, this makes sense with what we've done so far, which is really just
a tightly integrated network of workstations. I'm not at all sure its
what we want in the long term however. It assumes that things like
init will be running on every cpu, so that you have to distinguish
which copy of init you mean when you send it a signal.

I'm hoping that we will eventually have a really "single system image"
machine, where only one copy of init is actually running. Most cpus
would not be running any system daemons at all, just the necessary
kernel threads. 

Right now we do in fact have one copy of init on each cpu, along with
lots of other daemons. We can get away with them all having the same
pid because the system isn't really parallel yet, there is no notion
of a remote syscall. (we have in fact done a remote signal send
operation for parallel programs, but its not as general as a remote
kill)

> the system w/ the device, that kernel can implement the locks.  Any

mostly speed issues. Could using something like rmt really scale to
lots of processors with reasonable performance?
 
> commenting on it, other than to say make sure mmap works right.

The big problems are indeed cache coherency and things like mmap(). We
implemented a parallel filesystem called HiDIOS on the 128 node ap1000
which worked by putting the buffer cache for a block on the cell that
owns the block. We didn't support mmap() as the machine had no mmu,
and the only cache local to each cpu is an optional one controlled by
the user in much the same way as stdio, but applied to file
descriptors in the C library.

We were able to get away with this because the remote memory access
bandwidth was very high (slightly higher in fact than local memory),
and latencies were low. We also used a really simple meta data
structure that completely elimated indirect blocks to find data on the
disk. We got 60MB/sec through the filesystem (the hardware limit is
64MB/sec).

We've seen attempts to put standard unix filesystem structures on
parallel machines and they are just not efficient enough. The cost of
manipulating all that meta data is huge when the disks (in parallel)
are capable of higher thoughputs than a local memory copy.

We are planning on doing a similar parallel filesystem for
Linux/AP+. We'll use a more sophisticated meta data scheme than was
used in the AP1000 HiDIOS, but still much simpler than that used in
ext2. It will be tuned for big io tasks, like loading 2GB of data
before the start of a heavy computing task. It will probably be
pathetic for loading your .cshrc, but we aren't going to be
encouraging people to use this system to run shell scripts on :-)

I still don't know how we are going to handle mmap. We think mmap is
very important in a parallel filesystem, but we just don't know how to
implement it in a really fast and coherent way yet.
 
> should stick around after the CPU that created the socket has crashed.

yep, sockets are probably hard. We've already met problems with
them and we haven't even tried to make them parallel yet :-)

We use sockets to implement the stdin/stdout/stderr of parallel
processes. The paralleld that launches parallel programs on each cell
first creates 3 sockets back to the launching program, setting them up
as file desciptors 0, 1 and 2. When it then does a fork()/exec() the
parallel program inherits them.

The problem is that on a 64 cell machine we end up having 192 sockets
connected to the one process on the front end that launched the
parallel program. This is madness! It also won't work well if we have
1024 cpus :-)

I'm hoping this problem will go away when we revamp the way we launch
parallel programs. If we had a remote fork() and/or remote exec()
and also had a way for the file descriptors of remote forked processes
to feed back into the parent cpu then it would be much better. 

We'd probably also need to use a tree structure to feed the file
descriptors (and paging for that matter) back up into the parent
process. 1000 children all writing to one parent would not be pretty. 

> too sick to describe, trust me that we have a lot of work in this area.

This is a really interesting area to work on, but its probably not
something our group will be looking at soon, for the reasons described
earlier. We've got to focus our attentions a bit :-)
 
> without having to work for it - the other way frequently is harder.

We probably won't do a 100Mbit version ourselves, we just don't have
the time. We'd love to cooperate with people that are doing it,
however, and I hope that a lot of what we do will be relevant for
systems like that.

The problem is really latency. Ethernet type systems have latencies
which aren't much lower than the system clock tick interval. This
means it often makes sense to do things is quite different ways to
what we have to do.

Cheers, Andrew

---

From: [email-masked] (Alan Cox)
Date: Thu, 16 May 1996 18:19:16 +0100 (BST)

> parallel program inherits them.

Two things strike me here. Firstly if you are doing that kind of output
redirection across 192 cells you are going to need 192 logical connections
however you do it. Secondly you really want your node end library to be
a bit smarter and pass a tty check across the link so you can use tty/pty
pairs if the real descriptor is a tty.

> to feed back into the parent cpu then it would be much better. 

MOSIX does this by trapping them at the VFS layer. Effectively each inode
and file handle has a host field and if the operation is remote you RPC.

> process. 1000 children all writing to one parent would not be pretty. 

It would be an interesting application of multicast groups to allow the parent
to roam as well. With 1000 children thats an even bigger scaling problem, and
for sending stuff to a large number of nodes (eg a loosely synchronized SIMD
job) its going to be needed.

> means it often makes sense to do things is quite different ways to

Yes. The latency also means that attacking from two other angles is interesting
Firstly 10Mbit ethernet - latency is no worse really just we have to be more
reluctant to bulk copy data, and also combining it with something like the
TTL PAPERS device for the fast sync stuff (its a $60 to build parallel port
synchronization system with about a 3uS overhead). Very limited but might
solve some of our problems on ethernet linked boxes.

Alan