Abstract
Parallel programs are often written in the SPMD (single-program-multiple-data) form for exploiting data parallelism in the applications. In this paper, we show that even in SPMD programs further parallelism can be extracted by considering the function parallelism in the programs. Exploiting function parallelism is especially important for parallel systems using the NOW (network of workstations) approach. This is because the high communication overhead in such systems can be hidden with explicit control over the function parallelism. In this paper we describe a general methodology for exploiting function parallelism in SPMD programs and discuss the considerations involved in realizing such parallelism with the multithreading facility supported by most workstations today. The resultant multithreaded parallel program is still coded in the SPMD form. We demonstrate the application of this technique to a PDE solver, which solves a system of linear equations using Jacobi relaxation. Experiments on an 8-node NOW confirm that the performance of an SPMD program can be improved further by exploiting its function parallelism.