Path: utzoo!utgpu!watmath!clyde!att!osu-cis!tut.cis.ohio-state.edu!ukma!gatech!hubcap!wilson From: wilson@uicbert.eecs.uic.edu Newsgroups: comp.parallel Subject: optimistic computation: what and wh Message-ID: <3508@hubcap.UUCP> Date: 11 Nov 88 12:56:11 GMT Sender: fpst@hubcap.UUCP Lines: 103 Approved: parallel@hubcap.clemson.edu 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)