Data-parallel support for numerical irregular problems

A large class of intensive numerical applications show an irregular structu re, exhibiting an unpredictable runtime behavior. Two kinds of irregularity can be distinguished in these applications. First, irregular control struc tures, derived from the use of conditional statements on data only known at runtime. Second, irregular data structures, derived from computations invo lving sparse matrices, grids, trees, graphs, etc. Many of these application s exhibit a large amount of parallelism, but the above features usually mak e that exploiting such parallelism becomes a very difficult task. This pape r discusses the effective parallelization of numerical irregular codes, foc using on the definition and use of data-parallel extensions to express the parallelism that they exhibit. We show that the combination of data distrib utions with storage structures allows to obtain efficient parallel codes. C odes dealing with sparse matrices, finite element methods and molecular dyn amics (MD) simulations are taken as working examples. (C) 1999 Elsevier Sci ence B.V. All rights reserved.