This paper considers the following problem: In a fork:.RW.5 :.US and:.US join type of situation, n independent subtasks arise which can be assigned to p parallel processors. Allocation of subtasks to a processor is in batches of K subtasks, each batch allocation inducing some overhead h. What is the impact of K (on total finishing time, on efficiency, etc.)? Here is the stochastic setting: All subtask processing times are identically distributed (mean &mgr;, variance 6²), and all overhead times are identically distributed. Assuming “increasing failure rate” distributions for subtask times and “infinitely divisible” distributions for overhead times, the paper derives, as the central result, a formula for the expected total finishing time, E [ T ], asymptotically correct for large parameter values, in particular for large n &slash; p.

Due to a number of nonstandard derivations and intermediate results, the paper is interesting to read from a theoretical point of view. For the practitioner, it will be comforting news that the result for E [ T ] consists of two additive terms (overhead h deterministic):

(1) the first term, ( n &slash; p ) &dundot; μ + ( n &dundot; h ) &slash; ( p &dundot; K ), coinciding with the obvious guess, and

(2) the second, corrective term, &sgr; &dundot; &sqrt;2 K &dundot; log ( p ), being considered relatively small, by the authors.

On the other hand, I was not able to verify the various included graphs, E [ T ] vs. K, numerically against the given formula. The formula’s corrective term appears to me larger than depicted. This observation would conform with one of the authors’ concluding remarks that “significant improvement” in efficiency is possible by moving from fixed size batches to variable size batches; though it would somehow contradict the statement that “total time changes relatively little” with K.