Re: McVoy's Clusters (was Re: latest linus-2.5 BK broken)

Re: McVoy's Clusters (was Re: latest linus-2.5 BK broken)

[Jesse Pollard]

Sandy Harris <pashley@storm.ca>
> 
> [ I removed half a dozen cc's on this, and am just sending to the
>   list. Do people actually want the cc's?]
> 
> Larry McVoy wrote:
> 
> > > Checkpointing buys three things.  The ability to preempt jobs, the
> > > ability to migrate processes,
> 
> For large multi-processor systems, it isn't clear that those matter
> much. On single user systems I've tried , ps -ax | wc -l usually
> gives some number 50 < n < 100. For a multi-user general purpose
> system, my guess would be something under 50 system processes plus
> 50 per user. So for a dozen to 20 users on a departmental server,
> under 1000. A server for a big application, like database or web,
> would have fewer users and more threads, but still only a few 100
> or at most, say 2000.

You don't use compute servers much? The problems we are currently running
require the cluster (IBM SP) to have 100% uptime for a single job. that
job may run for several days. If a detected problem is reported (not yet
catastrophic) it is desired/demanded to checkpoint the users process.

Currently, we can't - but should be able to by this fall.

Having the users job checkpoint midway in it's computations will allow us
to remove a node from active service, substitute a different node, and
resume the users process without losing many hours of computation (we have
a maximum of 300 nodes for computation, another 30 for I/O and front end).

Just because a network interface fails is no reason to lose the job.

> So at something like 8 CPUs in a personal workstation and 128 or
> 256 for a server, things average out to 8 processes per CPU, and
> it is not clear that process migration or any form of pre-emption
> beyond the usual kernel scheduling is needed.
> 
> What combination of resources and loads do you think preemption
> and migration are need for?

It depends on the job. A web server farm shouldn't need one. A distributed
compute cluster needs it to:

a. be able to suspend large (256-300 nodes), long running (4-8 hours),
   low priority jobs, to favor high priority production jobs (which may
   also be relatively long running: say 2-4 hours on 256 nodes.
b. be able to replace/substitute nodes (switch processing from a failing
   node to allow for on-line replacement of the failing node or to wait for
   spare parts).

> > > and the ability to recover from failed nodes, (assuming the 
> > > failed hardware didn't corrupt your jobs checkpoint).
> 
> That matters, but it isn't entirely clear that it needs to be done
> in the kernel. Things like databases and journalling filesystems
> already have their own mechanisms and it is not remarkably onerous
> to put them into applications where required.

Which is why I realized you don't use compute clusters very often.

1. User jobs, written in fortran/C/other do not usually come with the ability
   to take snapshots of computation.
2. there is the problem of redirecting network connections (MPI/PVM) from one
   place to another.
3. (related to 2) Synchronized process suspension is difficult-to-impossible
   to do outside the kernel.

> [big snip]
> 
> > Larry McVoy's SMP Clusters
> > 
> > Discussion on November 8, 2001
> > 
> > Larry McVoy, Ted T'so, and Paul McKenney
> > 
> > What is SMP Clusters?
> > 
> >      SMP Clusters is a method of partioning an SMP (symmetric
> >      multiprocessing) machine's CPUs, memory, and I/O devices
> >      so that multiple "OSlets" run on this machine.  Each OSlet
> >      owns and controls its partition.  A given partition is
> >      expected to contain from 4-8 CPUs, its share of memory,
> >      and its share of I/O devices.  A machine large enough to
> >      have SMP Clusters profitably applied is expected to have
> >      enough of the standard I/O adapters (e.g., ethernet,
> >      SCSI, FC, etc.) so that each OSlet would have at least
> >      one of each.
> 
> I'm not sure whose definition this is:
>    supercomputer: a device for converting compute-bound problems
>       into I/O-bound problems
> but I suspect it is at least partially correct, and Beowulfs are
> sometimes just devices to convert them to network-bound problems.
> 
> For a network-bound task like web serving, I can see a large
> payoff in having each OSlet doing its own I/O.
> 
> However, in general I fail to see why each OSlet should have
> independent resources rather than something like using one to
> run a shared file system and another to handle the networking
> for everybody.

How about reliability, security isolation (accounting server isolated
from a web server or audit server.. or both).

See Suns use of "domains" in Solaris which does this in a single host.

-------------------------------------------------------------------------
Jesse I Pollard, II
Email: pollard@navo.hpc.mil

Any opinions expressed are solely my own.

Re: McVoy's Clusters (was Re: latest linus-2.5 BK broken)

[Nick LeRoy]

On Thursday 20 June 2002 12:23 pm, Jesse Pollard wrote:
<snip>
> You don't use compute servers much? The problems we are currently running
> require the cluster (IBM SP) to have 100% uptime for a single job. that
> job may run for several days. If a detected problem is reported (not yet
> catastrophic) it is desired/demanded to checkpoint the users process.
>
> Currently, we can't - but should be able to by this fall.
>
> Having the users job checkpoint midway in it's computations will allow us
> to remove a node from active service, substitute a different node, and
> resume the users process without losing many hours of computation (we have
> a maximum of 300 nodes for computation, another 30 for I/O and front end).

Have you tried Condor?  Condor is a "high throughput computing" package, 
specifically targetted at such applications, with the ability to checkpoint & 
migrate jobs, etc.  Condor is free as in beer, but currently not as in speech 
(sorry), and is developed by the University of Wisconsin.  
http://www.condorproject.org is the URL to learn more.  Version 6.4.0 is in 
the process of being released and should be available within the next couple 
of days.

Condor runs on Linux (x86 & Alpha), Solaris, IRIX, HPUX, Digital Unix, and 
NT, although the NT usually lags the Unix releases.

-Nick
Academic Staff at UW on the Condor Team

Re: McVoy's Clusters (was Re: latest linus-2.5 BK broken)

[Jesse Pollard]

Nick LeRoy <nleroy@cs.wisc.edu>:
> 
> On Thursday 20 June 2002 12:23 pm, Jesse Pollard wrote:
> <snip>
> > You don't use compute servers much? The problems we are currently running
> > require the cluster (IBM SP) to have 100% uptime for a single job. that
> > job may run for several days. If a detected problem is reported (not yet
> > catastrophic) it is desired/demanded to checkpoint the users process.
> >
> > Currently, we can't - but should be able to by this fall.
> >
> > Having the users job checkpoint midway in it's computations will allow us
> > to remove a node from active service, substitute a different node, and
> > resume the users process without losing many hours of computation (we have
> > a maximum of 300 nodes for computation, another 30 for I/O and front end).
> 
> Have you tried Condor?  Condor is a "high throughput computing" package, 
> specifically targetted at such applications, with the ability to checkpoint & 
> migrate jobs, etc.  Condor is free as in beer, but currently not as in speech 
> (sorry), and is developed by the University of Wisconsin.  
> http://www.condorproject.org is the URL to learn more.  Version 6.4.0 is in 
> the process of being released and should be available within the next couple 
> of days.
> 
> Condor runs on Linux (x86 & Alpha), Solaris, IRIX, HPUX, Digital Unix, and 
> NT, although the NT usually lags the Unix releases.

Condor is designed for a relatively low performance network (10-100Mbit) and
not for things like an IBM SP switch which can carry Gbit data. It needs
availablility on SP-3/4 and Cray SV systems (not that we have problems
with checkpoint there). Also note:

	Cannot use IPC (pipes shared memory), which also leave out PVM/MPI
	job cannot use threads
	cannot use forks

In many of our cases, the jobs are split across many nodes, then spread
across multiple processors in a single node (SP 3 has 4 cpus per node,
SP 4 will have 8-32). The current scientific library uses PVM/MPI to determine
whether it is using shared memory or node/node RPC.

Tightly integrated models wouldn't work well with Condor (disclaimer:
based on a fast look by me, and I don't work on the current jobs).

-------------------------------------------------------------------------
Jesse I Pollard, II
Email: pollard@navo.hpc.mil

Any opinions expressed are solely my own.

Re: latest linus-2.5 BK broken

[Linus Torvalds]

On 19 Jun 2002, Eric W. Biederman wrote:
>
> 10-20 years or someone finds a good way to implement a single system
> image on linux clusters.  They are already into the 1000s of nodes,
> and dual processors per node category.  And as things continue they
> might even grow bigger.

Oh, clusters are a separate issue. I'm absolutely 100% conviced that you
don't want to have a "single kernel" for a cluster, you want to run
independent kernels with good communication infrastructure between them
(ie global filesystem, and try to make the networking look uniform).

Trying to have a single kernel for thousands of nodes is just crazy. Even
if the system were ccNuma and _could_ do it in theory.

The NuMA work can probably take single-kernel to maybe 64+ nodes, before
people just start turning stark raving mad. There's no way you'll have
single-kernel for thousands of CPU's, and still stay sane and claim any
reasonable performance under generic loads.

So don't confuse the issue with clusters like that. The "set_affinity()"
call simply doesn't have anything to do with them. If you want to move
processes between nodes on such a cluster, you'll probably need user-level
help, the kernel is unlikely to do it for you.

			Linus

Re: latest linus-2.5 BK broken

[Eric W. Biederman]

Linus Torvalds <torvalds@transmeta.com> writes:

> On 19 Jun 2002, Eric W. Biederman wrote:
> >
> > 10-20 years or someone finds a good way to implement a single system
> > image on linux clusters.  They are already into the 1000s of nodes,
> > and dual processors per node category.  And as things continue they
> > might even grow bigger.
> 
> Oh, clusters are a separate issue. I'm absolutely 100% conviced that you
> don't want to have a "single kernel" for a cluster, you want to run
> independent kernels with good communication infrastructure between them
> (ie global filesystem, and try to make the networking look uniform).
> 
> Trying to have a single kernel for thousands of nodes is just crazy. Even
> if the system were ccNuma and _could_ do it in theory.

I totally agree, mostly I was playing devils advocate.  The model
actually in my head is when you have multiple kernels but they talk
well enough that the applications have to care in areas where it
doesn't make a performance difference (There's got to be one of those).

> The NuMA work can probably take single-kernel to maybe 64+ nodes, before
> people just start turning stark raving mad. There's no way you'll have
> single-kernel for thousands of CPU's, and still stay sane and claim any
> reasonable performance under generic loads.
> 
> So don't confuse the issue with clusters like that. The "set_affinity()"
> call simply doesn't have anything to do with them. If you want to move
> processes between nodes on such a cluster, you'll probably need user-level
> help, the kernel is unlikely to do it for you.

Agreed.  

The compute cluster problem is an interesting one.  The big items
I see on the todo list are:

- Scalable fast distributed file system (Lustre looks like a
   possibility)
- Sub application level checkpointing.

Services like a schedulers, already exist.  

Basically the job of a cluster scheduler gets much easier, and the
scheduler more powerful once it gets the ability to suspend jobs.
Checkpointing buys three things.  The ability to preempt jobs, the
ability to migrate processes, and the ability to recover from failed
nodes, (assuming the failed hardware didn't corrupt your jobs
checkpoint).

Once solutions to the cluster problems become well understood I
wouldn't be surprised if some of the supporting services started to
live in the kernel like nfsd.  Parts of the distributed filesystem
certainly will.

I suspect process checkpointing and restoring will evolve something
something like pthread support.  With some code in user space, and
some generic helpers in the kernel as clean pieces of the job can be
broken off.  The challenge is only how to save/restore interprocess
communications. Things like moving a tcp connection from one node to
another are interesting problems.  

But also I suspect most of the hard problems that we need kernel help
with can have uses independent of checkpointing.  Already we have web
server farms that spread connections to a single ip across nodes.

Eric

Re: latest linus-2.5 BK broken

[Larry McVoy]

> I totally agree, mostly I was playing devils advocate.  The model
> actually in my head is when you have multiple kernels but they talk
> well enough that the applications have to care in areas where it
> doesn't make a performance difference (There's got to be one of those).

....

> The compute cluster problem is an interesting one.  The big items
> I see on the todo list are:
> 
> - Scalable fast distributed file system (Lustre looks like a
>    possibility)
> - Sub application level checkpointing.
> 
> Services like a schedulers, already exist.  
> 
> Basically the job of a cluster scheduler gets much easier, and the
> scheduler more powerful once it gets the ability to suspend jobs.
> Checkpointing buys three things.  The ability to preempt jobs, the
> ability to migrate processes, and the ability to recover from failed
> nodes, (assuming the failed hardware didn't corrupt your jobs
> checkpoint).
> 
> Once solutions to the cluster problems become well understood I
> wouldn't be surprised if some of the supporting services started to
> live in the kernel like nfsd.  Parts of the distributed filesystem
> certainly will.

http://www.bitmover.com/cc-pitch

I've been trying to get Linus to listen to this for years and he keeps
on flogging the tired SMP horse instead.  DEC did it and Sun has been
passing around these slides for a few weeks, so maybe they'll do it too.
Then Linux can join the party after it has become a fine grained, 
locked to hell and back, soft "realtime", numa enabled, bloated piece
of crap like all the other kernels and we'll get to go through the 
"let's reinvent Unix for the 3rd time in 40 years" all over again.
What fun.  Not.

Sorry to be grumpy, go read the slides, I'll be at OLS, I'd be happy
to talk it over with anyone who wants to think about it.  Paul McKenney
from IBM came down the San Francisco to talk to me about it, put me 
through an 8 or 9 hour session which felt like a PhD exam, and 
after trying to poke holes in it grudgingly let on that maybe it was
a good idea.  He was kind of enough to write up what he took away 
from it, here it is.

--lm

From: "Paul McKenney" <Paul.McKenney@us.ibm.com>
To: lm@bitmover.com, tytso@mit.edu
Subject: Greatly enjoyed our discussion yesterday!
Date: Fri, 9 Nov 2001 18:48:56 -0800

Hello!

I greatly enjoyed our discussion yesterday!  Here are the pieces of it that
I recall, I know that you will not be shy about correcting any errors and
omissions.

                         Thanx, Paul

Larry McVoy's SMP Clusters

Discussion on November 8, 2001

Larry McVoy, Ted T'so, and Paul McKenney


What is SMP Clusters?

     SMP Clusters is a method of partioning an SMP (symmetric
     multiprocessing) machine's CPUs, memory, and I/O devices
     so that multiple "OSlets" run on this machine.  Each OSlet
     owns and controls its partition.  A given partition is
     expected to contain from 4-8 CPUs, its share of memory,
     and its share of I/O devices.  A machine large enough to
     have SMP Clusters profitably applied is expected to have
     enough of the standard I/O adapters (e.g., ethernet,
     SCSI, FC, etc.) so that each OSlet would have at least
     one of each.

     Each OSlet has the same data structures that an isolated
     OS would have for the same amount of resources.  Unless
     interactions with the OSlets are required, an OSlet runs
     very nearly the same code over very nearly the same data
     as would a standalone OS.

     Although each OSlet is in most ways its own machine, the
     full set of OSlets appears as one OS to any user programs
     running on any of the OSlets.  In particular, processes on
     on OSlet can share memory with processes on other OSlets,
     can send signals to processes on other OSlets, communicate
     via pipes and Unix-domain sockets with processes on other
     OSlets, and so on.  Performance of operations spanning
     multiple OSlets may be somewhat slower than operations local
     to a single OSlet, but the difference will not be noticeable
     except to users who are engaged in careful performance
     analysis.

     The goals of the SMP Cluster approach are:

     1.   Allow the core kernel code to use simple locking designs.
     2.   Present applications with a single-system view.
     3.   Maintain good (linear!) scalability.
     4.   Not degrade the performance of a single CPU beyond that
          of a standalone OS running on the same resources.
     5.   Minimize modification of core kernel code.  Modified or
          rewritten device drivers, filesystems, and
          architecture-specific code is permitted, perhaps even
          encouraged.  ;-)


