wilson@uicbert.eecs.uic.edu (11/11/88)
In an earlier posting I asked if anyone was doing work on fine-grained
or multiway optimistic computation. Nobody answered who knew of such
things, but a couple of people asked what optimistic computation *is*.
I guess I should clarify this.
Optimistic computation is the premature computation of things that
may or may not turn out to be useful. This can increase parallelism
by allowing you to execute things without waiting to be *sure* you're
computing the right thing.
Normal approaches to parallelism may be viewed as pessimistic; if
process A may affect process B at some point in the code, process
B has to stop and wait if it gets to that point first, to find out
what effect A is going to have on it.
With optimistic computation, B can make a *guess* as to what A will
do, and go on from there. If A later does as B expected, B has
gotten ahead of the game by not having to wait. If A does something
else, B has to roll back to its state at the point of interaction
and try again.
This approach appears to work well for applications, like distributed
simulations or financial transaction mechanisms, in which most
possible interactions do not in fact happen. For example, an automated
teller machine system may total up activities on your account under
the assumption that you are not at that same time using one of the
teller machines. Since you don't spend most of your time at teller
machines, it will be able to process your account just fine, usually.
If you happen to make a transaction that screws up its calculations,
it will have to go back and re-do the computation.
The seriously nifty thing about optimistic computation is that it allows
you to exploit parallelism that "doesn't exist" by assuming that on
average you guess fairly well.
Suppose you have a 1000-processor computer running a program that
can mostly be parallelized pretty well. Unfortunately, this program
has some sections that only have *real* parallelism of about 5. Those
sections will tend to dominate the performance of your program, because
995 of your processors will sit waiting while you execute them. No
matter how fast you get the rest of the program to go, those processors
will sit idle while 5 processors grind through the not-very-parallel
section of the program. Throwing more processors at the problem will
only make the very parallel parts of the program go faster, but the
less parallel parts will take the same time; this acts as a brick
wall that limits your performance.
The only two ways I know of to speed up these not-very-parallel
bottlenecks are 1) rewrite the program using a more parallelizable
algorithm, and 2) use optimistic computation to expand the bottlenecks.
In the example, you might allocate some of your processors to computing
all possible paths through the bottleneck *before* you get to it.
Then you just pick the appropriate answer on the basis of the state
when you get there.
Suppose the bottleneck contains this conditional:
if A then B else C
The usual way to compute this is to compute A, and then compute either
B or C.
The optimistic way of computing it would be to compute A and B and C
all at the same time. When you've finished computing A, you know
whether to keep the results of B or of C. You discard the other.
Of course some computation will be wasted. But if you're widening
a critical bottleneck, it may be well worth it. Better to waste
a few processors sometimes than to keep a whole bunch of processors
waiting.
(A similar way of computing conditionals is used on SIMD machines,
I hear, at a very fine grain. I'm looking for something a little
larger grained. Optimistic computation is also used in distributed
systems, but I'm looking for something in between. My impression
now is that *nobody* is doing medium-grained optimism of a MIMD
sort. If this is is a mistaken impression, someone PLEASE correct
me. I am also under the impression that large-grained optimisim
is generally depth-first, where at each juncture you pick ONE
most likely outcome and compute it, rather than several
possible outcomes simultaneously.)
I am interested in anybody doing medium-grained or multiway
optimistic systems. I am especially interested in *explicit*
optimisim, as well as implicit optimism. It seems that nobody
has come up with programming language constructs that let you
specify optimism (like an optimistic IF that behaves as described
above). The advantage of this is that you could write parallel
but deterministic programs using it. (On some runs, you may or
may not finish computing B or C, but you'll always finish computing
-- and keep the results of -- the one specified by the outcome of
A). This is similar in spirit to what Halsted et al. are doing
with speculative computation, but with the advantages of deterministic
outcomes. (easier to debug, verify, etc.)
Any comments?
-- Paul
Paul R. Wilson
Electronic Mind Control Lab*
U. of Illin. at C. EECS Dept. (M/C 154) wilson%uicbert@uxc.cso.uiuc.edu
Box 4348 Chicago,IL 60680 (* a.k.a. Human-Computer Interaction Laboratory)max@polya.stanford.edu (Max Hailperin) (11/14/88)
Just to try to illucidate the question of optimistic/speculative
concurrency a bit, let me say that they are frequently distinguished
from one another (though they are indeed intimately related):
OPTIMISTIC means you ignore synchonization constraints, while keeping
an eye out for cases where this gets you in trouble. For example, you
might read a variable without waiting to see if anyone at an earlier
logical time might write it. When the write is done, the writer
checks whether an invalid read did indeed slip in, and if so rolls
back the reader. All the work should be useful, except that it may be
computing using the wrong values. This is used in some distributed
database systems. It also is the essense of "Time Warp" discrete
event simulation. It has been proposed for lisp evaluation by Morris
Katz ("ParaTran: A Transparent, Transaction Based Runtime Mechanism
for Parallel Execution of Scheme," MIT EECS Masters Thesis, June 1986)
and also by Tom Knight ("An Architecture for Mostly Functional
Languages," Proceedings of the 1986 ACM Symposium on Lisp and
Functional Programming, pp. 105-112).
SPECULATIVE concurrency means going down multiple branches of a
conditional while you figure out which one you really want. This is
also allied to what the parallel logic programming community calls
"OR-parallelism," and with the notions of "competative concurrency"
and "sponsorship" in the actors field. Both of these generalize on
it. For example, suppose you want to evaluate the OR (or AND) of two
expressions: you can start evaluating them concurrently, and if either
returns TRUE (respectively FALSE), you can kill the other off. (This
is sort of like the case with a conditional, only more symmetric.)
I hope this pedanticness benefited someone; I'm sure many of you know
this all as well as I do (or better) -- I was aiming this at those who don't.bjornl@tds.kth.se (Bj|rn Lisper) (11/21/88)
In article <3508@hubcap.UUCP> wilson@uicbert.eecs.uic.edu writes: .... >Optimistic computation is the premature computation of things that >may or may not turn out to be useful. This can increase parallelism >by allowing you to execute things without waiting to be *sure* you're >computing the right thing. .... When reading this posting I came to think of a funny example of optimistic parallelism. The example is Swedish teller machines: Most teller machines work this way: first they ask you for your code. Then they ask you for the amount of withdrawal. Then they count the number of bills to give you. Finally, if the above steps are successfully passed, they give you the money. This is a strictly serial execution pattern. A Swedish teller machine instead does it this way: first it asks you not for your code, but for the amount of withdrawal. As soon as you provide the answer it will start counting bills. THEN it asks you for your code. While you're typing the code it will simultaneously count bills. This is optimistic parallelism, since there is a possibility that you will fail to provide the proper code. When the bills are counted and you have provided the right code, you will get your money. If, for some reason, you would fail to type the correct code, the machine will just drop the money in a box instead of giving it to you. This way of doing things makes Swedish teller machines faster, since the most time-consuming part of the cycle is counting bills and therefore this process should be started as soon as possible. Most users do succeed to provide the proper code. Therefore the failures are few and optimistic parallelism works very well. Just a funny example of everyday optimistic parallelism.... Bjorn Lisper