Keywords: parallel distributed algorithms, performance evaluation and prediction, multigrid numerical software.

This paper investigates the modelling and prediction of the performance of a class of parallel numerical multigrid software that can be implemented with different geometric partitioning of the computational work across a distributed memory architecture. A relatively simple empirical model is proposed, with the goal of allowing reliable predictions to be made as to the execution time of a given parallel code, on a large number of processors of a given parallel system, by only benchmarking the code on small numbers of processors. When extra memory and processors are available, parallel multilevel implementations are able to solve problems numerically on finer meshes, so as to achieve greater accuracy than would be otherwise possible. The methodology described permits us to estimate the performance prior to actually running with these very fine meshes on large numbers of processors. This is of great potential value in making decisions concerning the choice of resources and the scheduling of jobs within a multi-cluster or a Grid environment.

Following a short introduction, Section 2 of the paper describes some recent related work into performance modelling for parallel numerical software. In Section 3, we then provide a short summary of our previous work [1,2,3] in this area, where we have implemented predictive methodology for parallel multilevel software running across a one-dimensional strip partition of data and processors. The methodology used in this prior work is exploited in this new research for modelling and predicting the performance of multigrid software with different partitioning strategies, such as using a two-dimensional block partitioning approach for example.

The parallel execution time is assumed to be representable as the sum of two terms: the core computational time (on the slowest processor) and the parallel overhead (the latter being primarily due to inter-processor communications). Section 4 of the paper describes the methodology used to model both the computational time and the parallel overhead. In order to predict the communications patterns for large parallel runs, we use only information based on the patterns observed for sequences of runs across small numbers of processors.

Finally, in Section 5, a selection for numerical results obtained using our methodology are presented and discussed. We demonstrate that the approach is robust and accurate across different parallel architectures, sizes of problem and partitioning strategies used.

1

G. Romanazzi, P.K. Jimack, "Parallel performance prediction for multigrid codes on distributed memory architectures", in R. Perrott et al., (Editors), "High Performance Computing and Communications (HPCC-07)", Lecture Notes in Computer Science 4782, Springer, 647-658, 2007. doi:10.1007/978-3-540-75444-2_61

2

G. Romanazzi, P.K. Jimack, "Parallel performance prediction for numerical codes in a multi-cluster environment", in M. Ganzha et al., (Editors), "Proceedings of the 2008 International Multiconference on Computer Science and Information Technology (IMCSIT'08)", PTI Press, Katowice, Poland, 467-474, 2008.

3

G. Romanazzi, P.K. Jimack, C.E. Goodyer, "Reliable performance prediction for parallel scientific software in a multi-cluster Grid environment", in M. Papadrakakis, B.H.V. Topping, (Editors), "Proceedings of the Sixth International Conference on Engineering Computational Technology", Civil-Comp Press, Paper 4, 2008. doi:10.4203/ccp.89.4

purchase the full-text of this paper (price £20)

go to the previous paper
go to the next paper
return to the table of contents
return to the book description
purchase this book (price £72 +P&P)