I just implemented an Algebraic Multigrid solver for a Mixed Dirichlet-Neumann Boundary Value problem and was surprised to see the speed-up as compared to a simple iterative solver for a large problem like 2048x2048 and 4096x4096. My next step is to implement it in parallel. If Multigrid is so useful, I am sure people would like to (and have I think) implemented it for millions of processors. My question is : What are the challenges/bottlenecks in implementing Algebraic Multigrid on a large scale ? It will be extremely interesting to gain an insight into this to be able to produce a moderately optimised code at this stage.

  • 3
    $\begingroup$ There are many papers online about this including one titled Challenges of Scaling Algebraic Multigrid across Modern Multicore Architectures which has results up to 2e5 cores. Was there something specific you were wondering about that's not addressed in that (or similar) papers? There are only 2 computers in the world with 1M+ cores so "millions" might be asking to much at present. $\endgroup$ Jun 20 '15 at 0:01
  • $\begingroup$ Thank you @DougLipinski for pointing me towards the paper. I am in the process of reading it now. What I was looking for by posting this question was the practical experience of people who have tried to implement AMG on a large scale and discovered problems/bottlenecks/issues. For e.g. solving coarse grids is supposed to be inefficient on multiple processors. Such guidance can be extremely useful. I apologise for loosely writing millions of processors - i'll correct that. $\endgroup$ Jun 20 '15 at 2:32
  • $\begingroup$ @DougLipinski: As a small follow-up, I must say that the paper is pretty cryptic and the authors have made no attempts to 'teach' - its just a 'presentation' of what they did at a very high level and most of it is 'naming' of components of 'BoomerAMG'. Pardon my ability to understand the contents of this paper but, I still feel my question above is still valid. $\endgroup$ Jun 22 '15 at 11:17
  • $\begingroup$ Unfortunately it's not my area so I can't really answer your question, but I hope someone will. I only meant to suggest a paper that looked like it might be useful. There are some other papers that sound similar if you search for online for "massively parallel multigrid", perhaps one of those will be more useful. $\endgroup$ Jun 22 '15 at 11:26
  • $\begingroup$ @DougLipinski: Thanks again for your prompt reply and efforts ! $\endgroup$ Jun 22 '15 at 11:35

I am by no means an expert but I will share some challenges that I have heard of. One challenge is (and this may depend on how you chose your c-points) in order to avoid extensive communication between nodes you want your matrix to have a nice structure. For example lets say you are solving a finite element problem. Then you want your nodes to be ordered in such a way so that nodes that are geometrically close together are on the same processor. This will result in a matrix that has some kind of banded structure. This way when you are choosing your c-points every processor does not have to compare with every other processor (to determine which points should be cpoints and which should be f-points).

Another important issue is what happens as you coarsen your mesh. As you get to coarser and coarser meshes you will have to deal with load imbalancing. For example some processors might end up only containing fpoints by the time you get to very coarse grids. At these grid levels those nodes wont be doing anything. Meanwhile other nodes that might contain many cpoints and will be busy.

A lot of this has to do with how you choose your c-point/f-point grids but hopefully this helps. I actually just wrote my own AMG solver and came across the same issue when trying to parallelise. Good luck.

  • $\begingroup$ thank you for sharing. I totally agree with neighbours being on same node - close by, because the latency is appreciable over a number of iterations. Thanks for sharing, I am yet to experience it first hand - but soon I will :). $\endgroup$ Jun 28 '15 at 1:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.