Lazy Task Creation: A Technique for Increasing the Granularity of Parallel Programs

Abstract

Many parallel algorithms are naturally expressed at a fine level of granularity, often finer than MIMD parallel system can exploit efficiently. Most builders of parallel systems have looked to either the programmer or a parallelizing compiler to increase the granularity of such algorithms. In this paper we explore a third approach to the granularity problem by analyzing two strategies for combining parallel tasks dynamically at run-time.