Home → Magazine Archive → October 2016 (Vol. 59, No. 10) → Technical Perspective: The Power of Parallelizing... → Abstract

Technical Perspective: The Power of Parallelizing Computations

By James Larus

Communications of the ACM, Vol. 59 No. 10, Page 84

As computers become parallel, performance-challenged programs must also become parallel. For some algorithms, this is not a great challenge as the underlying problem divides naturally into independent pieces that can be computed concurrently. Other problems are not so lucky. Their constituent computations are tightly interdependent, and a parallel implementation requires considerable coordination and synchronization and may still perform poorly.

Recursive algorithms fall into this category. The recursive call is a dependence between the calculations in successive function invocations, which makes it difficult to overlap their executions significantly. There is no general formula for transforming a recursive function for parallel execution. It is necessary to understand the intrinsic structure of the underlying computation and to find a way to preserve the essential relationships while running in parallel.


No entries found