On the Granularity of Divide-and-Conquer Parallelism

Abstract

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.

Contributors

Hans-Wolfgang Loidl

Kevin Hammond

Conference

Publication date: July 1995

Publication date (Print): July 1995

Pages: 1-10

Affiliations

Department of Computing Science, University of Glasgow

Glasgow, Scotland, U.K.

Division of Computer Science, University of St. Andrews

St. Andrews, Scotland, U.K.

Article

DOI: 10.14236/ewic/FP1995.13

Copyright statement: © Hans-Wolfgang Loidl et al. Published by BCS Learning and Development Ltd. Proceedings of the 1995 Glasgow Workshop on Functional Programming, Ullapool, Scotland

License:

This work is licensed under a Creative Commons Attribution 4.0 Unported License. To view a copy of this license, visit http://creativecommons.org/licenses/by/4.0/

Conference name: Proceedings of the 1995 Glasgow Workshop on Functional Programming

Conference acronym: FP

Conference number:

Conference location: Ullapool, Scotland

Conference date: 10-12 July 1995

Conference sponsor: Electronic Workshops in Computing (eWiC)

Conference theme: Functional Programming

Product

Product Information: 1477-9358BCS Learning & Development

Self URI (article page): https://www.scienceopen.com/hosted-document?doi=10.14236/ewic/FP1995.13

Self URI (journal page): https://ewic.bcs.org/

Categories

Series title: Electronic Workshops in Computing