An order-aware dataflow model for parallel Unix pipelines
Abstract
We present a dataflow model for modelling parallel Unix shell pipelines. To accurately capture the semantics of complex Unix pipelines, the dataflow model is order-aware, i.e., the order in which a node in the dataflow graph consumes inputs from different edges plays a central role in the semantics of the computation and therefore in the resulting parallelization. We use this model to capture the semantics of transformations that exploit data parallelism available in Unix shell computations and prove their correctness. We additionally formalize the translations from the Unix shell to the dataflow model and from the dataflow model back to a parallel shell script. We implement our model and transformations as the compiler and optimization passes of a system parallelizing shell pipelines, and use it to evaluate the speedup achieved on 47 pipelines.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Aug 19, 2021
- Source ID
- 10.1145/3473570
Entities
People
- Konstantinos Kallas
- Martin C. Rinard
- Nikos Vasilakis
- Shivam Handa
Organizations
- Defense Advanced Research Projects Agency
- Massachusetts Institute of Technology
- National Science Foundation
- University of Pennsylvania