论文标题
并行UNIX管道的订单感知数据流模型
An Order-Aware Dataflow Model for Parallel Unix Pipelines
论文作者
论文摘要
我们提出了用于对并行UNIX壳管道建模的数据流模型。为了准确捕获复杂的Unix管道的语义，数据流模型是订单感知的，即，数据流图中的节点消耗来自不同边缘的输入的顺序在计算语义和所得并行化中起着核心作用。我们使用此模型捕获转换的语义，这些转换利用了Unix Shell计算中可用的数据并行性并证明其正确性。我们还将从Unix Shell到DataFlow模型以及从数据流模型到并行壳脚本的翻译正式化。当编译器和优化通过系统平行的外壳管道的编译器和优化时，我们实施了模型和转换，并使用它来评估47个管道上实现的速度。
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.
