Automatic parallelization of irregular applications

Parallel computers are present in a variety of fields, having reached a hig h degree of architectural maturity. However, there is still a lack of conve nient software support for implementing efficient parallel applications. Th is is specially true for the class of irregular applications, whose computa tional constructs hardly fit current parallel architectures. In fact, conte mporary automatic parallelizers produce, in general, poor parallel code fro m these applications. This paper discusses techniques and methods to help i mprove the quality of automatic parallel programs. We focus on two issues: parallelism detection and parallelism implementation. The first issue refer s to the detection of specific irregular computation constructs or data acc ess patterns. The second issue considers the case that some frequent constr uct has been detected but has been sub-optimally parallelized. Both issues are dealt with in depth and in the context of sparse computations (for the first issue) and irregular histogram reductions (for the second issue). (C) 2000 Elsevier Science B.V. All rights reserved.