Performance Analysis and Scheduling of Stochastic Fork-Join Jobs in a Multicomputer System

We model a parallel processing system comprising several homogeneous computers interconnected by a communication network. Jobs arriving to this system have a linear fork-join structure. Each fork of the job gives rise to a random number of tasks that can be processed independently on any of the computers. Since exact analysis of fork-join models is known to be intractable, we resort to obtaining analytical bounds to the mean job response time of the fork-join job. For jobs with a single fork-join and, probabilistic allocation of tasks of the job to the N processors, we obtain upper and lower bounds to the mean job response time. Upper bounds are obtained using the concept of associated random variables and are found to be a good approximation to the mean job response time. A simple lower bound is obtained by neglecting queueing delays. We also find two lower bounds that include queueing delays. For multiple fork-join jobs, we 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