Analyzing Halo Computations on Multicore CPUs

Abstract

Den fortsettende ytelses økningen for flerkjerne- og flernode systemer, krever at algoritmer parallelliseres for å utnytte ytelsen til slike systemer. Beregninger på store datasett gjøres raskere i slike systemer, da en kan raskere beregne flere verdier i parallell. Parallellisert stensil beregninger er en både regne- og kommunikasjonstung metode. Parallelliseringen introduserer oppspaltning av datasettet, som igjen krever kommunikasjon mellom nodene for at beregningene skal gi rett svar. Fordelen er at mellom hver iterasjon i metoden kreves det synkronisering, men under selve iterasjonen er det ingen kommunikasjon som hemmer beregningene, noe som er fordelaktig for parallelliseringen. Dette prosjektet implementerer en 3D-stensil-beregnings algoritme som bruke halo exchange som kommunikasjons mønster mellom nodene. Denne applikasjonen blir så brukt til å teste ulike aspekter ved halo exchangen og stensil beregningene. Vi ser på hvordan ulike optimaliseringer påvirker kjøretiden, hvor godt halo exchange blir gjemt av kjøretiden, hvordan algoritmen skalerer, samt hvordan kjøring på et ressursdelte maskiner påvirker kommunikasjonen.

Vi observerte en ytelses forbedring på 11.15x ved endring av datastruktur og kalkulering av minnehopp i forkant. Videre så vi at stensilutrulling ga en ytterligere forbedring på 1.40x. Skaleringen viste en "strong scaling" på 9.46x forbedring fra 1 til 12 noder, samt en "weak scaling" på 0.61x ved proporsjonal økning av antall noder og datasettets størrelse. I de fleste kjøringene ble kommunikasjonen kun 7% av kommunikasjonen gjemt under kjøring på disse delte ressursene, uten eksklusiv tilgang til disse. Da vi introduserte eksklusiv tilgang til nodene så vi 902% av kommunikasjonen gjemt, og 529% gjemt for det store datasettet fordi her må betydelig mer kommuniseres mellom nodene.

Dette viser i all hovedsak at eksklusiv tilgang på ressursene er den største bidragsyteren for å skjule kommunikasjonen. Hvis en annen bruker blir tildelt de resterende ressursene på samme maskin kan dette føre til kniving om kommunikasjonsressursene og dermed øke ventetiden for hvert kommunikasjonssteg. Videre så vi at oppskalering av antall noder og datasett størrelse økte mengden data prosessert per sekund, men ikke proporsjonalt med ressursøkningen som ble tildelt. For å utnytte den økte ytelsen godt ser vi at eksklusiv tilgang på maskinene og gode optimaliseringer vil redusere kjøretiden for 3D stensil beregninger. Oppskalering av ressurstilgangen vil også positivt påvirke prosesseringstiden, dog ikke proporsjonelt med økningen i ressurser som våre skaleringseksperimenter viste.

The continued increase in multi-core and multi-node system performance makes parallelization of algorithms necessary in order to get the best performance gains by utilizing the available CPU resources. These increasingly complex systems allow for larger datasets to be handled in parallel in order to improve performance. Stencil-based algorithms with halo exchange are typically a compute and communication heavy task benefitting from parallelization over multiple nodes. This is achieved since compute can be done between bulk communications.

This thesis focuses on implementing a 3D stencil computation benchmark using halo exchange for inter-node communication. The goal of the thesis is to benchmark and test different aspects of halo exchange-powered stencil computations. We test various optimizations to improve the computational intensity of the algorithm, observe how strong and weak scaling of the algorithm increases throughput, how halo exchange is hidden by computation, and how running on a shared cluster affects the exchange.

Our optimizations gave a total speed-up of 11.15, with stencil unrolling showing an additional 1.40x speed-up potential. Scaling showed potential with a speed-up of 9.46x from 1 to 12 nodes on the same problem size and 0.61 times performance gain when scaling both problem and node size equally. Furthermore, only 7-91% of the halo exchange was hidden with shared resources. However, node exclusivity resulted in 902% of the exchange hidden and 529% hidden for a large problem domain.

Our results show that with exclusive node access, halo exchange can be completely hidden by computation when doing a triple loop that results in a 27-point calculations. Scaling the node count will improve performance to some degree. However, the speed-up is not proportional to the nodes added as the compute loop is not a perfect parallel region.

In order to exploit the extra performance from multi-core clusters for stencil computations, exclusive node access is needed to maximize performance. Increasing the amount of resources will increase throughput, but strong and weak scaling shows that the throughput increase is not proportional to the added resources.

A discussion of how to optimize the 27-point calculations and several ideas for future work are also included.