Question

What is spawn and sync in multithreaded? ( book clrs )

there is an example about Fibonacci number which use spawn and sync, I do not understand the part about parallelism, which I imagine that:

- Fib ( n - 1 ) would run along Fib (n) so that no recurrence would happen for Fib(n), Fib(n-1) and Fib(n-2).

Answer 1

The spawn and sync keywords specify logical parallelism, not "actual" parallelism. i.e. these keywords indicate which code may possibly execute in parallel, but what actually runs in parallel is determined by a scheduler, which maps the dynamically unfolding computation onto the available processors.

Ex: Fibonacci series

1   if n < 2:                     | thread A
2     return n                    | thread A
3   x = <strong>spawn</strong> Fibonacci(n-1)      | thread A
4   y = <strong>spawn</strong> Fibonacci(n-2)      | thread B
5   <strong>sync</strong>                          | thread C
6   return x + y                  | thread C

# this is a really bad algorithm, because it's
# exponential time.

The keyword spawn is the parallel analog of an ordinary subroutine call. Spawn before the subroutine call in line 3 indicates that the subprocedure Fibonacci(n-1) can execute in parallel with the procedure Fibonacci(n) itself. Unlike an ordinary function call, where the parent is not resumed until after its child returns, in the case of a spawn, the parent can continue to execute in parallel with the child. In this case, the parent goes on to spawn Fibonacci(n-2). In general, the parent can continue to spawn off children, producing a high degree of parallelism.

A procedure cannot safely use the return values of the children it has spawned until it executes a sync statement. If any of its children have not completed when it executes a sync, the procedure suspends and does not resume until all of its children have completed. When all of its children return, execution of the procedure resumes at the point immediately following the sync statement. In the Fibonacci example, the sync statement in line 5 is required before the return statement in line 6 to avoid the anomaly that would occur if x and y were summed before each had been computed.

A directed acyclic graph G = (V, E), where threads make up the set V of vertices, and each spawn and return statement makes up an edge in E. There are also continuation edges in E that exist between statements.

In Fibonacci example there are three threads: lines 1, 2, 3 make up the thread A, line 4 is thread B and lines 5, 6 are thread C.

Here is how a graph of Fibonacci(4) computation looks like: