J. Papay, T.J. Atherton, M.J. Zemerly and G.R. Nudd, Performance Prediction of Parallel Self Consistent Field Computation (February 1, 1996).
This paper presents a methodology for performance prediction of parallel algorithms and illustrates its use on a large scale computational chemistry application. The performance prediction uses a component time characterisation technique which splits up the sequential code into computational components and measures the time for each of them. The parallel algorithm is built from these components by adding communication routines. A "Processor Activity Graph" (PAG) providing a graphical representation of the parallel algorithm runtime behaviour is used for predicting the execution time. For a case study a Self Consistent Field (SCF) computation has been selected which forms the basis of many computational chemistry packages [4,5]. The performance model of SCF computation has been built and the predictions have been compared with the results of measurements. The measurements have been provided on a mesh connected distributed memory parallel computer (128 T800 Parsytec SuperCluster). The prediction error is less than 10 percent. Performance optimisation of the application has been achieved by reducing the communication overhead and changing the data representation. This paper introduces a new model of computation that employs the tools of molecular biology whose in vitro implementation is far more error-resistant than extant proposals. We describe an abstraction of the model which lends itself to natural algorithmic description, particularly for problems in the complexity class NP. In addition we describe a number of linear-time algorithms within our model, particularly for NP-complete problems. We describe an in vitro realisation of the model and conclude with a discussion of future work.