On the Granularity of Divide-and-Conquer Parallelism

Hans-Wolfgang Loidl and Kevin Hammond
In Glasgow Workshop on Functional Programming 1995, Ullapool, Scotland, Jul. 8--10, 1995. Springer Verlag.

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.

  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

Available in: ps, ps.gz

GPH Papers | GPH