  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.
