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.
@InProceedings{gph-div-conc,
author = {Hans-Wolfgang Loidl and Kevin Hammond},
title = {On the Granularity of Divide-and-Conquer Parallelism},
booktitle = {Proceedings of the Glasgow Workshop on Functional Programming},
year = {1995},
address = {Ullapool, Scotland},
month = jul
}