Efficient multigrid algorithms for locally constrained parallel systems

摘要

By means of simple model problems, the speedup and efficiency are investigated that can be obtained by a parallelization of multigrid methods for systems of many independent processors that are coupled via common local memories. Trees and nearest-neighbor systems are studied as computer structures. Among multigrid methods we investigate the basic multigrid method (V-cycle, W-cycle) and the full multigrid method. Parallelization is realized by an appropriate projection of the problem on the computer system. For transferring data between nondirectly connected processors, the overlapping of transfers and the specific distance between source and target are considered. First, we discuss an asymptotic relation between the problem size and the system size. For obtaining efficient algorithms, the problem must be sufficiently oversized. In many cases we are thus able to obtain the asymptotically optimal speedup with positive efficiency. Finally, we discuss the relations between problem size, system size, and efficiency by means of a numerical evaluation of an analytical model for those system parameter values that include the advanced possibilities of constructing large parallel systems.