Which is better between 1D and 2D partitioning in matrix operations and how is it better? I have looked for how both partitions work but still couldn’t find which one is better. Can anyone please help me..
For distributed computation of sparse matrices, 2D partitioning is shown to be more scalable than 1D partitioning [1]. Having p processes, if you create a two dimensional grid of p^2 tiles, a 2D partitioning such as 2D-cyclic limits the communication of a row/column group of tiles to sqrt(p) processes whereas, e.g., 1D-column has to communicate with p processes for row group communication and no other process for column group communication. Therefore, 1D-column speedup is bound to a larger communication time which is a factor of p.
[1] Buluc, Aydin, and John R. Gilbert. Linear algebraic primitives for parallel computing on large graphs. University of California, Santa Barbara, 2010.