Path: utzoo!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!samsung!emory!hubcap!huff
From: huff@svax.cs.cornell.edu (Richard Huff)
Newsgroups: comp.parallel
Subject: RE: Parallel Paradigms for BBN Butterfly
Message-ID: <8130@hubcap.clemson.edu>
Date: 22 Feb 90 21:29:31 GMT
Sender: fpst@hubcap.clemson.edu
Lines: 83
Approved: parallel@hubcap.clemson.edu

About a week ago I sent out a request for information on alternative
parallel processing paradigms/packages for the BBN Butterfly.  (That is,
alternatives to the Uniform System.)  Here is a summary of what I learned.

*******************************************************************************

From: reiher@onyx.Jpl.Nasa.Gov (Peter Reiher)

The Time Warp Operating System runs on the Butterfly, currently only under
Chrysalis.  It runs discrete event simulations in parallel, though you could
probably use it for a few other things, if they fit the paradigm.  Basically,
you have to be able to decompose your problem into subcomponents (objects) that 
communicate only via messages, and you have to be able to assign a timestamp
to each event performed (messages cause events) indicating the event's 
relative order in the simulation.  Time Warp then runs all objects on a node
independently of all other nodes' objects.  This can cause out-of-order
processing, in which case Time Warp uses rollback and message cancellation
to automatically correct its mistake.

TWOS can be gotten through NASA's Cosmic software distribution system, but
we were recently told that they intend to charge $1500 for a copy, which doesn't
seem reasonable to us.  I'm not sure if we can get them to lower it.  The
price does include source code.

The most important papers are

"Virtual Time", David Jefferson, ACM Trans on Prog. Lang. & Systems, Vol. 7,
No. 3, (July 1985).

and

"Distributed Simulation and the Time Warp Operating System", Jefferson et.
al., ACM Operating Systems Review, Vol. 20, No. 4, 1987.

The idea is basically to synchronize solely by rollback and message
cancellation, never by blocking.  Each node independently chooses which of
its local objects to run next, basing its decision on which local object
has the message with the earliest timestamp.  Other nodes may simulataneously
be choosing work with an earlier timestamp, work that may produce further
messages to be sent to this node.  Those messages could have earlier 
timestamps than the message this node just chose, in which case the work
about to be done will eventually be rolled back, and all of its effects
undone.

It is an unusual way to do things, but, with suitable constraints, it works,
and works quite well.

*******************************************************************************

From: mrg@Princeton.EDU (Mark Greenstreet)

You might want to contact Robert Fowler at the University of Rochester.
They have an operating system called "PLATINUM" that deals with object
migration to lower memory latency.  See
    "The Implementation of a Coherent Memory Abstraction on a NUMA
     Multiprocessor: Experiences with PLATINUM", Alan L. Cox and Robert
     J. Fowler.  University of Rochester Deparatment of Computer Science
     Technical report 263, 1989.

*******************************************************************************

Several people mentioned the C Threads library available from Ohio State
University.  You can get the library from tut.cis.ohio-state.edu in the
/pub/Threads directory.  The directory contains source code for both
Chrysalis and Mach 1000 versions of the Butterfly, as well as some man
pages.  In addition, pick up files 1.Z through 5.Z.  When they are
uncompressed and concatenated, you will have the postscript source to a
report for last year's Butterfly Users Group.

The library was written by Yiannis Samiotakis, who then wrote a Master's
Thesis on the experience, "A Thread Library for a Non Uniform Memory
Acess Multiprocessor", finished in 1989.

Thanks to:
	george@cis.ohio-state.edu (George M. Jones)
	slim@cosimo.osgp.osc.edu (Scott Whitman)
	john_r_mudd@cis.ohio-state.edu

*******************************************************************************

Thanks for everyone's help.

huff@svax.cs.cornell.edu (Richard Huff)