byu@csri.toronto.edu (Benjamin Yu) (10/05/89)
I would appreciate information in current research on optimistic /
speculative programming. I know of some "old" articles such as
Jefferson's Time Warp (Toplas July 1985), Halstead's Futures but
haven't been able to track down more current work. Any pointers
will be much appreciated!
Benjamin Yu
University of Toronto CSNET, UUCP, BITNET:
Department of Computer Science byu@csri.toronto.edu
Toronto, Ontario Canada M5S 1A4 {uunet,watmath}!csri.utoronto.edu!byu
(o) (416) 978 - 4299 (h) (416) 470 - 8206dor@lanl.gov (David O. Rich) (10/05/89)
>From article <6672@hubcap.clemson.edu>, by byu@csri.toronto.edu (Benjamin Yu): > I would appreciate information in current research on optimistic / > speculative programming. I know of some "old" articles such as > Jefferson's Time Warp (Toplas July 1985), Halstead's Futures but > haven't been able to track down more current work. Any pointers > will be much appreciated! > Richard Fujimoto "The Virtual Time Machine" Technical Report UUCS-88-021 University of Utah December 1988 (also published in an ACM journal, 1989... I can't seem to find that reference though) Pete Tinker (pat@risc.com) Rockwell International Science Center "Task Scheduling for General Rollback Computing" ICPP 1988 (I think?) Pete Tinker and Morry Katz Rockwell International Science Center "Parallel Execution of Sequential Scheme with ParaTran" 1988 Lisp and Functional Programming Conference --Dave
liny@cs.washington.edu (Yi-Bing Lin) (10/09/89)
People at University of Washington have done some work about Time Warp Simulation. You may request the following TRs via E-mail: tech-report@june.cs.washington.edu TR 89-07-05. Yi-Bing Lin and Ed. Lazowska Optimality Considerations of Time Warp Parallel Simulation TR 89-09-04. Yi-Bing Lin and Ed. Lazowska The Optimal Checkpoint Interval in Time Warp Parallel Simulation TR 89-09-06. Yi-Bing Lin and Ed. Lazowska Comparing Synchronization Protocols for Parallel Logic-Level Simulation TR 89-09-07. Yi-Bing Lin and Ed. Lazowska A Study of Time Warp Rollback Mechanisms (In preparation) Yi-Bing Lin and Ed. Lazowska Determining the Global Virtual Time in Distributed Simulation Jason (Yi-Bing Lin)
wilson@carcoar.Stanford.EDU (Paul Wilson) (10/10/89)
I just came across another one: "An Execution Model for Distributed
Object-Oriented Computation," by Edward H. Bensley, Thomas J. Brando,
and Myra Jean Prelle of the MITRE Corporation, in the OOPSLA '88
proceedings (Special issue of SIGPLAN Notices, vol 23, no 11, Nov. 88,
pp. 316-322.
My first impression is that this looks a whole lot like Morry Katz'
Paratran system. It uses the program call graph to generate virtual
timestamps using an infinite-precision ("littlenums?") subdivision
mechanism.
Anybody know both of these systems and care to comment? Has anybody
heard from these people since and know what they're up to now?
By the way, in my MS thesis, I described (but haven't implemented)
a system that supports the same abstraction as Jonathan Smith's
"Multiple Worlds," only I call it "Alternate Universes." My implementation
ideas are quite different, though, supporting finer-grained parallelism
and being less sensitive to poor locality. I also discuss garbage
collection across multiple worlds/universes/whatevers. On the other
hand, mine incurs a certain amount of continual overhead on stock
hardware.
-- Paul
Paul R. Wilson
Software Systems Laboratory lab ph.: (312) 996-9216
U. of Illin. at C. EECS Dept. (M/C 154) wilson@carcoar.stanford.edu
Box 4348 Chicago,IL 60680 watro@linus.UUCP (Ronald J. Watro) (10/19/89)
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