Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!mailrus!purdue!gatech!hubcap!watro
From: watro@linus.UUCP (Ronald J. Watro)
Newsgroups: comp.parallel
Subject: Re: Optimistic / Speculative Programming
Keywords: Optimistic computation, parallelism, PARATRAN
Message-ID: <6820@hubcap.clemson.edu>
Date: 19 Oct 89 12:37:49 GMT
Sender: fpst@hubcap.clemson.edu
Lines: 56
Approved: parallel@hubcap.clemson.edu

In <6714@hubcap.clemson.edu>, Paul Wilson (wilson@carcoar.Stanford.EDU)
asked for (1) a comparison of ParaTran and the MITRE system for
parallel execution of sequential LISP code, and (2) information on
what the people at MITRE are currently up to.  I recently joined the
MITRE group doing this work, and my opinions on these questions are
given below.  My comments on ParaTran are based on reading the paper
by Tinker and Katz from the `88 Lisp and Functional Programming
Conference.  The MITRE system is described in a paper from OOPSLA88.

(1) Certainly the basic ideas of ParaTran and the MITRE system are
exactly the same.  Both systems create parallel execution using
futures and Time Warp with timestamps that are generated by the system
to reflect sequential processing order.  The systems differ in the
details of how they are constructed.  MITRE considers object-oriented
programs in Common Lisp with Flavors, and uses the programmer's
objects as the parallel tasks.  ParaTran takes Scheme code and does a
compile-time analysis to identify code segments that will form
parallel tasks.

The design of the MITRE system is object-oriented (futures are
objects) and generally aimed at a loosely-coupled, message-passing
MIMD machine.  We have run the system on a 32-node Symult S2010 and a
16-node Intel iPSC/2.  While neither MITRE nor ParaTran is tied to a
specific architecture, the ParaTran paper uses a shared-memory model
for ease of exposition, and mentions the BBN Butterfly as the proposed
target for implementation.


(2) Since the OOPSLA88 paper, work at MITRE has continued in several
directions:
    a) Fault Tolerance - A fault-tolerant version of the system was
       designed, implemented, and is currently being tested in a 
       distributed system and in a single processor simulation.
    b) Formal Analysis - We attempted to give a correctness proof for
       the system.  So far, we have sketched a proof for "partial
       correctness."  Termination is a more difficult issue that we
       are working on.  We want to extend the formal analysis to
       include fault tolerance.
    c) Implementation - As mentioned above, we have implemented the
       basic system on Symult and Intel machines.  Lazy cancellation
       was recently added to the system.
    d) Performance Studies - This work is just beginning.









-- 
Dr. Ronald J. Watro   The MITRE Corporation, MS A129, Burlington RD,
                      Bedford, MA 01730  USA      617-271-7648
InterNet:   rjwatro@mitre.org
UUCP:   ...{decvax,utzoo,philabs,security,allegra,genrad}!linus!watro