4.8. Fork-join


	Chapter 4. Programming Idioms
4.7. Parallel Matching	4.8. Fork-join	4.9. Sequential Fork-Join

One of the most common concurrent idioms is a fork-join: run two processes concurrently, and wait for a result from each one. This is very easy to express in Orc. Whenever we write a val declaration, the process computing that value runs in parallel with the rest of the program. So if we write two val declarations, and then form a tuple of their results, this performs a fork-join.

val x = F
val y = G
   # (x,y)

Fork-joins are a fundamental part of all Orc programs, since they are created by all nested expression translations. In fact, the fork-join we wrote above could be expressed even more simply as just:

(F,G)

4.8.1. Example: Machine initialization

In Orc programs, we often use fork-join and recursion together to dispatch many tasks in parallel and wait for all of them to complete. Suppose that given a machine m, calling m.init() initializes m and then publishes a signal when initialization is complete. The function initAll initializes a list of machines.

def initAll([]) = signal
def initAll(m:ms) = ( m.init() , initAll(ms) ) >> signal

For each machine, we fork-join the initialization of that machine (m.init()) with the initialization of the remaining machines (initAll(ms)). Thus, all of the initializations proceed in parallel, and the function returns a signal only when every machine in the list has completed its initialization.

Note that if some machine fails to initialize, and does not return a signal, then the initialization procedure will never complete.

4.8.2. Example: Simple parallel auction

We can also use a recursive fork-join to obtain a value, rather than just signaling completion. Suppose we have a list of bidders in a sealed-bid, single-round auction. Calling b.ask() requests a bid from the bidder b. We want to ask for one bid from each bidder, and then return the highest bid. The function auction performs such an auction for a list of bidders (max finds the maximum of its arguments):

def auction([]) = 0
def auction(b:bs) = max(b.ask(), auction(bs))

Note that all bidders are called simultaneously. Also note that if some bidder fails to return a bid, then the auction will never complete. Later we will see a different solution that addresses the issue of non-termination.

4.8.3. Example: Barrier synchronization

Consider an expression of the following form, where F and G are expressions and M and N are sites:

M()  >x>  F | N()  >y>  G

Suppose we would like to synchronize F and G, so that both start executing at the same time, after both M() and N() respond. This is easily done using the fork-join idiom. In the following, we assume that x does not occur free in G, nor y in F.

( M() , N() )  >(x,y)>  ( F | G )