3 ms·

Uh, Fibonacci is not embarrassingly parallel. That term has a precise technical meaning; it is that the parallel processes have no dependencies and require no c

Uh, Fibonacci is not embarrassingly parallel. That term has a precise technical meaning; it is that the parallel processes have no dependencies and require no communication. Fibonacci computations depend upon prior results, which is why it is a poor fit for parallelization in general. While, yes, it is possible to fork on every recurrence and join to wait for the result, the overhead of that is gigantic and dwarfs any benefits.

deleted 6y ago
[deleted]
chrisseaton 6y ago
> Fibonacci is not embarrassingly parallel Just take a look at the code we’re talking about yourself. See the operator a + b between the two recursions? There are zero data or control dependencies between a and b. They can be perfectly distributed, which is why it’s been used as an example here. Also read the note directed at the 'algorithms police' here https://cilk.mit.edu/programming/ https://cilk.mit.edu/programming/ which I think will pre-empt the point you're going to make next.
- spenczar5 6y ago
  Okay, so let's look at fib(5). It starts two tasks, fib(4) and fib(3). It waits for them to complete. There are now 3 tasks, but 2 are running. fib(4) starts two tasks, fib(3) (second edition) and fib(2). It waits for them to complete. There are now 5 tasks (fib(5), fib(4), fib(3), fib(3), and fib(2)), and 3 are running (fib(3), fib(3), and fib(2)). fib(3) (the first one) starts two tasks, fib(2) and fib(1). It waits for them to complete. 7 tasks, 4 are running. fib(3) (the other one) starts fib(2) and fib(1). It waits for them to complete. 9 tasks, 5 are running. We keep going like this. Notice how many tasks are not running at any given time because they depend upon other tasks to complete. This is nowhere near an embarrassingly parallel problem. For an actual embarrassingly parallel problem, consider something like "this 1GB slice of memory contains a continuous sequence of 64-bit floating point numbers. Please square each number in place." This can be divided among any number of processes trivially, with actually zero coordination. There's also "nearly embarassingly parallel," where a minor amount of coordination is required in a final step. You can parallelize "compute the max of an array of integers", for example, by splitting it into N chunks, having each one compute their own max, and then taking the max of the maxes. But Fibonacci is nowhere close to those.

deleted 6y ago

[deleted]

chrisseaton 6y ago

> Fibonacci is not embarrassingly parallel Just take a look at the code we’re talking about yourself. See the operator a + b between the two recursions? There are zero data or control dependencies between a and b. They can be perfectly distributed, which is why it’s been used as an example here. Also read the note directed at the 'algorithms police' here https://cilk.mit.edu/programming/ https://cilk.mit.edu/programming/ which I think will pre-empt the point you're going to make next.

spenczar5 6y ago
Okay, so let's look at fib(5). It starts two tasks, fib(4) and fib(3). It waits for them to complete. There are now 3 tasks, but 2 are running. fib(4) starts two tasks, fib(3) (second edition) and fib(2). It waits for them to complete. There are now 5 tasks (fib(5), fib(4), fib(3), fib(3), and fib(2)), and 3 are running (fib(3), fib(3), and fib(2)). fib(3) (the first one) starts two tasks, fib(2) and fib(1). It waits for them to complete. 7 tasks, 4 are running. fib(3) (the other one) starts fib(2) and fib(1). It waits for them to complete. 9 tasks, 5 are running. We keep going like this. Notice how many tasks are not running at any given time because they depend upon other tasks to complete. This is nowhere near an embarrassingly parallel problem. For an actual embarrassingly parallel problem, consider something like "this 1GB slice of memory contains a continuous sequence of 64-bit floating point numbers. Please square each number in place." This can be divided among any number of processes trivially, with actually zero coordination. There's also "nearly embarassingly parallel," where a minor amount of coordination is required in a final step. You can parallelize "compute the max of an array of integers", for example, by splitting it into N chunks, having each one compute their own max, and then taking the max of the maxes. But Fibonacci is nowhere close to those.