| Performance analysis of parallel systems has become important with the growing popularity of multiprocessor systems and parallel programming languages. A job on arriving at a parallel system is often split (forked) into several tasks which then execute in parallel on different processing units. When a task completes its execution phase it waits at the barrier synchronization (join) point for its siblings to complete execution. A job leaves the system only when all its tasks complete execution. Queueing models are often used to analyze such problems. The fork-join structure is the basic queueing model of parallel systems and this work focuses on the study of such queueing networks. The synchronization introduced by forking of jobs and joining of tasks destroys product-form properties of queueing networks. Consequently, product-form networks do not provide a viable framework for evaluating parallel systems. There is a need to expand the theory of queueing networks into new directions to better model issues relating to parallelism.;The primary contributions of this work are in two main areas of concentration with regard to parallel systems. The first area concentrates on the response time analysis of parallel systems using a tagged job approach. The response time is shown to be the sum of wait and service times which are defined in a parallel system context. The distributions of service and wait time are then derived. The service time of a tagged job is shown to be dependent on the jobs ahead of this job in the parallel system. The wait time is shown to be equal to the sum of mutually independent, non-identical random variables representing the service times of jobs ahead of the tagged job. The analysis quantifies the recursive behavior of fork-join systems and helps to better understand the effect of fork-join constraints and parallelism on system performance. The second area of concentration focuses on the underlying stochastic process of a fork-join queueing network. The fork-join queue is mapped onto two non-parallel networks, namely, a serial-join model and a state-dependent model. Using these models, results relating the arrival, departure, and steady state distributions of fork-join networks are derived. In particular, a closed form equation for the queue lengths of closed, balanced fork-join networks is given. This analysis leads to a quick and easy solution technique for solving performance measures of a closed parallel network. |
