Performance Characterization and Evaluation of Parallel PDE Solvers

Henrik Johansson

22 November 2006

Abstract:

Computer simulations that solve partial differential equations (PDEs) are common in many fields of science and engineering. To decrease the execution time of the simulations, the PDEs can be solved on parallel computers. For efficient parallel implementations, the characteristics of both the hardware and the PDE solver must be taken into account. In this thesis, we explore two ways to increase the efficiency of parallel PDE solvers.

First, we use full-system simulation of a parallel computer to get detailed knowledge about cache memory usage for three parallel PDE solvers. The results reveal cases of bad cache memory locality. This insight can be used to improve the performance of the PDE solvers.

Second, we study the adaptive mesh refinement (AMR) partitioning problem. Using AMR, computational resources are dynamically concentrated to areas in need of a high accuracy. Because of the dynamic resource allocation, the workload must repeatedly be partitioned and distributed over the processors. We perform two comprehensive characterizations of partitioning algorithms for AMR on structured grids. For an efficient parallel AMR implementation, the partitioning algorithm must be dynamically selected at run-time with regard to both the application and computer state. We prove the viability of dynamic algorithm selection and present performance data that show the benefits of using a large number of complementing partitioning algorithms. Finally, we discuss how our characterizations can be used in an algorithm selection framework.

Note: Included papers available at http://www.it.uu.se/research/publications/lic/2006-010/paperA.pdf, http://www.it.uu.se/research/publications/lic/2006-010/paperB.pdf, and http://www.it.uu.se/research/publications/lic/2006-010/paperC.pdf

Available as PDF (528 kB)

Download BibTeX entry.