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-time 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.