Our SMP cluster discussion was quite a bit of fun, very challenging!
I still stand by my assessment:
> 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.
See you at Ottawa!
Thanx, Paul
> Larry McVoy <lm@bitmover.com>
> Sent by: linux-kernel-owner@vger.kernel.org
> 06/19/2002 10:24 PM
>
> > 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
-
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/