This is the layout that we will use for Gaussian elimination. There is one more layout shown, the Block Skewed Layout , which is not a special case of 2D Block Cyclic Layout. This layout has feature that each row and each column is shared among all p processors, so p-fold parallelism is available for any row operation or any column operation. The Block Skewed Layout is not useful for Gaussian elimination, but can be useful in a variety of other matrix operations, so we mention it here. The following figure shows how the BLAS3 algorithm is performed on a 2D block cyclic layout.
Shaded regions indicate busy processors or communication performed.
It is unnecessary to have a barrier between each step of the algorithm. In other words, there can be parallelism with some steps of the algorithm forming a pipeline. To view the top level routine that performs Gaussian elimination, pdgetrf.f, click here . We assume no collective communications like broadcasts are available. It turns out these account for almost all of words and flops, which are the most important terms for large n.