libes@cme-durer.ARPA (Don Libes) (07/14/88)
I am rendering an algorithm into C that was originally written using Dijkstra's guarded commands. I am wondering if there is a nice way of writing the C so that the algorithm preserves the possibility for parallel execution - should such a processor appear on my desk in the near future. Indeed, I've been specifically told that there is a high likelihood that the code will be moved to a parallel environment. Which one, however, is unknown at this time. By "possibility", I mean "with minimal code rewriting". For example, a simplistic way is to ignore the potential for parallel execution and just fixedly serialize the statements. But this is obviously not in the spirit of what I am asking. I am prepared to accept that this is entirely out of the realm of C. After all, it seems as though many people are barely able to come to terms with the idea of a compiler rearranging operands in an expression. Now, I'm asking about rearranging statements in a subroutine. Yes, I realize this is a very difficult problem. For example, parallel execution of guards containing functions with side-effects would be awful. (Fortunately, I don't believe I have to worry about that particular problem.) Anyway, I have never heard of any such conventions. Even if they are just personal (i.e., used only by yourself), I would be interested in hearing about them. Pointers to literature gratefully accepted, also. Don Libes cme-durer.arpa ...!uunet!cme-durer!libes
ark@alice.UUCP (07/15/88)
In article <515@muffin.cme-durer.ARPA>, libes@cme-durer.UUCP writes: > I am rendering an algorithm into C that was originally written using > Dijkstra's guarded commands. I am wondering if there is a nice way of > writing the C so that the algorithm preserves the possibility for > parallel execution Dijkstra's guarded commands don't really allow for parallel execution. If you say if C1 -> S1 | C2 -> S2 | C3 -> S3 fi then exactly one of S1, S2, and S3 will be executed (or the program will abort). Where's the parallelism?
libes@cme-durer.ARPA (Don Libes) (07/17/88)
In article <8044@alice.UUCP>, ark@alice.UUCP writes: > Dijkstra's guarded commands don't really allow for parallel > [ example deleted ] > Where's the parallelism? You can execute the guards in parallel, as long as they don't have side-effects. I noted this in the last paragraph of my posting, but I guess you missed it. I'll repeat it: In article <515@muffin.cme-durer.ARPA>, I wrote: > parallel execution of guards containing functions with side-effects > would be awful. (Fortunately, I don't believe I have to worry about > that particular problem.) In fact, I have never seen anyone using guards WITH side-effects. I think it is commonly understood that one of the benefits of Dijkstra's guarded commands is that the obvious nondeterminism makes it easy to speed up on a parallel machine. I have already received several elegant solutions to my question. I will post the best shortly. Don Libes cme-durer.arpa ...!uunet!cme-durer!libes
smryan@garth.UUCP (Steven Ryan) (07/17/88)
>> I am wondering if there is a nice way of >> writing the C so that the algorithm preserves the possibility for >> parallel execution > > if C1 -> S1 > | C2 -> S2 > | C3 -> S3 > fi > >then exactly one of S1, S2, and S3 will be executed (or the >program will abort). Where's the parallelism? Underconstraining strikes again. The three guards C1, C2, and C3 are evaluated nondeterministically. They can be evaluated in order, in reverse order, in any other permutation. The individual instructions can be intermingled, in parallel on a segmented cpu. Also, all three guards can be sent to three parallel processors. If at least one guard is true, then any one true guard can be selected. The parallelism is neither required nor forbidden. The programmer must avoid interfering side effects and let the compiler make what it thinks is best. In answer to the original question, you can't avoid overconstraining the guard evaluations in statements: C only supports a deterministic statement order. [You decide if that's good or bad.] I don't know about declarations: I don't know if initialisers are serialised or collateral. sm ryan