Electronic workshops in computing · 1995 · 30 citations · 5 references
ComputingComputer ScienceAlgorithmsParallel AlgorithmsParallel ComputingData ParallelismParallel Algorithm DesignParallel ComputationParallel Performance AnalysisParallel Programming ModelsParallel Runtime SystemsGranularityGranularity ControlParallel Divide And ConquerParallel Divide-and-conquer AlgorithmsParallel Runtime AnalysisParallelism GranularityPerformance OverheadThread Creation
This paper studies the runtime behaviour of various parallel divide-and-conquer algorithms written in a non-strict functional language, when three common granularity control mechanisms are used: a simple cut-off, a priority thread creation and a priority scheduling mechanism. These mechanisms use granularity information that is currently provided via annotations to improve the performance of the parallel programs. The programs we examine are several variants of a generic divide-and-conquer program, an unbalanced divide-and-conquer algorithm and a parallel determinant computation. Our results indicate that for balanced computation trees a simple, low-overhead mechanism performs well whereas the more complex mechanisms offer further improvements for unbalanced computation trees.
5