Attacking the problem of scalability in parallel Gauss-Seidel and Jacobi solvers for mixed model equations
Per Madsen, Martin Larsen · Bulletin - International Bull Evaluation Service/Interbull bulletin · 1999
The history of the CEBUS project and some of its early experiences was described in: “The CEBUS project: History and overview” by Larsen and Madsen (This workshop). Test of the second implementation showed that parallel speedup could be achieved, but communication among the processors could limit the parallel speedup substantially. An analysis of amount and pattern of communication indicates that it should be possible to reduce communication at the expense of a little more computation. This is achieved in a third implementation by splitting the MMEs in a local and a global subset, as described below. Common to all tree implementations are the following: To obtain data parallelism (DP), records are sorted according to level codes of one of the effects in the model. Typically effects as herd-year-season or management group is used to obtain DP. Initially the master processor distributes disjoint sets of records to the slave processors. In the same pass through data, diagonal blocks for all effects except the one used to obtain DP are built, inverted and stored. In every round of iteration, each slave processor processes its part of the data, solve for the DP effect by Gauss-Seidel and accumulate contributions to the corrected right hand sides for all other effects in a local vector. When all data has been processed a complete corrected right hand side (crhs) can be build by summing over processors. In the first two implementations a global reduce operation was used to obtain the global crhs. In the third implementation only a small subset of the global crhs is needed. Each processor then solves for a part of the remaining effects by second order Jacobi. The third implementation is characterised by a split of the system in equations within a processor (local equations) and equations across processors (global equations). The local equations only receive contributions from data on the processor in question, while the global equations receive contributions from data on more than one processor. This approach has been programmed, and test runs on models of dimensions between 1.2 and 30.1 mio. equations has shown close to linear scalability and in some cases super linear scalability.