Parallel and adaptive algorithms for problems in scientific and medical computing (multiprocessor, parabolic partial, differential equation, iterative, sor, communication)
Joel Haskin Saltz · 1985
Methods are proposed and explored which allow the efficient computation of numerical algorithms on a wide variety of Multiple Instruction Multiple Datastream (MIMD) machines. A number of techniques are advanced to reduce the detrimental effects of interprocessor communication delays and suboptimal balancing of computational load on algorithm performance. The model problem examined concerns finding the time-accurate solution to a linear time dependent partial differential equation discretized in space and implicitly marched forward in time. Much of what is presented is directly applicable to the solving of elliptic partial differential equations. The algorithms investigated are iterative methods that are extensions of block Jacobi and SOR. The techniques proposed and explored are used in a number of different ways to reduce the effect of the obstacles to efficient utilization of multiprocessors. Iterations are performed over a window of several timesteps. It is proved that windowing has no effect on asymptotic convergence rates. In each processor, the solution of the equations required to advance particular variables over an iteration is treated as an independently schedulable subtask. Three subtask selection strategies for scheduling subtasks are proposed. Methods are given for efficiently computing the potential work that cold be performed by each processor in the absence of new input from other processors. Simulations described in this dissertation examine the use of combinations of the techniques of: (a) windowing, (b) independently scheduling subtasks within a processor and (c) estimation of potential work in the facilitation of efficient computation in multiprocessor systems. The first two techniques listed are useful in ameliorating the effects of communication delays and in obtaining high fractions of the available computational resources in multiprogrammed multiprocessors. Load balancing methods utilizing potential work calculations are proposed. Responsibility for computations updating the values of sets of variables shift in response to gradients in potential work. Simulations explore the situations under which these load balancing methods can reduce the work required to complete a problem. The load balancing methods are strongly dependent on the ability to independently schedule subtasks. These methods increase in efficiency as window sizes increase.