A Unified Scheduler for Recursive and Task Dataflow Parallelism

Research output: Chapter in Book/Report/Conference proceedingConference contribution

27 Citations (Scopus)
300 Downloads (Pure)

Abstract

Task dataflow languages simplify the specification of parallel programs by dynamically detecting and enforcing dependencies between tasks. These languages are, however, often restricted to a single level of parallelism. This language design is reflected in the runtime system, where a master thread explicitly generates a task graph and worker threads execute ready tasks and wake-up their dependents. Such an approach is incompatible with state-of-the-art schedulers such as the Cilk scheduler, that minimize the creation of idle tasks (work-first principle) and place all task creation and scheduling off the critical path. This paper proposes an extension to the Cilk scheduler in order to reconcile task dependencies with the work-first principle. We discuss the impact of task dependencies on the properties of the Cilk scheduler. Furthermore, we propose a low-overhead ticket-based technique for dependency tracking and enforcement at the object level. Our scheduler also supports renaming of objects in order to increase task-level parallelism. Renaming is implemented using versioned objects, a new type of hyper object. Experimental evaluation shows that the unified scheduler is as efficient as the Cilk scheduler when tasks have no dependencies. Moreover, the unified scheduler is more efficient than SMPSS, a particular implementation of a task dataflow language.
Original languageEnglish
Title of host publication2011 International Conference on Parallel Architectures and Compilation Techniques (PACT 2011)
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Pages1-11
Number of pages11
ISBN (Print)9781457717949
DOIs
Publication statusPublished - Oct 2011
Event2011 International Conference on Parallel Architectures and Compilation Techniques (PACT) - Galveston, United States
Duration: 10 Oct 201114 Oct 2011

Conference

Conference2011 International Conference on Parallel Architectures and Compilation Techniques (PACT)
CountryUnited States
CityGalveston
Period10/10/201114/10/2011

Bibliographical note

ISSN: 1089-795X

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Theoretical Computer Science

Fingerprint Dive into the research topics of 'A Unified Scheduler for Recursive and Task Dataflow Parallelism'. Together they form a unique fingerprint.

Cite this