OS Boot

     Early-boot code/firmware must partition the machine, and prepare
     tables for each OSlet that describe the resources that each
     OSlet owns.  Each OSlet must be made aware of the existence of
     all the other OSlets, and will need some facility to allow
     efficient determination of which OSlet a given resource belongs
     to (for example, to determine which OSlet a given page is owned
     by).

     At some point in the boot sequence, each OSlet creates a "proxy
     task" for each of the other OSlets that provides shared services
     to them.

     Issues:

     1.   Some systems may require device probing to be done
          by a central program, possibly before the OSlets are
          spawned.  Systems that react in an unfriendly manner
          to failed probes might be in this class.

     2.   Interrupts must be set up very carefully.  On some
          systems, the interrupt system may constrain the ways
          in which the system is partitioned.


Shared Operations

     This section describes some possible implementations and issues
     with a number of the shared operations.

     Shared operations include:

     1.   Page fault on memory owned by some other OSlet.
     2.   Manipulation of processes running on some other OSlet.
     3.   Access to devices owned by some other OSlet.
     4.   Reception of network packets intended for some other OSlet.
     5.   SysV msgq and sema operations on msgq and sema objects
          accessed by processes running on multiple of the OSlets.
     6.   Access to filesystems owned by some other OSlet.  The
          /tmp directory gets special mention.
     7.   Pipes connecting processes in different OSlets.
     8.   Creation of processes that are to run on a different
          OSlet than their parent.
     9.   Processing of exit()/wait() pairs involving processes
          running on different OSlets.

     Page Fault

          As noted earlier, each OSlet maintains a proxy process
          for each other OSlet (so that for an SMP Cluster made
          up of N OSlets, there are N*(N-1) proxy processes).

          When a process in OSlet A wishes to map a file
          belonging to OSlet B, it makes a request to B's proxy
          process corresponding to OSlet A.  The proxy process
          maps the desired file and takes a page fault at the
          desired address (translated as needed, since the file
          will usually not be mapped to the same location in the
          proxy and client processes), forcing the page into
          OSlet B's memory.  The proxy process then passes the
          corresponding physical address back to the client
          process, which maps it.

          Issues:

          o    How to coordinate pageout?  Two approaches:

               1.   Use mlock in the proxy process so that
                    only the client process can do the pageout.

               2.   Make the two OSlets coordinate their
                    pageouts.  This is more complex, but will
                    be required in some form or another to
                    prevent OSlets from "ganging up" on one
                    of their number, exhausting its memory.

          o    When OSlet A ejects the memory from its working
               set, where does it put it?

               1.   Throw it away, and go to the proxy process
                    as needed to get it back.

               2.   Augment core VM as needed to track the
                    "guest" memory.  This may be needed for
                    performance, but...

          o    Some code is required in the pagein() path to
               figure out that the proxy must be used.

               1.   Larry stated that he is willing to be
                    punched in the nose to get this code in.  ;-)
                    The amount of this code is minimized by
                    creating SMP-clusters-specific filesystems,
                    which have their own functions for mapping
                    and releasing pages.  (Does this really
                    cover OSlet A's paging out of this memory?)

          o    How are pagein()s going to be even halfway fast
               if IPC to the proxy is involved?

               1.   Just do it.  Page faults should not be
                    all that frequent with today's memory
                    sizes.  (But then why do we care so
                    much about page-fault performance???)

               2.   Use "doors" (from Sun), which are very
                    similar to protected procedure call
                    (from K42/Tornado/Hurricane).  The idea
                    is that the CPU in OSlet A that is handling
                    the page fault temporarily -becomes- a
                    member of OSlet B by using OSlet B's page
                    tables for the duration.  This results in
                    some interesting issues:

                    a.   What happens if a process wants to
                         block while "doored"?  Does it
                         switch back to being an OSlet A
                         process?

                    b.   What happens if a process takes an
                         interrupt (which corresponds to
                         OSlet A) while doored (thus using
                         OSlet B's page tables)?

                         i.   Prevent this by disabling
                              interrupts while doored.
                              This could pose problems
                              with relatively long VM
                              code paths.

                         ii.  Switch back to OSlet A's
                              page tables upon interrupt,
                              and switch back to OSlet B's
                              page tables upon return
                              from interrupt.  On machines
                              not supporting ASID, take a
                              TLB-flush hit in both
                              directions.  Also likely
                              requires common text (at
                              least for low-level interrupts)
                              for all OSlets, making it more
                              difficult to support OSlets
                              running different versions of
                              the OS.

                              Furthermore, the last time
                              that Paul suggested adding
                              instructions to the interrupt
                              path, several people politely
                              informed him that this would
                              require a nose punching.  ;-)

                    c.   If a bunch of OSlets simultaneously
                         decide to invoke their proxies on
                         a particular OSlet, that OSlet gets
                         lock contention corresponding to
                         the number of CPUs on the system
                         rather than to the number in a
                         single OSlet.  Some approaches to
                         handle this:

                         i.   Stripe -everything-, rely
                              on entropy to save you.
                              May still have problems with
                              hotspots (e.g., which of the
                              OSlets has the root of the
                              root filesystem?).

                         ii.  Use some sort of queued lock
                              to limit the number CPUs that
                              can be running proxy processes
                              in a given OSlet.  This does
                              not really help scaling, but
                              would make the contention
                              less destructive to the
                              victim OSlet.

          o    How to balance memory usage across the OSlets?

               1.   Don't bother, let paging deal with it.
                    Paul's previous experience with this
                    philosophy was not encouraging.  (You
                    can end up with one OSlet thrashing
                    due to the memory load placed on it by
                    other OSlets, which don't see any
                    memory pressure.)

               2.   Use some global memory-pressure scheme
                    to even things out.  Seems possible,
                    Paul is concerned about the complexity
                    of this approach.  If this approach is
                    taken, make sure someone with some
                    control-theory experience is involved.


     Manipulation of Processes Running on Some Other OSlet.

          The general idea here is to implement something similar
          to a vproc layer.  This is common code, and thus requires
          someone to sacrifice their nose.  There was some discussion
          of other things that this would be useful for, but I have
          lost them.

          Manipulations discussed included signals and job control.

          Issues:

          o    Should process information be replicated across
               the OSlets for performance reasons?  If so, how
               much, and how to synchronize.

               1.   No, just use doors.  See above discussion.

               2.   Yes.  No discussion of synchronization
                    methods.  (Hey, we had to leave -something-
                    for later!)

     Access to Devices Owned by Some Other OSlet

          Larry mentioned a /rdev, but if we discussed any details
          of this, I have lost them.  Presumably, one would use some
          sort of IPC or doors to make this work.

     Reception of Network Packets Intended for Some Other OSlet.

          An OSlet receives a packet, and realizes that it is
          destined for a process running in some other OSlet.
          How is this handled without rewriting most of the
          networking stack?

          The general approach was to add a NAT-like layer that
          inspected the packet and determined which OSlet it was
          destined for.  The packet was then forwarded to the
          correct OSlet, and subjected to full IP-stack processing.

          Issues:

          o    If the address map in the kernel is not to be
               manipulated on each packet reception, there
               needs to be a circular buffer in each OSlet for
               each of the other OSlets (again, N*(N-1) buffers).
               In order to prevent the buffer from needing to
               be exceedingly large, packets must be bcopy()ed
               into this buffer by the OSlet that received
               the packet, and then bcopy()ed out by the OSlet
               containing the target process.  This could add
               a fair amount of overhead.

               1.   Just accept the overhead.  Rely on this
                    being an uncommon case (see the next issue).

               2.   Come up with some other approach, possibly
                    involving the user address space of the
                    proxy process.  We could not articulate
                    such an approach, but it was late and we
                    were tired.

          o    If there are two processes that share the FD
               on which the packet could be received, and these
               two processes are in two different OSlets, and
               neither is in the OSlet that received the packet,
               what the heck do you do???

               1.   Prevent this from happening by refusing
                    to allow processes holding a TCP connection
                    open to move to another OSlet.  This could
                    result in load-balance problems in some
                    workloads, though neither Paul nor Ted were
                    able to come up with a good example on the
                    spot (seeing as BAAN has not been doing really
                    well of late).

                    To indulge in l'esprit d'escalier...  How
                    about a timesharing system that users
                    access from the network?  A single user
                    would have to log on twice to run a job
                    that consumed more than one OSlet if each
                    process in the job might legitimately need
                    access to stdin.

               2.   Do all protocol processing on the OSlet
                    on which the packet was received, and
                    straighten things out when delivering
                    the packet data to the receiving process.
                    This likely requires changes to common
                    code, hence someone to volunteer their nose.


     SysV msgq and sema Operations

          We didn't discuss these.  None of us seem to be SysV fans,
          but these must be made to work regardless.

          Larry says that shm should be implemented in terms of mmap(),
          so that this case reduces to page-mapping discussed above.
          Of course, one would need a filesystem large enough to handle
          the largest possible shmget.  Paul supposes that one could
          dynamically create a memory filesystem to avoid problems here,
          but is in no way volunteering his nose to this cause.


     Access to Filesystems Owned by Some Other OSlet.

          For the most part, this reduces to the mmap case.  However,
          partitioning popular filesystems over the OSlets could be
          very helpful.  Larry mentioned that this had been prototyped.
          Paul cannot remember if Larry promised to send papers or
          other documentation, but duly requests them after the fact.

          Larry suggests having a local /tmp, so that /tmp is in effect
          private to each OSlet.  There would be a /gtmp that would
          be a globally visible /tmp equivalent.  We went round and
          round on software compatibility, Paul suggesting a hashed
          filesystem as an alternative.  Larry eventually pointed out
          that one could just issue different mount commands to get
          a global filesystem in /tmp, and create a per-OSlet /ltmp.
          This would allow people to determine their own level of
          risk/performance.


     Pipes Connecting Processes in Different OSlets.

          This was mentioned, but I have forgotten the details.
          My vague recollections lead me to believe that some
          nose-punching was required, but I must defer to Larry
          and Ted.

          Ditto for Unix-domain sockets.


     Creation of Processes on a Different OSlet Than Their Parent.

          There would be a inherited attribute that would prevent
          fork() or exec() from creating its child on a different
          OSlet.  This attribute would be set by default to prevent
          too many surprises.  Things like make(1) would clear
          this attribute to allow amazingly fast kernel builds.

          There would also be a system call that would cause the
          child to be placed on a specified OSlet (Paul suggested
          use of HP's "launch policy" concept to avoid adding yet
          another dimension to the exec() combinatorial explosion).

          The discussion of packet reception lead Larry to suggest
          that cross-OSlet process creation would be prohibited if
          the parent and child shared a socket.  See above for the
          load-balancing concern and corresponding l'esprit d'escalier.


     Processing of exit()/wait() Pairs Crossing OSlet Boundaries

          We didn't discuss this.  My guess is that vproc deals
          with it.  Some care is required when optimizing for this.
          If one hands off to a remote parent that dies before
          doing a wait(), one would not want one of the init
          processes getting a nasty surprise.

          (Yes, there are separate init processes for each OSlet.
          We did not talk about implications of this, which might
          occur if one were to need to send a signal intended to
          be received by all the replicated processes.)


Other Desiderata:

1.   Ability of surviving OSlets to continue running after one of their
     number fails.

     Paul was quite skeptical of this.  Larry suggested that the
     "door" mechanism could use a dynamic-linking strategy.  Paul
     remained skeptical.  ;-)

