Language and Compiler Support for Adaptive Mesh RefinementMultiscale Modeling ProblemsBlock-Structured AMRA Layered Attack on These ProblemsAlgorithms for AMR3D AMR Gas Dynamics3D AMR PoissonMLC for Finite-DifferencesSlide 9Accuracy of the MLC for FDError on High-Wavenumber ProblemSlide 12Java for Scientific ComputingJava ObjectsJava Object ExampleImmutable Classes in TitaniumArrays in JavaMultidimensional Arrays in TitaniumUnordered iterationLaplacian ExampleSequential PerformanceSlide 22SPMD ModelBuilding Distributed Data StructuresGlobal Address SpaceSlide 26Slide 27Local Pointer AnalysisParallel OptimizationsSemantics: Sequential ConsistencyCycle Detection: Dependence AnalogCycle DetectionStatic Analysis for Cycle DetectionAutomatic Communication OptimizationParallel performanceScalable Poisson Solver (MLC)Slide 37SparsitySparsity PerformanceSlide 40Slide 41ArchitectureSummaryYelick 1AMR & TitaniumLanguage and Compiler Support for Adaptive Mesh RefinementKatherine Yelick Alex Aiken, Greg Balls, Dan Bonachea, Phillip Colella, David Gay, Susan Graham, Paul Hilfinger, Arvind Krishnamurthy, Ben Liblit, Chang Sun Lin, Peter McCorquodale, Carleton Miyamoto, Geoff Pike, Kar Ming Tang, Siu Man YauYelick 2AMR & TitaniumMultiscale Modeling Problems•Many modeling problems in astrophysics, biology, material science, and other areas require –Enormous range of spatial and temporal scales•To solve interesting problems, one needs:–Adaptive methods–Large scale parallel machines•For Computational Fluid Dynamics, a popular technique is–Adaptive Mesh Refinement (AMR)Yelick 3AMR & TitaniumBlock-Structured AMR•Algorithms for many rectangular, grid-based computations are–communication intensive–memory intensive•AMR makes these harder–more small messages –more complex data structures–most of the programming effort is debugging the boundary cases–locality and load balance trade-off is hardYelick 4AMR & TitaniumA Layered Attack on These Problems•Algorithms•Languages: Titanium–Java dialect compiled to C–Extensions for serial programming–Extensions for parallel programming •Compilers–Uniprocessor optimizations–Communication optimizations•Libraries–Automatic tuning of kernels•ArchitectureYelick 5AMR & TitaniumAlgorithms for AMR•Existing algorithms in Titanium–3D AMR Poisson solver–3D AMR Gas dynamics–Domain-decomposition MLC Poisson•Under development–Self-gravitating gas dynamics (3D AMR)»For stellar collapse, etc.–Immersed boundary method (3D, non-adaptive)»Peskin and MacQueen’s method for heart model, etc.–Embedded boundaries»Simulation of bio-MEMs devices and cellular level modeling•All joint with Colella’s group at LBNLYelick 6AMR & Titanium3D AMR Gas Dynamics•Hyperbolic Solver [McCorquodale and Colella]–Implementation of Berger-Colella algorithm–Mesh generation algorithm included•2D Example (3D supported) –Mach-10 shock on solid surface at oblique angle•Future: Self-gravitating gas dynamics packageYelick 7AMR & Titanium3D AMR Poisson•Poisson Solver [Semenzato, Pike, Colella]–finite domain–variable coefficients–multigrid across levels •Currently synthetic grids, no grid generation•Under construction–reengineered to interface with hyperbolic solver–including mesh generationLevel 0Level 2Level 1Yelick 8AMR & TitaniumMLC for Finite-Differences•Poisson solver with infinite domains [Colella, Balls]–Uses a Method of Local Corrections (MLC)–Currently non-adaptive and 2D–Supports only constant coefficients•Uses 2-level, domain decomposition approach–Fine-grid solutions are computed in parallel –Information transferred to a coarse-grid and solved serially–Fine-grid solutions is computed using boundary conditions from the coarse grid•Future work includes 3D Adaptive versionYelick 9AMR & TitaniumMLC for Finite-Differences•Features of the method–Solution is still second-order accurate–Accuracy depends only weakly on the coarse-grid spacing•Scalability–No communication during fine-grid solves–Single communication step (global all-to-all)–coarse grid work is serial (replicated), but relatively small•Future work: extend to 3D and adaptive meshesYelick 10AMR & TitaniumAccuracy of the MLC for FD2.02e-88.25e-8842572.302.424.12e-91.67e-81645132.182.325.05e-91.96e-8845132.062.235.26e-92.01e-8825132.062.225.32e-92.02e-8425131.77e-87.23e-81642572.13e-88.51e-8822572.18e-88.61e-842257L2 ConvergenceMax ConvergenceL2 ErrorMax ErrorNrNpGrid Size•Solution is second-order accurate–decreasing h by 2x, decreases error by ~4xYelick 11AMR & TitaniumError on High-Wavenumber Problem•Charge is–1 charge of concentric waves –2 star-shaped charges.•Largest error is where the charge is changing rapidly. Note:–discretization error–faint decomposition error•Run on 16 procs -6.47x10-9 0 1.31x10-9Yelick 12AMR & TitaniumA Layered Attack on These Problems•Algorithms•Languages: Titanium–Java dialect compiled to C–Extensions serial programming–Extensions for parallel programming •Compilers–Uniprocessor optimizations–Communication optimizations•Libraries–Automatic tuning of kernels•ArchitectureYelick 13AMR & TitaniumJava for Scientific Computing•Computational scientists work on increasingly complex models–Popularized C++ features: classes, overloading, pointer-based data structures•But C++ is very complicated–easy to lose performance and readability•Java is a better C++–Safe: strongly typed, garbage collected–Much simpler to implement (research vehicle)–Industrial interest as well: IBM HP JavaYelick 14AMR & TitaniumJava Objects•Primitive scalar types: boolean, double, int, etc.–implementations store these in place–access is fast -- comparable to other languages•Objects: user-defined and library–passed by pointer value –has level of indirection (pointer to) implicit–simple model, but inefficient for small objects2.63truer: 7.1i: 4.3Complex objectYelick 15AMR & TitaniumJava Object Exampleclass Complex { private double real; private double imag; public Complex(double r, double i) { real = r; imag = i; } public Complex operator+(Complex c) { return new Complex(c.real + real, c.imag + imag); } public double getReal {return real; } public
View Full Document
Unlocking...