Affiliations: European Center for Parallelism of Barcelona,
Technical University of Catalunya, Barcelona 08034, Spain | Edinburgh Parallel Computing Center, The University of
Edinburgh, Edinburgh EH93JZ, UK
Abstract: Many scientific applications involve array operations that are
sparse in nature, ie array elements depend on the values of relatively few
elements of the same or another array. When parallelised in the shared-memory
model, there are often inter-thread dependencies which require that the
individual array updates are protected in some way. Possible strategies include
protecting all the updates, or having each thread compute local temporary
results which are then combined globally across threads. However, for the
extremely common situation of sparse array access, neither of these approaches
is particularly efficient. The key point is that data access patterns usually
remain constant for a long time, so it is possible to use an inspector/executor
approach. When the sparse operation is first encountered, the access pattern is
inspected to identify those updates which have potential inter-thread
dependencies. Whenever the code is actually executed, only these selected
updates are protected. We propose a new OpenMP clause, {\tt indirect}, for
parallel loops that have irregular data access patterns. This is trivial to
implement in a conforming way by protecting every array update, but also allows
for an inspector/executor compiler implementation which will be more efficient
in sparse cases. We describe efficient compiler implementation strategies for
the new directive. We also present timings from the kernels of a Discrete
Element Modelling application and a Finite Element code where the
inspector/executor approach is used. The results demonstrate that the method
can be extremely efficient in practice.
