Path: utzoo!utgpu!attcan!uunet!lll-winken!lll-tis!helios.ee.lbl.gov!pasteur!agate!bionet!apple!bloom-beacon!tut.cis.ohio-state.edu!ukma!gatech!hubcap!wilson
From: wilson@uicbert.eecs.uic.edu
Newsgroups: comp.parallel
Subject: fine-grained and/or multiway optimi
Message-ID: <3466@hubcap.UUCP>
Date: 7 Nov 88 19:04:35 GMT
Sender: fpst@hubcap.UUCP
Lines: 53
Approved: parallel@hubcap.clemson.edu

I am looking for pointers to research on optimistic computation,
especially fine-grained optimism and multiway optimism.

My impression is that most of the work in optimistic parallelism is
either very loosely-coupled (e.g., distributed simulation) or massively
parallel (e.g., connectionist).  There's also some optimism 
in the pipelining of processors.

Questions:

   1.  Is anybody doing tightly-coupled multiprocessor optimism?  If not,
       is there some reason for it?

   2.  Are there any explicitly optimistic programming systems, with
       language constructs that specify/allow optimistic execution?

   3.  How promising are optimistic techniques, really?  They would
       *seem*, to a nonexpert like me, to be the only way around
       Amdahl's law without redesigning all of our algorithms to
       have tremendous parallelism, which is difficult.

   4.  Is anybody doing multiway optimism, for example computing
       all possible branches of a conditional in parallel with
       evaluation of the condition?  (When you finally know the
       value of the condition, you just keep the appropriate
       consequent, already computed, and discard the others.)

   5.  Do any optimistic systems let you play with a general heap,
       or do they impose major restrictions (like all data being
       allocated on a stack, or requiring that the compiler be
       able to determine statically when something will become
       garbage)?

My own interest in this stems partly from the fact that I have devised a
couple of checkpointing and recovery mechanisms that efficiently checkpoint
heaps.  One of them is good for allowing reversion to all past states, with
the cost being quite reasonable in space and time, but smallest for recently-
accessed states.  The other supports having several "current" states, with
each being an efficient virtual copy of a parent state.

The former system should allow optimistic systems like Time Warp to use a
general heap efficiently, while the latter should allow multiway, fine-grained
optimism on multiprocessors.

I actually came up with these things for quite different reasons, but I am
curious how applicable they are to optimistic systems.  Any opinions on
these issues would be welcome.

Thanks prematurely,

Paul R. Wilson                         
Human-Computer Interaction Laboratory
U. of Illin. at C. EECS Dept. (M/C 154)   wilson%uicbert@uxc.cso.uiuc.edu
Box 4348   Chicago,IL 60680