5,323
edits
Parallel Algorithms: Difference between revisions
→Compaction of an n^2 array with \leq n elements in O(\log n) time
| Line 680: | Line 680: | ||
* Perform one compaction on the size of each subarray | * Perform one compaction on the size of each subarray | ||
* Compact all elements using (total size of prev subarrays + position in current subarray) | * Compact all elements using (total size of prev subarrays + position in current subarray) | ||
The benefit of this segmented compaction/prefix sum is that if you only do each segment once in an iterative algorithm such as parallel BFS, | |||
you can get <math>O(n^2)</math> or <math>O(m)</math> work. | |||
==Hardware/Architecture== | ==Hardware/Architecture== | ||