王庆江，桂小林，郑守淇
（西安交通大学电子与信息工程学院,710049,西安)
摘要：为取得网格中流水式计算的高吞吐率，提出一种任务指派算法X-max-min.在一个流水线中，任务彼此是并行的，且每个任务本身是可并行化的.当多个任务被指派到同一个并行系统时，通过最小化任务计算成本的最大值确定每个任务分得处理机的个数.任务用于收发数据集的通信成本依赖其他任务的指派，故当相关任务的指派未完成时，需要在任务通信成本中引入均值估计.任务响应时间是计算成本和通信成本之和，它是任务指派的函数.用max-min算法确定任务指派，可有效降低任务响应时间的最大值，从而使流水线的吞吐率得到提高.仿真实验表明，X-max-min算法使流水线取得的吞吐率与复杂的Taura算法相当.
关键词：网格；流水式计算；流水线；任务指派；吞吐率
中图分类号：TP393文献标识码：A文章编号： 0253９８７Ｘ（２００4）040417０3