Performance analysis and scheduling of stochastic fork-join jobs in a multicomputer system

Abstract

The authors model a parallel processing system comprising several homogeneouscomputers interconnected by a communication network. Jobs arriving to this system havea linear fork-join structure. Each fork of the job gives rise to a random number of tasksthat can be processed independently on any of the computers. Since exact analysis offork-join models is known to be intractable, the authors resort to obtaining analyticalbounds to the mean job response time of the fork-join job. For jobs with a single fork-joinand, probabilistic allocation of tasks of the job to the N processors, they obtain upperand lower bounds to the mean job response time. Upper bounds are obtained using theconcept of associated random variables and are found to be a good approximation to themean job response time. A simple lower bound is obtained by neglecting queueing delays. They also find two lower bounds that include queueing delays. For multiple fork-join jobs, they study an approximation based on associated random variables. Finally, two versions of the join-the-shortest-queue (JSQ) allocation policy (i.e., JSQ by batch and JSQ by task) are studied and compared, via simulations and diffusion limits.