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

王庆江　桂小林　郑守淇

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

关键词：网格；流水线；数据并行流水线；吞吐率；延迟；任务指派

中图分类号：TP393文献标识码：A文章编号：0253—987X(2004)08—0771—04