Path: utzoo!attcan!uunet!ncrlnk!ncrcae!hubcap!khb
From: khb@Sun.COM (Keith Bierman - Sun Tactical Engineering)
Newsgroups: comp.parallel
Subject: Re: fine-grained and/or multiway optimi
Message-ID: <3485@hubcap.UUCP>
Date: 9 Nov 88 13:01:09 GMT
Sender: fpst@hubcap.UUCP
Lines: 96
Approved: parallel@hubcap.clemson.edu

In article <3465@hubcap.UUCP> wilson@uicbert.eecs.uic.edu writes:
>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?

For very tightly coupled processors it might not make much sense. Very
optimistic systems will probably be loosely coupled.

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

TimeWarp the first operating system with virtual time. Contact Brian
Beckman at JPL, or look into back issues of CACM; the idea was
formulated by a UCLA professor (still there, I think), the first
hypercube implementation was done by Brian and some folks reporting to
him (mostly him, I think). There are others working on this for
networks and such. At one time there was a Mac simulator, a Sun
network implementation and a JPL Mark II hypercube implementation. I
don't know the projects current status.

>
>   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.

These don't always make the rewrite easier. There was a paper
presented at a SIGMETRICS or two ago which purported to prove that
parallelism didn't work. The fellow worked for IBM, and strangely
enough the ruling committee really like the paper (gave it an honor).
Brian's results are extremely encouraging (as of a couple of years
ago). They built discrete simulations which worked. Got the speedup,
not infinite time loops. What more can we ask of a research project ?
>
>   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.)

Cydra 5 directed dataflow. Cydrome is fast becoming history but the
machine was a VLIW with lot's of attractive features (and it worked).
But it takes more to be a sucessful company.

>
>   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)?

TimeWarp is (in principle) object based, and built upon message
passing. So, IP, the programmer shouldn't know about the stack(s) etc.
Current reality is probably more primative, but it's research.
>
>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.

Good start.
>
>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.

Woops, just got this far. If you know about TW, why the questions ?
>
>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.
>

The fundamental practial engineering questions are: what is the cost of
doing extra work ? what is the probability of success (i.e. doing
useful work) . For a tightly coupled system there are typically lots
of ways to use pessimitic scheduling and rely on other ways to get
speed (until you hit Cray speeds). Loosely coupled arrays seem more
amenable to these techniques.



Keith H. Bierman
It's Not My Fault ---- I Voted for Bill & Opus