Community
cancel
Showing results for 
Search instead for 
Did you mean: 
balaji_ram
Beginner
34 Views

Help in understanding parallel_scan

Hello,

I have the read the Intel TBB documentation regarding parallel_scan.
But I still havent figured out how exactly this works. For me it seems quite impossible to parallelize
an alogorithm that depends on the result of the previous computation (for ex : fibonacci series).
But parallel_scan seems to be useful in exactly such scenarios.

Can you please guide me some explanation (or) lead me to some link which can give me a clear picture of how parallelization is done in suchalgorithms ?

Thanks very much.

Balaji Ram.
0 Kudos
2 Replies
RafSchietekat
Black Belt
34 Views

Fibonacci is probably a bad example because it can be computed in wildly disparate ways, with a serial loop somewhere in-between as far as efficiency goes, but parallel_scan does not seem to be applicable, nor would it necessarily be very efficient compared to what a bit of mathematics can do for you (see the Tutorial about that). The first example I would think of instead is integral approximation: conceptually, each subgroup's contribution can be independently computed (concurrency), and then the results can be redistributed (alas, some serial dependencies) and locally merged (more concurrency).

I see that the word "parallel_scan" does not occur in "Tutorial (Open Source).pdf", current revision 1.13, but it does in "Reference (Open Source).pdf", current revision also 1.13, and there it has been documented rather nicely, I would say (see "Problems using parallel_scan" about that).

balaji_ram
Beginner
34 Views

Quoting - Raf Schietekat
Fibonacci is probably a bad example because it can be computed in wildly disparate ways, with a serial loop somewhere in-between as far as efficiency goes, but parallel_scan does not seem to be applicable, nor would it necessarily be very efficient compared to what a bit of mathematics can do for you (see the Tutorial about that). The first example I would think of instead is integral approximation: conceptually, each subgroup's contribution can be independently computed (concurrency), and then the results can be redistributed (alas, some serial dependencies) and locally merged (more concurrency).

I see that the word "parallel_scan" does not occur in "Tutorial (Open Source).pdf", current revision 1.13, but it does in "Reference (Open Source).pdf", current revision also 1.13, and there it has been documented rather nicely, I would say (see "Problems using parallel_scan" about that).


Thanks very much. I also have the parallel_scan.pdf by Arch Robison from the above link. This will surely help.
Reply