Approximate analysis of the average delay in parallel program execution

An approximate analysis of the average delay executing a parallel program is presented. The parallel processing system under consideration is modeled as an acyclic fork-join queuing network. The system model consists of a set of N parallel paths, where individual paths model the delay incurred by each of the tasks spawned by the parent job. Each path may consist of several servers and associated queues. Each server can model either the communication or processing requirement of a task. The delay incurred by a task is the sum of the communication and processing delays along its path. An approximation for the mean value of the job execution delay is presented. The results from the analytical expression are validated against simulation. This analysis may be used to obtain the speedup factor for different communication and processing configurations. The effect of subtask granularity and effects of relative communication and processing times and associated tradeoffs can be studied