Parallel Evaluation of Dataflow Programs for Extreme-Scale Many-Task Computing

TitleParallel Evaluation of Dataflow Programs for Extreme-Scale Many-Task Computing
Publication TypeConference Paper
Year of Publication2011
AuthorsWozniak, JM, Maheshwari, K, Zhang, Z, Munson, TS, Foster, IT, Katz, D, Lusk, EL, Ripeanu, M, Wilde, M
Date Published09/2011
Other NumbersANL/MCS-P1933-0911

Developing programming solutions to help applications utilize the high concurrency of multi-petaflop computing systems is a challenge. Emerging languages such as Dryad, Swift, and Skywriting provide a promising direction. Their implicitly parallel dataflow semantics allow the high level logic of large-scale applications to be expressed in a manageable way while exposing massive parallelism through many-task programming. However, the implementations of these languages limit the evaluation of the overall program to a single-node computer, relying on threads and the multiple SMP cores of the evaluation node to generate the parallel tasks which are in turn executed on many nodes.

In this work, we provide a model for distributed parallel evaluation of dataflow programs in a manner that spreads the overhead of program evaluation and parallel task generation throughout an extreme-scale computing system. This execution model enables function and expression evaluation to take place on any node of a computing system. It breaks parallel loops into fragments for distributed execution, and can more readily achieve the task generation rates needed to efficiently utilize future exascale systems.

This paper describes the design and preliminary implementation of a distributed evaluation model for implicitly parallel dataflow programs, and motivates it with requirements projected from scientific applications. The preliminary implementation shows promising scalability curves and processes 500K task/sec on 1024 lowspeed compute nodes.