Implementation of a fully balanced periodic tridiagonal solver on a parallel distributed memory architecture

Publisher Website
Google Scholar
Abstract
While parallel computers offer significant computational performance, it is generally necessary to evaluate several programming strategies. Two programming strategies for a fairly common problem—a periodic tridiagonal solver—are developed and evaluated. Simple model calculations as well as timing results are presented to evaluate these strategies.The particular tridiagonal solver evaluated is used in many computational fluid dynamic simulation codes. The feature that makes this algorithm unique is that these simulation codes usually require simultaneous solution for multiple right‐hand‐sides (RHS) of the system of equations. Each RHS solutions is independent and thus can be computed in parallel. Thus, a Gaussian‐elimination‐type algorithm can be used in a parallel computation and more complicated approaches such as cyclic reduction are not required.The two strategies are a transpose strategy and a distributed solver strategy. For the transpose strategy, the data are moved so that a subset of all the RHS problems is solved on each of the several processors. This usually requires significant data movement between processor memories across a network. The second strategy attempts to have the algorithm follow the data across processor boundaries in a chained manner. This usually requires significantly less data movement. An approach to accomplish this second strategy in a near‐perfect load‐balanced manner is developed. In addition, an algorithm will be shown to directly transform a sequential Gaussian‐elimination‐type algorithm into the parallel, chained, load‐balanced algorithm.

This publication has 3 references indexed in Scilit: