Parallel Computing Strategies for Irregular Algorithms

Biswas, Rupak; Oliker, Leonid; Shan, Hongzhang; Biegel, Bryan

Parallel computing promises several orders of magnitude increase in our ability to solve realistic computationally-intensive problems, but relies on their efficient mapping and execution on large-scale multiprocessor architectures. Unfortunately, many important applications are irregular and dynamic in nature, making their effective parallel implementation a daunting task. Moreover, with the proliferation of parallel architectures and programming paradigms, the typical scientist is faced with a plethora of questions that must be answered in order to obtain an acceptable parallel implementation of the solution algorithm. In this paper, we consider three representative irregular applications: unstructured remeshing, sparse matrix computations, and N-body problems, and parallelize them using various popular programming paradigms on a wide spectrum of computer platforms ranging from state-of-the-art supercomputers to PC clusters. We present the underlying problems, the solution algorithms, and the parallel implementation strategies. Smart load-balancing, partitioning, and ordering techniques are used to enhance parallel performance. Overall results demonstrate the complexity of efficiently parallelizing irregular algorithms.

Document ID

20020090950

Acquisition Source

Ames Research Center

Document Type

Preprint (Draft being sent to journal)

Authors

Date Acquired

September 7, 2013

Publication Date

September 1, 2002

Subject Category

Funding Number(s)

Distribution Limits

Public

Public Use Permitted.

Available Downloads

Name

Type

20020090950.pdf

STI

No Preview Available

NTRS

NTRS - NASA Technical Reports Server

Available Downloads

Related Records