Advanced search
1 file | 399.39 KB Add to list

A unified scheduler for recursive and task dataflow parallelism

(2011)
Author
Organization
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 hyperobject. 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.

Downloads

  • paper.pdf
    • full text
    • |
    • open access
    • |
    • PDF
    • |
    • 399.39 KB

Citation

Please use this url to cite or link to this publication:

MLA
Vandierendonck, Hans, George Tzenakis, and Dimitrios S Nikolopoulos. “A Unified Scheduler for Recursive and Task Dataflow Parallelism.” New York, NY, USA: IEEE, 2011. Print.
APA
Vandierendonck, H., Tzenakis, G., & Nikolopoulos, D. S. (2011). A unified scheduler for recursive and task dataflow parallelism. Presented at the 20th International conference on Parallel Architectures and Compilation Techniques (PACT 2011), New York, NY, USA: IEEE.
Chicago author-date
Vandierendonck, Hans, George Tzenakis, and Dimitrios S Nikolopoulos. 2011. “A Unified Scheduler for Recursive and Task Dataflow Parallelism.” In New York, NY, USA: IEEE.
Chicago author-date (all authors)
Vandierendonck, Hans, George Tzenakis, and Dimitrios S Nikolopoulos. 2011. “A Unified Scheduler for Recursive and Task Dataflow Parallelism.” In New York, NY, USA: IEEE.
Vancouver
1.
Vandierendonck H, Tzenakis G, Nikolopoulos DS. A unified scheduler for recursive and task dataflow parallelism. New York, NY, USA: IEEE; 2011.
IEEE
[1]
H. Vandierendonck, G. Tzenakis, and D. S. Nikolopoulos, “A unified scheduler for recursive and task dataflow parallelism,” presented at the 20th International conference on Parallel Architectures and Compilation Techniques (PACT 2011), Galveston, TX, USA, 2011.
@inproceedings{1934780,
  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 hyperobject. 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.},
  author       = {Vandierendonck, Hans and Tzenakis, George and Nikolopoulos, Dimitrios S},
  language     = {eng},
  location     = {Galveston, TX, USA},
  pages        = {11},
  publisher    = {IEEE},
  title        = {A unified scheduler for recursive and task dataflow parallelism},
  year         = {2011},
}