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.
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.