Data-parallel support for numerical irregular problems

EL Zapata and O Plata and R Asenjo and GP Trabado, PARALLEL COMPUTING, 25, 1971-1994 (1999).

DOI: 10.1016/S0167-8191(99)00090-3

A large class of intensive numerical applications show an irregular structure, exhibiting an unpredictable runtime behavior. Two kinds of irregularity can be distinguished in these applications. First, irregular control structures, derived from the use of conditional statements on data only known at runtime. Second, irregular data structures, derived from computations involving sparse matrices, grids, trees, graphs, etc. Many of these applications exhibit a large amount of parallelism, but the above features usually make that exploiting such parallelism becomes a very difficult task. This paper discusses the effective parallelization of numerical irregular codes, focusing on the definition and use of data-parallel extensions to express the parallelism that they exhibit. We show that the combination of data distributions with storage structures allows to obtain efficient parallel codes. Codes dealing with sparse matrices, finite element methods and molecular dynamics (MD) simulations are taken as working examples. (C) 1999 Elsevier Science B.V. All rights reserved.

Return to Publications page