Performance Modeling of a Load-Balanced FDM Wave Equation Solver on Heterogeneous Clusters

Abstract

I denne avhandlingen utvikles en skalerbar implementasjon av endelig differansemetode for å løse den todimensjonale bølgelikningen. Vi utvikler algoritmer som benytter lastbalansering i flere lag for å sikre at beregningsressursene tilgjengelig blir utnyttet effektivt, selv i heterogene miljøer. Implementasjonen bruker både GPUer og CPUer for å beregne stensilene is samtid, og overlapper kommunikasjon med beregninger. Vi lager også en ytelsesmodell for å forutsi kjøretiden nøyaktig.

Den mest avgjørende beregningskjernen er validert til å være nær optimal ved bruk av rooflineanalyse. Sterk skalering er målt både på en enkelt node, hvor effektiveten er 97% når 10 grafikkort er i bruk, og på tvers av noder er effektiviteten 96% når ti noder med et grafikkort hver brukes. Svak skalering er også undersøkt, og på store gittere oppnås 93% effektivitet på ti noder, som beregner et diskretisert gitter på nesten 10 milliarder punkter. Implementasjons anvender semistatisk lastbalansering for å fordele last på heterogene noder, men også mellom beregningsenhetene tilstede på en enkelt node. Vi demonstrerer fordelen av lastbalasering ved å kjøre en benchmark både med og uten lastbalanseringa aktivert.

Vi modellerer kommunikasjonen mellom prosesser og minneoverføringer mellom enheter ved bruk av Hockneymodellen. For beregninger tilpasser vi enkle analytiske funksjoner til målinger av beregningshastighet ved ulike gitterstørrelser for å modellere ytelsen. Denne metoden vil implisitt ta høyde for minnehierarkiet og minneparallelismer. Ytelsesmodellen trenger altså å måle latens og båndbredde mellom prosessene, samt estimere beregningskapasitet for å predikere kjøretid.

Ytelsesmodellen er validert ved å sammenligne resultatene fra stark og svakskalingstestene, samt den heterogene benchmarken som tydeliggjør effektene av lastbalansering. Resultatene viser at modeller er særlig nøyaktig for store problemstørrelser, med en gjennomsnittlig prosent differanse på 5.9%. Når store gittere modelleres i et heterogens miljø som bruker lastbalanseringen er kjøretiden modellert med en prosentdifferanse på 3.6%.

This thesis develops a scalable implementation of the finite difference method to solve the 2D wave equation. We develop algorithms that utilize load balancing at multiple levels to ensure that the computational resources are utilized effectively, even in heterogeneous clusters. The implementation uses GPUs and CPUs to execute stencil operations concurrently and overlaps the communication with computation. We also develop a performance model to predict the runtime of the algorithms accurately.

The most important computational kernels are validated to be close to optimum using roofline analysis. Strong scaling is measured on a single node, achieving a 97% efficiency when using ten GPUs, and across nodes, with 96% efficiency when using one GPU from ten different nodes. Weak scaling is also tested, and on large grids, we measure a 93% efficiency when using ten nodes to compute a set of discretized grids containing almost ten billion points. The implementation uses semi-static load balancing to distribute the workload among heterogeneous nodes and between the computational devices present on each node. We demonstrate the benefits of load balancing by running benchmarks with and without it to measure the difference.

We model inter-process communication and memory transfers between devices using the Hockney model. For computation, we fit simple analytic functions to measurements of how many stencil computations each device can achieve for grids of varying sizes. This will implicitly account for caching and memory-level parallelism. Our performance model then needs to measure the latency and bandwidth between the processes and estimate the computational throughput of each node to predict the runtime.

The performance model is validated by comparing it to the results of the strong and weak scaling experiments, as well as the heterogeneous benchmark showcasing the effects of the load balancing. The results show that the model is particularly reliable for large problem instances, with a mean percentage difference of 5.9%. When modeling a large grid being computed in a heterogeneous environment employing the load balancing scheme, the runtime is modeled with a percentage difference of 3.6%.