Assuming you have an infinite number of processors, to compute the scan of this array:
Every processor in parallel adds two nodes. The first two elements are now complete.
The first four elements are now complete.
The first eight elements are now complete
etc.
If we have p processors instead of an infinite number, we divide the work w as:
$w / p$
$w = O(N \lg N)$
So we have each processor computing $(N/p) \lg N$
This comment was marked helpful 0 times.
Assuming you have an infinite number of processors, to compute the scan of this array:
Every processor in parallel adds two nodes. The first two elements are now complete.
The first four elements are now complete.
The first eight elements are now complete
etc.
If we have p processors instead of an infinite number, we divide the work w as:
$w / p$
$w = O(N \lg N)$
So we have each processor computing $(N/p) \lg N$
This comment was marked helpful 0 times.