Accession Number:

ADA281651

Title:

Implementation of a Fully-Balanced Periodic Tridiagonal Solver on a Parallel Distributed Memory Architecture

Descriptive Note:

Contractor rept.

Corporate Author:

INSTITUTE FOR COMPUTER APPLICATIONS IN SCIENCE AND ENGINEERING HAMPTON VA

Personal Author(s):

Report Date:

1994-05-01

Pagination or Media Count:

56.0

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 the various 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 solutions for multiple right-hand-sidesRHS 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 the 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 is 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.

Subject Categories:

  • Computer Programming and Software
  • Computer Hardware
  • Fluid Mechanics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE