Optimised grid partitioning for block structured grids in parallel computing [Elektronische Ressource] / von Daniel Junglas

Description

Optimised Grid-Partitioning for BlockStructured Grids in Parallel ComputationVom Fachbereich Mathematikder Technischen Universit¨at Darmstadtzur Erlangung des Grades einesDoktors der Naturwissenschaften(Dr. rer. nat.)genehmigte DissertationvonDipl.-Math. Daniel Junglasaus Freiburg im BreisgauReferent: Prof. Dr. A. MartinKoreferent: Prof. Dr. M. Sch¨aferTag der Einreichung: 27. April 2006Tag der mu¨ndlichen Pru¨fung: 12. Dezember 2006Darmstadt 2007D17AbstractSimulation of turbulent flows in complex geometries is nowadays usually performed by ap-plication of grid-based algorithms on parallel computers. In this approach it is not onlyimportant to have a clever discretisation and an appropriate grid. One must also use (ordevelop) algorithms that are convergent and numerically stable. As a final ingredient tosuccess the different work packages of the simulation must be distributed over the set ofavailable processors. This distribution must be performed so as to optimally exploit thecomputational resources provided by processors, thereby minimising simulation time.Our work will focus on this last optimisation problem and develop models as well solutionalgorithms forit. To this end we assume that a block structured as well as a suitable simula-tionalgorithmarefixedandlookforanoptimalmapping ofblockstoprocessors.

Sujets

• Mathematics

Informations

• Publié par: technischen_universitat_darmstadt
• Publié le: 01 janvier 2007
• Nombre de lectures: 22
• Langue: English
• Poids de l'ouvrage: 2 Mo

Extrait

StrOupcttiumriesdedGrGirdisd-inPaPrtairtailolnelinCgofomrpuBtloatcikon

VomFachbereichMathematik
derTechnischenUniversita¨tDarmstadt
zurErlangungdesGradeseines
DoktorsderNaturwissenschaften
(Dr.rer.nat.)
genehmigteDissertation

novDipl.-Math.DanielJunglas
ausFreiburgimBreisgau

Referent:Prof.Dr.A.Martin
Koreferent:Prof.Dr.M.Scha¨fer
TagderEinreichung:27.April2006
Tagdermu¨ndlichenPru¨fung:12.Dezember2006

Darmstadt2007
71D

Abstract

Simulationofturbulentowsincomplexgeometriesisnowadaysusuallyperformedbyap-
plicationofgrid-basedalgorithmsonparallelcomputers.Inthisapproachitisnotonly
importanttohaveacleverdiscretisationandanappropriategrid.Onemustalsouse(or
develop)algorithmsthatareconvergentandnumericallystable.Asanalingredientto
successthedierentworkpackagesofthesimulationmustbedistributedoverthesetof
availableprocessors.Thisdistributionmustbeperformedsoastooptimallyexploitthe
computationalresourcesprovidedbyprocessors,therebyminimisingsimulationtime.
Ourworkwillfocusonthislastoptimisationproblemanddevelopmodelsaswellsolution
algorithmsforit.Tothisendweassumethatablockstructuredaswellasasuitablesimula-
tionalgorithmarexedandlookforanoptimalmappingofblockstoprocessors.Werestrict
ourselvestoblockstructuredgridsfortworeasons:onetheonehand,thisclassofgridsis
mostwidelyusedinsimulationofturbulentowsincomplexgeometries.Ontheotherhand
blockstructuredgridscanbepartitionedintoarelativelysmallnumberofblocksandthe
mappingproblemcanberestrictedtothesetofblocks.Thislastaspectallowsapplicationof
integerprogrammingmethodstondoptimalmappings.Asopposedtostandardapproaches
intheliterature,wenotonlyaimatbalancingcomputationalloadovertheprocessors,but
alsoconsidercommunicationoverheadinducedbydatadependenciesbetweenblocksmapped
todierentprocessors.Thecommunicationmodelweapplyisanexactrepresentationof
therestrictionsourhardwareimposesoninter-processorcommunication.
Seekingtominimisesimulationtimeleadstoahighlycomplexcombinatorialoptimisation
problemthesolutionofwhichistheaimofourwork.Tothisendweformulatetheproblem
asintegerprogram.Sinceitisanewproblemthathas–tothebestofourknowledge–
notbeeninvestigatedintheliteraturewedonotstickwithasingleoptimisationmodel.
Instead,weproposedierentformulationsandconsidertradeosbetweenthem.Finally,
weinvestigatethepolyhedradenedbythevariousintegerprogramsinordertoimplement
thevalidandfacet-deninginequalitiesfoundinBranch-and-Cutalgorithms.Aswecannot
expecttosolvelargeprobleminstancesbyintegerprogrammingmethodsinanacceptable
amountoftime,wealsodevelopseverallocal-searchheuristicsthatproducegoodsolutions
inareasonableamountoftime.

