网格中流水式计算的一种任务指派算法

为取得网格中流水式计算的高吞吐率,提出一种任务指派算法X max min.在一个流水线中,任务彼此是并行的,且每个任务本身是可并行化的.当多个任务被指派到同一个并行系统时,通过最小化任务计算成本的最大值确定每个任务分得处理机的个数.任务用于收发数据集的通信成本依赖其他任务的指派,故当相关任务的指派未完成时,需要在任务通信成本中引入均值估计.任务响应时间是计算成本和通信成本之和,它是任务指派的函数.用max min算法确定任务指派,可有效降低任务响应时间的最大值,从而使流水线的吞吐率得到提高.仿真实验表明,X max min算法使流水线取得的吞吐率与复杂的Taura算法相当.

Task Assignment Algorithm for Pipelined Computing in Grid

To obtain high throughput of the pipelined computation in grid, a task assignment algorithm called X-max-min was proposed. In a pipeline, tasks were parallel with each other, and each task was parallelizable itself. When more than one task was assigned to an identical parallel system, the number of processors allocated to each task was determined by minimizing the maximum of task computation costs. The task communication cost used for receiving and sending a data set depended on the assignments of other tasks, so the mean estimate was needed to be introduced into the task communication cost when the assignments of related tasks were not completed yet. The task response-time was the sum of the computation cost and communication cost, and was a function of task assignments. Using max-min algorithm to determine task assignments, the maximum of the task response-times could be effectively reduced so that the pipeline throughput was increased. Simulation results show that the X-max-min algorithm makes pipelines obtain high throughput that is almost the same as the one provided by complicated Taura's algorithm.