2.   Ability to run different versions of the OS on different OSlets.

     Some discussion of this above.


The Score.

     Paul agreed that SMP Clusters could be implemented.  He was not
     sure that it could achieve good performance, but could not prove
     otherwise.  Although he suspected that the complexity might be
     less than the proprietary highly parallel Unixes, he was not
     convinced that it would be less than Linux would be, given the
     Linux community's emphasis on simplicity in addition to performance.

-- 
---
Larry McVoy            	 lm at bitmover.com           http://www.bitmover.com/lm 

McVoy's Clusters (was Re: latest linus-2.5 BK broken)

[Sandy Harris]

[ I removed half a dozen cc's on this, and am just sending to the
  list. Do people actually want the cc's?]

Larry McVoy wrote:

> > Checkpointing buys three things.  The ability to preempt jobs, the
> > ability to migrate processes,

For large multi-processor systems, it isn't clear that those matter
much. On single user systems I've tried , ps -ax | wc -l usually
gives some number 50 < n < 100. For a multi-user general purpose
system, my guess would be something under 50 system processes plus
50 per user. So for a dozen to 20 users on a departmental server,
under 1000. A server for a big application, like database or web,
would have fewer users and more threads, but still only a few 100
or at most, say 2000.

So at something like 8 CPUs in a personal workstation and 128 or
256 for a server, things average out to 8 processes per CPU, and
it is not clear that process migration or any form of pre-emption
beyond the usual kernel scheduling is needed.

What combination of resources and loads do you think preemption
and migration are need for?

> > and the ability to recover from failed nodes, (assuming the 
> > failed hardware didn't corrupt your jobs checkpoint).

That matters, but it isn't entirely clear that it needs to be done
in the kernel. Things like databases and journalling filesystems
already have their own mechanisms and it is not remarkably onerous
to put them into applications where required.

[big snip]

> Larry McVoy's SMP Clusters
> 
> Discussion on November 8, 2001
> 
> Larry McVoy, Ted T'so, and Paul McKenney
> 
> What is SMP Clusters?
> 
>      SMP Clusters is a method of partioning an SMP (symmetric
>      multiprocessing) machine's CPUs, memory, and I/O devices
>      so that multiple "OSlets" run on this machine.  Each OSlet
>      owns and controls its partition.  A given partition is
>      expected to contain from 4-8 CPUs, its share of memory,
>      and its share of I/O devices.  A machine large enough to
>      have SMP Clusters profitably applied is expected to have
>      enough of the standard I/O adapters (e.g., ethernet,
>      SCSI, FC, etc.) so that each OSlet would have at least
>      one of each.

I'm not sure whose definition this is:
   supercomputer: a device for converting compute-bound problems
      into I/O-bound problems
but I suspect it is at least partially correct, and Beowulfs are
sometimes just devices to convert them to network-bound problems.

For a network-bound task like web serving, I can see a large
payoff in having each OSlet doing its own I/O.

However, in general I fail to see why each OSlet should have
independent resources rather than something like using one to
run a shared file system and another to handle the networking
for everybody.

Re: McVoy's Clusters (was Re: latest linus-2.5 BK broken)

[William Lee Irwin III]

On Thu, Jun 20, 2002 at 11:41:45AM -0400, Sandy Harris wrote:
> For large multi-processor systems, it isn't clear that those matter
> much. On single user systems I've tried , ps -ax | wc -l usually
> gives some number 50 < n < 100. For a multi-user general purpose
> system, my guess would be something under 50 system processes plus
> 50 per user. So for a dozen to 20 users on a departmental server,
> under 1000. A server for a big application, like database or web,
> would have fewer users and more threads, but still only a few 100
> or at most, say 2000.

Certain unnameable databases like to have 2K processes at minimum and
see task counts soar even higher under significant loads.

Also, the scholastic departmental servers I've seen in action generally
host 300+ users with something less than 50/logged in user and something
more than 50 for the baseline. For the school-wide one I used hosting
10K+ (40K+?) users generally only between 500 and 2500 (where the non-rare
maximum was around 1500) are logged in simultaneously, and the task/user
count was more like 5-10, with a number of them (most?) riding at 2 or 3
(shell + MUA or shell + 2 tasks for rlogin to elsewhere). The uncertainty
with respect to number of accounts is due to no userlists being visible.

I can try to contact some of the users or administrators if better
numbers are needed, though it may not work as I've long since graduated.

Cheers,
Bill

Re: McVoy's Clusters (was Re: latest linus-2.5 BK broken)

[Timothy D. Witham]

Another point is that I've seen large multi-user machines that roll
a 32 bi pid in less than 1/2 hour. So not only is it a large
number of process but also a very dynamic process environment.

Tim

On Thu, 2002-06-20 at 10:10, William Lee Irwin III wrote:
> On Thu, Jun 20, 2002 at 11:41:45AM -0400, Sandy Harris wrote:
> > For large multi-processor systems, it isn't clear that those matter
> > much. On single user systems I've tried , ps -ax | wc -l usually
> > gives some number 50 < n < 100. For a multi-user general purpose
> > system, my guess would be something under 50 system processes plus
> > 50 per user. So for a dozen to 20 users on a departmental server,
> > under 1000. A server for a big application, like database or web,
> > would have fewer users and more threads, but still only a few 100
> > or at most, say 2000.
> 
> Certain unnameable databases like to have 2K processes at minimum and
> see task counts soar even higher under significant loads.
> 
> Also, the scholastic departmental servers I've seen in action generally
> host 300+ users with something less than 50/logged in user and something
> more than 50 for the baseline. For the school-wide one I used hosting
> 10K+ (40K+?) users generally only between 500 and 2500 (where the non-rare
> maximum was around 1500) are logged in simultaneously, and the task/user
> count was more like 5-10, with a number of them (most?) riding at 2 or 3
> (shell + MUA or shell + 2 tasks for rlogin to elsewhere). The uncertainty
> with respect to number of accounts is due to no userlists being visible.
> 
> I can try to contact some of the users or administrators if better
> numbers are needed, though it may not work as I've long since graduated.
> 
> Cheers,
> Bill
> -
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at  http://www.tux.org/lkml/
-- 
Timothy D. Witham - Lab Director - wookie@osdlab.org
Open Source Development Lab Inc - A non-profit corporation
15275 SW Koll Parkway - Suite H - Beaverton OR, 97006
(503)-626-2455 x11 (office)    (503)-702-2871     (cell)
(503)-626-2436     (fax)

Re: McVoy's Clusters (was Re: latest linus-2.5 BK broken)

[Eric W. Biederman]

Sandy Harris <pashley@storm.ca> writes:

> [ I removed half a dozen cc's on this, and am just sending to the
>   list. Do people actually want the cc's?]
> 
> Larry McVoy wrote:
> 
> > > Checkpointing buys three things.  The ability to preempt jobs, the
> > > ability to migrate processes,

 
> For large multi-processor systems, it isn't clear that those matter
> much. 

The systems that are built because there is no machine that can
run your compute intensive application fast enough they matter quite
a bit.
 
> What combination of resources and loads do you think preemption
> and migration are need for?

Good answers have already been given.
The problem domain I am looking at are compute clusters.  The
solutions are useful elsewhere but in compute clusters they are
extremely valuable.

> > > and the ability to recover from failed nodes, (assuming the 
> > > failed hardware didn't corrupt your jobs checkpoint).
> 
> That matters, but it isn't entirely clear that it needs to be done
> in the kernel. 

I agree, glibc would be fine, but it must be below the level of
the application.   Generally it is a pretty onerous task to checkpoint 
a random program.  For a proof attempt to checkpoint your X desktop,
the infrastructure is there to do it.  

Every application must be capable of checkpointing it for the cluster
batch scheduler to take advantage of it.

Example case.
[Preemption]
You start job 1, a compute intensive application that runs for 4 days,
on 100 cpus.  Your job is low priority.

In comes job2, a high priority job that runs for 4 hours and needs 256
cpus.

job1 is preempted.  With checkpoint support it can be saved and
restarted later.  Without checkpointing support it is simply killed.

[Migration]
Migration is needed for failing hardware or to get low priority jobs
out of the way onto less capable nodes that are going unused.

Or to restart a job that failed on other hardware.

Eric

Re: McVoy's Clusters (was Re: latest linus-2.5 BK broken)

[Kai Henningsen]

pashley@storm.ca (Sandy Harris)  wrote on 20.06.02 in <3D11F7B9.27C74922@storm.ca>:

> For large multi-processor systems, it isn't clear that those matter
> much. On single user systems I've tried , ps -ax | wc -l usually
> gives some number 50 < n < 100. For a multi-user general purpose

156 here right now, and I'd call that a light load. On a

processor	: 0
vendor_id	: AuthenticAMD
cpu family	: 5
model		: 8
model name	: AMD-K6(tm) 3D processor
stepping	: 12
cpu MHz		: 350.818

with 768 MB - not the fastest machine around.


MfG Kai