Performance characterization and evaluation of parallel PDE solvers

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