It has been conjectured that higher-order discretizations for partial differential equations will have advantages over the lower-order counterparts commonly used today. The reasoning is that the increase in arithmetic operations will be more than offset by the reduction in data transfers and the increase in concurrent floating-point units. To evaluate this conjecture, the arithmetic intensity of a class of high-order finite-volume discretizations for hyperbolic systems of conservation laws is theoretically analyzed for spatial discretizations from orders three through eight in arbitrary dimensions. Three cache models are considered: the limiting cases of no cache and infinite cache as well as a finite-sized cache model. Models are validated experimentally by measuring floating-point operations and data transfers on an IBM Blue Gene/Q node. Theory and experiments demonstrate that high-order finite-volume methods will be able to provide increases in arithmetic intensity that will be necessary to make better utilization of on-node floating-point capability.
(2012) BGPM - BG/Q Hardware Perf Monitoring API. International Business Machines Corporation.
2.
AdamsMColellaPGravesD. (2014) Chombo software package for AMR applications – design document. Technical report LBNL-6616E, Lawrence Berkeley National Laboratory, CA.
3.
AshbySBeckmanPChenJ. (2010) The opportunities and challenges of exascale computing. Technical report, U.S. Department of Energy Advanced Scientific Computing Advisory Committee, Washington, DC.
4.
BallardGCarsonEDemmelJ. (2014) Communication lower bounds and optimal algorithms for numerical linear algebra. Acta Numerica23: 1–155.
5.
BasuPHallMWilliamsS. (2015) Compiler-directed transformation for higher-order stencils. In: 29th annual IEEE international parallel and distributed processing symposium (ed O’ConnerL), Hyderabad, India, 25–29 May 2015, pp.313–323. Los Alamitos, CA, USA: IEEE Computer Society Conference Publishing Services.
6.
BellJAlmgrenABecknerV. (2013) BoxLib User’s Guide. Center for Computational Sciences and Engineering, Lawrence Berkeley National Laboratory, CA.
7.
Bermejo-MorenoIBodartJLarssonJ. (2013) Solving the compressible Navier-Stokes equations on up to 1.97 million cores and 4.1 trillion grid points. In: SC `13 Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis, (eds GroppWMatsuokaS), Denver, CO, 17–21 November 2013, pp.62:1–62:10. New York, NY, USA: ACM.
8.
BhateléAWesolowskiLBohmE. (2010) Understanding application performance via micro-benchmarks on three large supercomputers: Intrepid, Ranger and Jaguar. The International Journal of High Performance Computing Applications24(4): 411–427.
9.
BohrM (2007) A 30 year retrospective on Dennard’s MOSFET scaling paper. IEEE Solid-State Circuits Society Newsletter12(1): 11–13.
10.
BorisJPBookDL (1973) Flux-corrected transport. I. SHASTA, a fluid transport algorithm that works. Journal of Computational Physics11: 38–69.
11.
CallahanDCockeJKennedyK (1988) Estimating interlock and improving balance for pipelined architectures. Journal of Parallel and Distributed Computing5(4): 334–358.
12.
CarrSKennedyK (1994) Improving the ratio of memory operations to floating-point operations in loops. ACM Transactions on Programming Languages and Systems16(6): 1768–1810.
13.
ChaplinCColellaP (2017) A single stage flux-corrected transport algorithm for high-order finite-volume methods. Communications in Applied Mathematics and Computational SciencearXiv: 1506.02999.
14.
ChenGChacónLBarnesDC (2012) An efficient mixed-precision, hybrid CPU-GPU implementation of a nonlinearly implicit one-dimensional particle-in-cell algorithm. Journal of Computational Physics231(16): 5374–5388.
15.
ColellaPWoodwardPR (1984) The piecewise parabolic method (PPM) for gas-dynamical simulations. Journal of Computational Physics54(1): 174–201.
16.
ColellaPDorrMRHittingerJAF. (2011) High-order, finite-volume methods in mapped coordinates. Journal of Computational Physics230(8): 2952–2976.
17.
DongarraJHittingerJBellJ. (2014) Applied mathematics research for exascale computing. Technical report, Advanced Scientific Computing Research Program, U.S. Department of Energy Office of Science, Washington, DC.
18.
GodenschwagerCSchornbaumFBauerM. (2013) A framework for hybrid parallel flow simulations with a trillion cells in complex geometries. In: SC `13 Proceedings of the international conference on high performance computing, networking, storage and analysis (eds GroppWMatsuokaS), Denver, CO, USA, 17–21 November 2013, pp.35:1–35:12. New York, NY, USA: ACM.
19.
GolubGVan LoanC (2012) Matrix Computations (Johns Hopkins Studies in the Mathematical Sciences). Baltimore, MD: Johns Hopkins University Press.
HejazialhosseiniBRossinelliDContiC. (2012) High throughput software for direct numerical simulations of compressible two-phase flows. In: SC `12 Proceedings of the international conference on high performance computing, networking, storage and analysis (ed HollingsworthJ), Salt Lake City, UT, USA, 11–15 November 2012, pp.1–12. New York, NY, USA: ACM.
22.
HornungRDKohnSR (2002) Managing application complexity in the SAMRAI object-oriented framework. Concurrency and Computation14: 347–368.
23.
IdomuraYJollietS (2011) Performance evaluations of gyrokinetic Eulerian code GT5D on massively parallel multi-core platforms. In: State of the practice reports, pp. 4:1–4:9.
24.
JiangGSShuCW (1996) Efficient implementation of weighted ENO schemes. Journal of Computational Physics126(1): 202–228.
25.
Jia-WeiHKungHT (1981) I/O complexity: The red-blue pebble game. In: Proceedings of the thirteenth annual ACM symposium on theory of computing (ed RivestR), Milwaukee, Wisconsin, USA, 11–13 May 1981, pp.326–333. New York, NY, USA: ACM.
26.
KreissHOOligerJ (1972) Comparison of accurate methods for the integration of hyperbolic equations. Tellus24(3): 199–215.
27.
LangguthJWuNChaiJ. (2013) On the GPU performance of cell-centered finite volume method over unstructured tetrahedral meshes. In: Proceedings of the 3rd workshop on irregular applications: Architectures and algorithms (eds TumeoAFeoJVillaOSecchiS.), Denver, CO, USA, 17–21 November 2013, pp.7:1–7:8. New York, NY, USA: ACM.
LucasRAngJBergmanK. (2014) Top ten exascale research challenges. Technical report, U.S. Department of Energy Advanced Scientific Computing Advisory Committee, Washington, DC.
30.
McCorquodalePColellaP (2011a) A high-order finite volume method for conservation laws on locally refined grids. Communications in Applied Mathematics and Computational Science6(1): 1–25.
31.
McCorquodalePDorrMRHittingerJAF. (2015) High-order finite-volume methods for hyperbolic conservation laws on mapped multiblock grids. Journal of Computational Physics288: 181–195.
32.
OlschanowskyCStroutMMGuzikS. (2014) A study on balancing parallelism, data locality, and recomputation in existing PDE solvers. In: SC `14 Proceedings of the international conference on high performance computing, networking, storage and analysis (eds DamkrogerTDongarraJ), New Orleans, LA, USA, 16–21 November 2014, pp.793–804. New York, NY, USA: ACM.
33.
PananilathIAcharyaAVasistaV. (2015) An optimizing code generator for a class of lattice-Boltzmann computations. ACM Transactions on Architecture and Code Optimization12(2): 14:1–14:23.
34.
RossinelliDHejazialhosseiniBHadjidoukasP. (2013) 11 pflop/s simulations of cloud cavitation collapse. In: SC `13 Proceedings of the international conference on high performance computing, networking, storage and analysis (eds GroppWMatsuokaS), Denver, CO, USA, 17–21 November 2013, pp.3:1–3:13. New York, NY, USA: ACM.
35.
RossinelliDHejazialhosseiniBSpampinatoDG. (2011) Multicore/multi-GPU accelerated simulations of multiphase compressible flows using wavelet adapted grids. SIAM Journal on Scientific Computing33(2): 512–540.
36.
ShuCW (1997) Essentially non-oscillatory and weighted essentially non-oscillatory schemes for hyperbolic conservation laws. Technical report ICASE-97-65, NASA, Washington, DC.
37.
SimJDasguptaAKimH. (2012) A performance analysis framework for identifying potential benefits in GPGPU applications. SIGPLAN Notices47(8): 11–22.
38.
StengelHTreibigJHagerG. (2015) Quantifying performance bottlenecks of stencil computations using the execution-cache-memory model. In: Proceedings of the 29th ACM on international conference on supercomputing (eds BhuyanLNChongFSarkarV), Newport Beach, CA, USA, 8–11 June 2015, pp.207–216. New York, NY, USA: ACM.
39.
WilliamsSCarterJOlikerL. (2009a) Optimization of a lattice Boltzmann computation on state-of-the-art multicore platforms. Journal of Parallel and Distributed Computing69(9): 762–777.
40.
WilliamsSOlikerLCarterJ. (2011) Extracting ultrascale lattice Boltzmann performance via hierarchical and distributed auto-tuning. In: SC `11 Proceedings of the international conference on high performance computing, networking, storage and analysis (eds LathropSCostaJKramerW) Seattle, WA, USA, 12–18 November 2011, pp.55:1–55:12. New York, NY, USA: ACM.
41.
WilliamsSWatermanAPattersonD (2009b) Roofline: An insightful visual performance model for multicore architectures. Communications of the ACM52(4): 65–76.
42.
YokotaRBarbaLA (2012) Hierarchical n-body simulations with autotuning for heterogeneous systems. Computing in Science & Engineering14(3): 30–39.
43.
ZalesakST (1979) Fully multidimensional flux-corrected transport algorithms for fluids. Journal of Computational Physics31(2): 335–362.
44.
ZhangWWeiWCaiX (2014) Performance modeling of serial and parallel implementations of the fractional Adams-Bashforth-Moulton method. Fractional Calculus and Applied Analysis17(3): 617–637.
