Performance Modeling of a Finite Volume Method for the Shallow Water Equations

Abstract

Oppgaven omhandler en proxy-applikasjon for å beregne grunnvannsligningene gjennom den endelige volummetoden. Vannoverflaten er diskretisert gjennom en triangulering, der kystlinjen til Mehamn brukes til alle tester. Applikasjonen bruker MPI for å lage parallelle prosesser og OpenMP for å lage parallelle tråder for hver prosess, og kjøres på Idun-klyngen ved NTNU.

En ytelsesmodell for applikasjonen forutsier parametrene til den trekantede strukturen, som er basert på antall punkter, og bruker de strukturelle estimeringene til å forutsi kjøretid og skaleringskarakteristikk. Modellen skiller mellom beregnings- og kommunikasjonstid, med fokus på skaleringsegenskapene til beregningstiden. De geometriske unntakene blir eliminert ved å holde seg til Mehamn for alle trianguleringene. Roofline- og Hockney-modell er også estimert gjennom et sett med benchmarking-tester for å oppdage maskinvareegenskapene til maksimal FLOP-ytelse og kommunikasjonstid. En sammenligning av ytelsesmodellen og benchmarking-modellene med applikasjonskjøringen brukes for å verifisere ytelsesegenskapene til applikasjonen.

Resultatene viser en presis prediksjon av parametrene til den trekantede strukturen, som bekrefter det første trinnet i ytelsesmodellen. Gjennom roofline-modellen bekrefter benchmarking-testene at applikasjonen er minnebundet, hvor maksimal båndbredde brukes videre til ytelsesmodellen. Hockney-modellen bekrefter at kommunikasjonstiden forblir konstant for et økende antall noder og vokser sakte for en økende problemstørrelse, mens kommunikasjonstiden mellom noder blir overvurdert.

Resultatene viser også konsistent skalerbarhet av beregningstiden mellom ytelsesmodellen og applikasjonskjøringen, for både sterk og svak skalering, og for skalering av både prosesser og tråder, gitt at problemstørrelsen ikke flyter over cache-minnet. Dette støttes av en jevn lastbalanse mellom prosesseringsenhetene. Det er oppdaget at cache-minnet til maskinvaren påvirket skalerbarheten, der en problemstørrelse for stor til å passe inn i cache-minnet gav dårligere ytelse. I tillegg gav én prosess per node dårligere ytelse, siden en node har flere CPUer med separate cache-minner, noe som får trådene til å forurense cache-minnet. En optimal ytelse oppnås ved å velge en problemstørrelse som bruker hele cache-minnet og ved å tildele minst én prosess for hver CPU. Ved å bruke den konstante kommunikasjonstiden gir dette en samlet stabil og forutsigbar svak skalering, egnet for skalering av noder med multiprosessorer.

The thesis presents a proxy application for computing the shallow water equations through the finite volume method. A triangulation discretizes the water surface, where the coastline of Mehamn harbor is used for all tests. The application uses MPI for making parallel ranks and OpenMP for creating parallel threads for each rank, and is run on the Idun cluster provided by NTNU.

A performance model for the application predicts the parameters of the triangular structure, which is based on the number of vertices, and uses the structural estimations to predict the runtime and scaling characteristics. It separates computation and communication time, with focus on the scaling characteristics of the computation time. By applying Mehamn harbor for the triangulation, a more direct prediction is made, as the geometrical exceptions are eliminated. The roofline and Hockney models are also made through a set of benchmarking tests in order to discover the hardware properties of maximum FLOP performance and communication time of message passing. A comparison of the performance model and the benchmarking models with the application execution is used to verify the performance characteristics of the application.

The results show an accurate prediction of the parameters of the triangular structure, which confirms the first step of the performance model. Through the roofline model, the benchmarking tests confirms that the application is memory bound, where the maximum bandwidth is further used for the performance model. The Hockney model confirmed that the communication time stays constant for an increasing number of nodes and grows slowly for an increasing problem size, while the communication time between nodes were overestimated.

The results also show consistent scalability of computation time between the performance model and the application execution, for both strong and weak scaling, and for scaling of both ranks and threads, given that the problem size does not overflow the cache memory. This is supported by an even load balance between the processing units. It is discovered that the cache memory of the hardware affected the scalability, where a problem size too large to fit into cache gave a poorer performance. In addition, a single rank per node gave a poorer performance, since a node has multiple CPUs with separate cache memories, causing the threads to pollute the cache. An optimal performance is reached by choosing a problem size that uses the entire cache space and by assigning at least one rank for each CPU. By applying the constant communication time, this gives an overall stable and predictable weak scaling, suitable for scaling of nodes with multiprocessors.