Algebraic multigrid (AMG) is often viewed as a scalable solver for sparse linear systems. Yet, AMG lacks parallel scalability due to increasingly large costs associated with communication, both in the initial construction of a multigrid hierarchy and in the iterative solve phase. This work introduces a parallel implementation of AMG that reduces the cost of communication, yielding improved parallel scalability. It is common in Message Passing Interface (MPI), particularly in the MPI-everywhere approach, to arrange inter-process communication, so that communication is transported regardless of the location of the send and receive processes. Performance tests show notable differences in the cost of intra- and internode communication, motivating a restructuring of communication. In this case, the communication schedule takes advantage of the less costly intra-node communication, reducing both the number and the size of internode messages. Node-centric communication extends to the range of components in both the setup and solve phase of AMG, yielding an increase in the weak and strong scaling of the entire method.
AdamsMFBayraktarHHKeavenyTM, et al. (2004) Ultrascalable implicit finite element analyses in solid mechanics with over a half a billion degrees of freedom. In: SC ‘04: Proceedings of the 2004 ACM/IEEE Conference on Supercomputing, 6–12 November 2004, pp. 34–34. IEEE. DOI:10.1109/SC.2004.62.
2.
AlOnaziAMarkomanolisGSKeyesD (2017) Asynchronous task-based parallelization of algebraic multigrid. In: Proceedings of the platform for advanced scientific computing conference, PASC ‘17. ISBN 978-1-4503-5062-4, 26–28 June 2017, pp. 5:1–5:11. New York, NY, USA: ACM. DOI:10.1145/3093172.3093230.
3.
BakerAHGamblinTSchulzM, et al. (2011) Challenges of scaling algebraic multigrid across modern multicore architectures. In: Proceedings of the 2011 IEEE international parallel & distributed processing symposium, IPDPS ‘11. ISBN 978-0-7695-4385-7, 16–20 May 2011, pp. 275–286. Washington, DC, USA: IEEE Computer Society. DOI:10.1109/IPDPS.2011.35.
4.
BakerAHSchulzMYangUM (2011) On the performance of an algebraic multigrid solver on multicore clusters. In: PalmaJMLMDaydéMMarquesOLopesJC (eds) High Performance Computing for Computational Science—VECPAR 2010. Berlin, Heidelberg: Springer Berlin Heidelberg. ISBN 978-3-642-19328-6, pp. 102–115.
5.
BhateleAKaleLV (2008) Application-specific topology-aware mapping for three dimensional topologies. In: 2008 IEEE international symposium on parallel and distributed processing, 14–18 April 2008, pp. 1–8. IEEE. DOI:10.1109/IPDPS.2008.4536348.
6.
BhateleAGamblinTLangerSH, et al. (2012) Mapping applications with collectives over sub-communicators on torus networks. In: Proceedings of the International conference on high performance computing, networking, storage and analysis, SC ‘12. ISBN 978-1-4673-0804-5, pp. 97:1–97:11. Los Alamitos, CA, USA: IEEE Computer Society Press. DOI:10.1109/SC.2012.75.
7.
BienzAOlsonLN (2017) RAPtor: parallel algebraic multigrid v0.1. Available at:https://github.com/lukeolson/raptor. Release 0.1 (accessed February 2019).
8.
BienzAFalgoutRDGroppW, et al. (2016) Reducing parallel communication in algebraic multigrid through sparsification. SIAM Journal on Scientific Computing38(5): S332–S357.
9.
BienzAGroppWDOlsonLN (2018) Improving performance models for irregular point-to-point communication. In: Proceedings of the 25th European MPI Users’ Group Meeting, Barcelona, Spain, 23–26 September 2018, pp. 7:1–7:8. Association for Computing Machinery. DOI:10.1145/3236367.3236368.
10.
BienzAGroppWDOlsonLN (2019) Node aware sparse matrix-vector multiplication. Journal of Parallel and Distributed Computing130: 166–178. DOI:10.1016/j.jpdc.2019.03.016.
11.
BodeBButlerMDunningT, et al. (2013) The Blue Waters super-system for super-science. In: VetterJS (ed) Contemporary High Performance Computing: From Petascale Toward Exascale, CRC Computational Science Series, Vol. 1. 1st ed. Boca Raton: Taylor and Francis, pp. 339–366. ISBN 9781466568341.
12.
BrandtAMcCormickSFRugeJW (1984) Algebraic multigrid (AMG) for sparse matrix equations. In: EvansDJ (ed) Sparsity and Its Applications. Cambridge: Cambridge Univ. Press, pp. 257–284.
13.
ÇatalyürekUVAykanatC (1999) Hypergraph-partitioning-based decomposition for parallel sparse-matrix vector multiplication. IEEE Transactions on Parallel and Distributed Systems10(7): 673–693.
14.
ÇatalyürekUVAykanat C (2010) On two-dimensional sparse matrix partitioning: models, methods, and a recipe. SIAM Journal on Scientific Computing32(2): 656–683.
15.
FalgoutRDSchroderJB (2014) Non-Galerkin coarse grids for algebraic multigrid. SIAM Journal on Scientific Computing36(3): C309–C334.
16.
GroppWLuskEDossN, et al. (1996) A high-performance, portable implementation of the MPI message passing interface standard. Parallel Computing22(6): 789–828. DOI:10.1016/0167-8191(96)00024-5.
17.
GroppWOlsonLNSamfassP (2016) Modeling MPI communication performance on SMP nodes: Is it time to retire the ping pong test. In: Proceedings of the 23rd European MPI Users’ Group Meeting, EuroMPI 2016. ISBN 978-1-4503-4234-6, pp. 41–50. New York, NY, USA: ACM. DOI:10.1145/2966884.2966919.
HensonVEYangUM (2002) BoomerAMG: A parallel algebraic multigrid solver and preconditioner. Applied Numerical Mathematics41(1): 155–177.
20.
HoeflerTTraffJL (2009) Sparse collective operations for MPI. In: 2009 IEEE international symposium on parallel distributed processing, Rome, Italy, 23–29 May 2009, pp. 1–8. IEEE. DOI:10.1109/IPDPS.2009.5160935.
21.
KaronisNTde SupinskiBRFosterI, et al. (2000) Exploiting hierarchy in parallel computer networks to optimize collective operation performance. In: Proceedings 14th international parallel and distributed processing symposium. IPDPS 2000, Cancun, Mexico, 1–5 May 2000, pp. 377–384. IEEE. DOI:10.1109/IPDPS.2000.846009.
22.
KielmannTHofmanRFHBalHE, et al. (1999) MagPIe: MPI’s collective communication operations for clustered wide area systems. SIGPLAN Not34(8): 131–140.
23.
Lawrence Livermore National Laboratory (LLNL) (2008) HYPRE: high performance preconditioners. Available at: http://www.llnl.gov/CASC/hypre/ (accessed February 2019).
24.
Lawrence Livermore National Laboratory (LLNL) (2010) MFEM: modular finite element methods. Available at: mfem.org (accessed February 2019).
25.
McCormickSFRugeJW (1982) Multigrid methods for variational problems. SIAM Journal on Numerical Analysis19(5): 924–929.
26.
MirsadeghiSTraffJBalajiP, et al. (2017) Exploiting common neighborhoods to optimize MPI neighborhood collectives. In: 2017 IEEE 24th international conference on high performance computing (HiPC), Jaipur, India, 18–21 December 2017, pp. 348–357. Los Alamitos, CA, USA: IEEE Computer Society.DOI:10.1109/HiPC.2017.00047.
PinarAAykanatC (2004) Fast optimal load balancing algorithms for 1D partitioning. Journal of Parallel and Distributed Computing64(8): 974–996.
29.
RugeJWStübenK (1987) Algebraic multigrid (AMG). In: McCormickSF (ed) Multigrid Methods, Frontiers in Applied Mathematics. Philadelphia: SIAM, pp. 73–130.
30.
SackPGroppW (2012) Faster topology-aware collective algorithms through non-minimal communication. In: Proceedings of the 17th ACM SIGPLAN symposium on principles and practice of parallel programming, PPoPP ‘12. ISBN 978-1-4503-1160-1, New Orleans, Louisiana, USA, 25–29 February 2012, pp. 45–54. New York, NY, USA: ACM.
31.
SolomonikEBhateleADemmelJ (2011) Improving communication performance in dense linear algebra via topology aware collectives. In: Proceedings of 2011 international conference for high performance computing, networking, storage and analysis, SC ‘11. ISBN 978-1-4503-0771-0, Seattle, WA USA, 12–18 November 2011, pp. 77:1–77:11. New York, NY, USA: ACM.
32.
SterckHDFalgoutRDNoltingJW, et al. (2008) Distance-two interpolation for parallel algebraic multigrid. Numerical Linear Algebra with Applications15(2-3): 115–139.
33.
SterckHDYangUMHeysJJ (2005) Reducing complexity in parallel algebraic multigrid preconditioners. SIAM Journal on Matrix Analysis and Applications27(4): 1019–1039.
34.
TreisterEYavnehI (2015) Non-Galerkin multigrid based on sparsified smoothed aggregation. SIAM Journal on Scientific Computing37(1): A30–A54.
35.
TuminaroRSTongC (2000) Parallel smoothed aggregation multigrid: aggregation strategies on massively parallel machines. In: Supercomputing, ACM/IEEE 2000 conference, Dallas, TX USA, 4–10 November 2000, pp. 5–5. IEEE. DOI:10.1109/SC.2000.10008.
36.
VassilevskiPSYangUM (2014) Reducing communication in algebraic multigrid using additive variants. Numerical Linear Algebra with Applications21(2): 275–296. DOI: 10.1002/nla.1928.
37.
VastenhouwBBisselingRH (2005) A two-dimensional data distribution method for parallel sparse matrix-vector multiplication. SIAM Review47(1): 67–95.
38.
WesolowskiLVenkataramanRGuptaA, et al. (2014) TRAM: Optimizing fine-grained communication with topological routing and aggregation of messages. In: 2014 43rd International Conference on Parallel Processing, Minneapolis, MN USA, 9–12 September 2014, pp. 211–220. IEEE. DOI:10.1109/ICPP.2014.30.
39.
YangUM (2010) On long-range interpolation operators for aggressive coarsening. Numerical Linear Algebra with Applications17(2–3): 453–472.
