网格中数据并行流水线的任务指派优化

为了缩短网格中数据并行流水线在吞吐率受限下的延迟,提出了一种优化任务指派的算法.在一个流水线中,每个任务都可以是一个数据并行程序.当多个任务被指派到同一个并行系统时,假设每个任务排他地使用一组处理机.根据优化目的,优化过程可分成连续的两个阶段,即提高吞吐率和缩短吞吐率受限下的延迟.对不同的优化阶段,用不同的启发式算法确定一个并行系统中每个任务的处理机数.改派任一任务都会使流水线的性能发生变化,性能提高的幅度被称为任务优先级.通过重复改派优先级最高的任务,流水线的性能可迅速提高,这在仿真实验中已得到了证实.

Task Assignment Optimization for Data Parallel Pipelines in Grids

To shorten the throughput-constrained latency of data parallel pipelines in grids, an algorithm for optimizing task assignments was proposed. In a pipeline, each task might be a data parallel program. When more than one task was assigned to an identical parallel system, each task was supposed to exclusively use a set of processors. According to optimization purposes, the optimization process could be partitioned into two consecutive phases, namely, increasing the throughput and shortening the throughput-constrained latency. For different optimization phases, different heuristic algorithms were adopted to determine the processor number of each task in a parallel system. Reassigning any task would bring some changes to the pipeline performance, and the range of the increased performance was called task priority. By iteratively reassigning the task with highest priority, the pipeline performance would be increased quickly, which was proved in simulated experiments.