M.J. Zemerly, J. Papay and G.R. Nudd, Optimising Overlaped and Non-Overlapped Parallel Algorithms Using Bottleneck Analysis: A Case Study (November 1, 1995).
In this paper a methodology for parallel algorithm selection and optimisation based on performance prediction and bottleneck analysis is presented. The performance prediction method used here is based on an instruction set characterisation technique which assumes the availability of the sequential code and the compiler for the target machine. A "Processor Activity Graph" (PAG) which provides a graphical representation of the parallel system runtime behaviour is used to extend the applicability of the characterisation technique to overlapping parallel algorithms. The bottleneck analysis assumes that a bottleneck is caused by the slowest component of a computing system. These components are: memory, processor, communication and I/O. Three dimensionless ratios are used to identify and quantify bottlenecks, these are: the B-ratio, the communication-computation ratio and the memory-processing ratio. The optimisation methodology is illustrated and validated using a communication intensive linear solver algorithm (Givens rotations) which was implemented on a mesh connected distributed memory parallel computer (128 T800 Parsytec SuperCluster) using non-overlapping and overlapping parallelisation techniques.