Control of parallel task granularity by throttling decomposition

This paper introduces a new mechanism which performs lazy task creation in a novel way for the exposure of large grain parallelism. In lazy task creation, all new-born tasks are provisionally inlined and parallelism is extracted from the inlined information later on demand. Large grain parallelism is achieved by executing the inlined tasks in the current thread unless a new task is demanded. However, the new scheme leaves a self-divisible task called seed instead inlining the task and let further task demands be satisfied by sprouting new tasks from the seed rather than retrospectively reversing the inlining decision of the task. In the scheme, decomposition itself is throttled rather than just the extraction of a task. The scheme makes the serial section clearly separated from the parallel section in an evaluation tree, and this allows the serial section to adopt a sequential algorithm. The performance improvement is significant in divide-and-conquer applications by adoption of sequential algorithms