Data Structures For Scientific Computing

Data Structuresfor Scientific ComputingOrion Sky Lawlorwww.cs.uaf.edu2011/04/141

OverviewIntroduction and Motivation Structured Grids Unstructured Grids Adaptive structured gridsAdaptive unstructured gridsParticles and Spatial SearchRegular grids Trees 2

Introduction / Motivation There are only a few ways torepresent the problem domain:Structured Grids Unstructured Grids Particles Knowing the basic terms helpsyou talk to application folks,and understand their code3

Grids in General4

Grids: IntroductionSo you’re trying to representsome physical situation, likeheat flow You decide to divide up spaceinto a bunch of little pieces: Node, orVertex, orPointElement, orCell, orVolume5

Grids: Location of Data Element Centered Data Fluid Dynamics, most PDEsData valuesconstant (orsimple) in a cell Node Centered Data Structural dynamics/FEMHybrids too,likeArakawa C-grid“Shape function”interpolatesbetween nodes6

Grids: Motion of Grid and Data Eulerian: non-moving grid E.g., pressure waves move throughthe grid in CFDLagrangian: moving grid E.g., grid deformation follows thestructure deformation in FEMOr hybrid,7 e.g. “ALE”

Structured Grids8

Structured Grids: Introduction AKA “Regular Grid”, since grid cellslie in regular rows and columnsCells are stored in a 3D arrayCells can lie along axes (“rectilineargrid”); or curve through spaceYX9

Structured Grids: Terminology “Stencil” of source cells to compute adestination cell Classic GPU algorithmjCommon in fluid dynamics Also found in PDE solversx iRead-only “Ghost” or “Dummy”cells around boundaryji10

Structured Grids: Applications Fluid Dynamics Jacobi and other PDE solvers “Finite Difference” formulationLevel set methods Classical fluid dynamics gridE.g., fluid solidification phase fieldImage processing Just a 2D pixel array!11

Adaptive Structured Grids12

Adaptive Structured Grids: Intro “Adaptive Mesh Refinement”/AMRCells are stored in small 3D arrays,linked together with pointersFor regular refinement, use quadtree(2D) or octree (3D); can be irregular“block structured AMR”13from LLNL SC98 SAMRAI flier

Adaptive Structured Grids: Terms “Refinement” and “Coarsening” criteriacontrol evolution of mesh Basically simulation error estimates“Hanging Node Constraint” Neighbors must have similar ( 1)refinement levelbad!14

Adaptive Structured Grids: AppsAdaptive physics solvers LLNL SAMRAI C Framework NASA GSFC PARAMESH AMRITA (James Quirk) INRIA GPU Gems 3:5 15

Unstructured Grids16

Unstructured Grids: Introduction AKA “Mesh”Cells are stored in 1D arrayVertices (“nodes”) of each cell(“element”) are listed explicitlyMesh consists of trianglesand/or quadrilaterals (2D);tetrahedra, cubes/hexahedra,prisms, pyramids (3D)17

Unstructured Grids: Terms “Ghost regions”, like structured grids“Shared nodes” along partitionboundaries: Runcomputationon separatepieces Add up nodeforces alongboundaries18

Unstructured Grids: Terms “Conformality” Nodes never land in middle of elementEnforced during meshgeneration/modificationbad!19

Unstructured Grids: Applications Structural Mechanics Fluid Dynamics This is the classic finite elementmeshIn strange domains, wherestructured grids are tough toautomatically generateCan be extended to AdaptiveMeshes!20

Adaptive Unstructured Grids21

Adaptive Unstructured Grids: Intro AKA “Mesh Refinement”, shades intofrom-scratch “Mesh Generation”Cells still stored in 1D arrays, but thecells can now changeMust respect conformalityMust ensure element “quality”Must work in parallel22

Adaptive Meshes: Terminology “Delaunay” mesh and “flip” “Edge bisection”: cut edge inmiddle23

Adaptive Meshes: Applications Almost every unstructured meshprogram wants to be adaptive.Charm Triangle MeshRefinement (Wilmarth) Charm PMAF3D (Wilmarth) Charm Tet Data TransferLibrary (Lawlor) 24

Particle Methodsand Spatial Search25

Particles and Spatial Search To work on a particle, you neednearby particles E.g., all particles within cutoff r Used for molecular dynamics (NAMD) or, all k nearest particles Used by Smoothed ParticleHydrodynamics (SPH) methods Search for neighboring particlesis spatial, so need a “spatialsearch structure” Can use: structured grid, adaptive26search tree, unstructured grid,.

. using Structured Grids E.g., NAMD molecular dynamicsParticles are Atoms Search structure is based on“Patches” of space in regular,rectilinear grid atomsoverhere. .never talkto atomsover hereE.g., Charm Collision Library Search structure is based onregular rectilinear voxel grid27

. using Search Trees E.g., Cosmology simulationsParticles are stars, galaxies Search structure is a spatial octree SPH: “Smoothedparticlehydrodynamics” Barnes-Hutgravity “Tree walk” 28

Conclusions29

Conclusions There are only a few ways torepresent the problem domain:Structured Grids Unstructured Grids Particles There are a lot of specializedterms, but very few concepts30

Apr 14, 2011 · 26 Particles and Spatial Search To work on a particle, you need nearby particles E.g., all particles within cutoff r Used for molecular dynamics (NAMD) or, all k nearest particles Used by Smoothed Particle Hydrodynamics (SPH) methods Search for neighboring particles is spatial, so need a “spatial search structure”