Computationalresultsshowthatourmodelsandsolutionalgorithms–bothofwhichare
dedicatedtoacertainhardwaremodel–arehighlysuperiortogenericapproachesdescribed
intheliterature.WewerethusabletoimprovetheusageofCPUresourcesduringsimulation
ofturbulentowsincomplexgeometries.Letusnallyremarkthatourapproachisnot
limitedtothisconcreteapplicationofnite-elementornite-volumeprocedures.Insteadit
canbeappliedinanysituationswheresmallorblockstructuredgridsariseandthehardware
modelisatleastsimilartotheoneassumedinourwork.

Zusammenfassung

DieSimulationturbulenterStro¨mungeninkomplexenGeometrienerfolgtheutemeistens
durchdenEinsatzvongitterbasiertenLo¨sungsalgorithmenaufParallelrechnern.Dabei
kommtesnichtalleinedaraufan,einemo¨glichstgeschickteDiskretisierungbzw.einmo¨glichst
geeignetesGitterauszuwa¨hlenodernumerischstabileundkonvergenteAlgorithmenzuent-
wickeln.Insbesonderemu¨ssendieeinzelnenArbeitspaketederSimulationsoaufdiegegebe-
nenProzessorenverteiltwerden,dassdieRechnerressourcenoptimalausgenutztwerden,d.h.
dieSimulationinminimalerZeitabla¨uft.
DieArbeitkonzentriertsichaufdiesesletzteOptimierungsproblemundentwickeltdafu¨r
ModellesowieLo¨sungsmethoden.Dazunehmenwiran,dassfu¨rdieSimulationbereitsein
blockstrukturiertesGittergewa¨hltwurdeundsuchennacheineroptimalenVerteilungder
einzelnenGitterelementeaufdievorhandenenProzessoren.DieBeschra¨nkungaufblock-
strukturierteGittererfolgt,dadieserstensderinderSimulationturbulenterStro¨mungenin
komplexenGeometrienamha¨ugsteneingesetzteGittertypistundzweitensGitterdieses
Typsineineu¨berschaubareMengevonBlo¨ckenzerlegtwerdenko¨nnen,sodasszurBerech-
nungeineroptimalenVerteilungdesGittersMethodenderganzzahligenProgrammierung
verwendetwerdenko¨nnen.ImGegensatzzudenu¨blichenAnsa¨tzenausderLiteratur
achtenwirbeiZuordnungvonArbeitspaketenanProzessorennichtnuraufeinegleichma¨ßige
VerteilungderRechenlast,sondernbetrachtenauchexaktdenZusatzaufwand,dersichfu¨r
einbestimmtesHardwaremodelldurchDatenaustauschzwischenverschiedenenProzessoren
wa¨hrendderSimulationergibt.
DieseFragestellungfu¨hrtunsaufeinhochkomplexeskombinatorischesOptimierungsprob-
lem,dessenLo¨sungdasZielunsererArbeitist.ZudiesemZweckformulierenwirdasProblem
alsganzzahligeslinearesProgramm.DaessichumeininderPraxisunseresWissensbisher
nichtuntersuchtesProblemhandelt,beschra¨nkenwirunsnichtaufeineFormulierung,son-
dernstellenverschiedeneFormulierungenvorundwa¨gendiesegegeneinanderab.Schließlich
untersuchenwirdiedurchdieganzzahligenProgrammede