Data-parallel support for numerical irregular problems

✍ Scribed by E.L. Zapata; O. Plata; R. Asenjo; G.P. Trabado

• Publisher: Elsevier Science
• Year: 1999
• Tongue: English
• Weight: 502 KB
• Volume: 25
• Category: Article
• ISSN: 0167-8191
• DOI: 10.1016/s0167-8191(99)00090-3

✦ Synopsis

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 dicult task. This paper discusses the eective parallelization of numerical irregular codes, focusing on the de®nition 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 ecient parallel codes. Codes dealing with sparse matrices, ®nite element methods and molecular dynamics (MD) simulations are taken as working examples.