Performance Modeling of Finite Difference Shallow Water Equation Solvers with Variable Domain Geometry

Abstract

I denne oppgaven undersøker vi metoder som kan brukes til å redusere ubalansert beregningslast, som kan oppstå når man dekomponerer et todimensjonalt domene av endelige differanser med ujevn beregningskostnad. I dette tilfellet kan en Kartesisk dekomponering opprette ubalanserte partisjoner, fordi den ikke utnytter strukturen til domenet. Slike ubalanser kan resultere i signifikante ventetider for applikasjonen, som skyldes at en prosess må vente på å motta resultatdata fra en annen.

Vi beskriver to dekomponeringsteknikker som står i kontrast til den Kartesiske metoden. En av disse er basert på ortogonal rekursiv halvering, mens den andre er basert på diagonal rektangulering. Vi viser så at den økte kommunikasjonskostnaden som disse fører til oppveies gjennom økt effektivitet som følge av reduserte ventetider. Til slutt implementerer vi en proxy-applikasjon som løser grunntvannslikningene numerisk. Denne applikasjonen introduserer regioner med varierende beregningskostnad som lar oss teste våre ideer og demonstrere deres nytte.

In this thesis we examine techniques for reducing the computational load imbalance which may arise when creating decompsitions of a two-dimensional finite difference domain with regions of uneven computational cost. In this case a simple Cartesian decomposition may create partitions which are not balanced, because it does not exploit the domain's features. Depending on the choice of implementation, such an imbalance can result in significant periods of idle time in the application, as a consequence of one process having to wait for the results of another.

We describe two decomposition schemes to contrast with the simple Cartesian decompositon. One of these is rooted in orthogonal recursive bisection, while the other is based on diagonal rectangulation. We then show that the increase in communication cost introduced by the more complex decomposition schemes is outweighed by the efficiency gained though reduced wait times. Finally, we implement a proxy-application which solves the shallow water equations numerically. This application introduces regions of differing computational cost, which allows us to test our ideas and demonstrate their efficacy.