Accession Number : ADA322751

Title :   Parallel ICCG on a Hierarchical Memory Multiprocessor-Addressing the Triangular Solve Bottleneck.

Corporate Author : STANFORD UNIV CA DEPT OF COMPUTER SCIENCE

Personal Author(s) : Rothberg, Edward ; Gupta, Anoop

PDF Url : ADA322751

Report Date : OCT 1990

Pagination or Media Count : 23

Abstract : The incomplete Cholesky conjugate gradient (ICCG) algorithm is a commonly used iterative method for solving large sparse systems of equations. In this paper, we study the parallel solution of sparse triangular systems of equations, the most difficult aspect of implementing the ICCG method on a multiprocessor. We focus on shared-memory multiprocessor architectures with deep memory hierarchies. On such architectures we find that previously proposed parallelization approaches result in little or no speedup. The reason is that these approaches cause significant increases in the amount of memory system traffic as compared to a sequential approach. Increases of as much as a factor of 10 on four processors were observed. In this paper we propose new techniques for limiting these increases, including data remappings to increase spatial locality, new processor synchronization techniques to decrease the use of auxiliary data structures, and data partitioning techniques to reduce the amount of interprocessor communication. With these techniques, memory system traffic is reduced to as little as one sixth of its previous volume. The resulting speedups are greatly improved as well, although they are still much less than linear. We discuss the factors that limit further speedups. We present both simulation results and results of experiments on an SGI 4D/340 multiprocessor.

Descriptors :   *DISTRIBUTED DATA PROCESSING, *COMPUTER COMMUNICATIONS, *PARALLEL PROCESSING, DATA BASES, ALGORITHMS, LINEAR SYSTEMS, DATA MANAGEMENT, INFORMATION TRANSFER, COMMUNICATIONS TRAFFIC, MULTIPROCESSORS, HIERARCHIES, FLOATING POINT OPERATION.

Subject Categories : Computer Programming and Software
      Computer Systems

Distribution Statement : APPROVED FOR PUBLIC RELEASE