Execution-time modeling of parallel programs with message-passing communication

摘要

This paper presents a method of predicting the execution times for massage-passing parallel programs. It is to show the execution behaviors of parallel programs when they are being developed for scientific and engineering computation. We have analyzed parallel programs by classifying the code into two parts: computation and communication. Each part is estimated separately, then overall time is obtained. For the computation times, the number of arithmetic operations and the frequency of memory access are counted. As for the communication times, the latency in processor and interconnection network is modeled. The predicted times of programs are compared with experimental results to verify the validity. Representative algorithms such as bitonic sort, FFT, matrix multiplication and quick sort are coded and executed on IBM SP2 and a duster of PCs(personal computers). Results show good matching, together with a few cases of high errors in the prediction. It is from the fact that communication takes more time than the expected time due to the asynchronous nature of processors, thus the delay in their synchronization lengthens the time, and computation time may vary depending on many other factors not considered in the prediction such as system load, contention in memory access, high variation in cache hit ratio, etc. Although the estimate is not perfect, the result can serve to give rough execution behaviors of the programs being developed.