Optimal latency-throughput tradeoffs for data parallel pipelines
Optimal latency-throughput tradeoffs for data parallel pipelines
复制标题
数据并行管道的最佳延迟-吞吐量权衡
DOI：
--
复制
发表时间：
1996
期刊：
影响因子：
--
通讯作者：
G. Vondran
中科院分区：
文献类型：
--
作者：
J. Subhlok;G. Vondran
本文研究由数据并行任务链组成的并行程序到并行系统处理机的最优映射问题。这类程序的输入是一个数据集流，每个数据集都由任务链按顺序处理。这种计算结构，也被称为数据并行流水线，在数字信号处理、图像处理和计算机视觉等多个应用领域都很常见。流处理性能的参数是延迟（处理单个数据集的时间）和吞吐量（处理数据集的总速率）。这两个标准是不同的，因为多个数据集可以流水线或并行处理。我们提出了一种新的算法来确定一个处理器映射的任务链，优化的延迟存在的吞吐量约束，并chscuss优化的吞吐量与延迟的约束。问题的制定使用一个通用的和现实的模型，任务间的通信，并解决了映射，其中包括聚类任务到模块，分配处理器的模块，和可能的复制模块的入口问题。主要算法基于动态规划，其执行时间复杂度是关于处理器和任务数量的多项式。整个框架是作为一个自动映射工具，在高性能Fortran方言的Fx并行化编译器。
This paper addressesoptimal mapping of parallel programs composed of a chain of data parallel tasks onto the processors of a parallel system. The input to this class of programs is a stream of data sets, each of which is processed in order by the chain of tasks. This computation structure, also referrecl toasa data parallel pipeline, iscommon inseveralapplication domains including digital signal processing, image processing, and computer vision. Theparameters of the performance of stream processing are latency (the time to process an individual data set) and throughput (the aggregate rate at which the data sets are processed). These two criterion are distinct since multiple data sets can be pipelined or processed in parallel. We present anew algorithm to determine a processor mapping of a chain of tasks that optimizes the latency in the presence of throughput constraints, and chscuss optimization of the throughput with latency constraints. The problem formulation uses a general and realistic model of inter-task communication, and addresses the entree problem of mapping, which includes clustering tasks into modules, assignment of processors to modules, and possible replication of modules. The main algorithms are based on dynamic programming and their execution time complexity is polynomial in thenumber of processors and tasks. The entire framework is implemented as an automatic mapping tool in the Fx parallelizing compiler for a dialect of High Performance Fortran.