Accession Number : ADA322741

Title :   The Performance Impact of Data Reuse in Parallel Dense Cholesky Factorization,

Corporate Author : STANFORD UNIV CA DEPT OF COMPUTER SCIENCE

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

PDF Url : ADA322741

Report Date : 01 JAN 1992

Pagination or Media Count : 31

Abstract : This paper explores performance issues for several prominent approaches to parallel dense Cholesky factorization. The primary focus is on issues that arise when blocking techniques are integrated into parallel factorization approaches to improve data reuse in the memory hierarchy. We first consider panel oriented approaches, where sets of contiguous columns are manipulated as single unit. These methods represent natural extensions of the column-oriented methods that have been widely used previously. On machines with memory hierarchies, panel-oriented methods significantly increase the achieved performance over column-oriented methods. However, we find that panel-oriented methods do not expose enough concurrency for problems that one might reasonably expect to solve on moderately parallel machines, thus significantly limiting their performance. We then explore block-oriented approaches, where square submatrices are manipulated instead of sets of columns. These methods greatly increase the amount of available concurrency, thus alleviating the problems encountered with panel-oriented method. However, a number of issues, including scheduling choices and block-placement issues, complicate their implementation. We discuss these issues and consider approaches that solve the resting problem. The resulting block-oriented implementation yields high processor utilization levels over a wide range of problem sizes.

Descriptors :   *DATA MANAGEMENT, *PARALLEL PROCESSING, *MULTIPROCESSORS, DATA BASES, DISTRIBUTED DATA PROCESSING, COMPUTER COMMUNICATIONS, CONCURRENT ENGINEERING, HIERARCHIES, BLOCK ORIENTED RANDOM ACCESS MEMORIES.

Subject Categories : Computer Programming and Software
      Computer Systems

Distribution Statement : APPROVED FOR PUBLIC RELEASE