Data allocation strategies for the Gauss and Jordan algorithms on a ring of processors (Q1823615)

The problem is to determine the allocation function minimizing the total time complexity defined as the sum of the arithmetic time and the communication time for the parallel implementation of the Gauss and Jordan elimination methods on a ring of processors. It is supposed that no overlap occurs between computations and communications. The asymptotic optimality of the block repartition is proved for the Jordan elimination. Its efficiency is \(e_{\alpha}=1/[1+\alpha (1+\alpha)\rho],\) where \(\rho\) is the ratio of the elemental communication/computation costs for a problem of size n with \(p=\alpha n\) processors, \(0<\alpha \leq 1\). Various allocation functions are considered for the Gauss elimination, where data are wrapped among the processors by blocks of size r. The execution time for Gauss elimination is proved as a function of \(\alpha\) and \(\rho\). The value of r which is optimal and the efficiency for a block-r repartition are derived. The agreement of the theoretical results with the numerical experiments on a hypercube is pointed out.