To access the full text documents, please follow this link:

New OpenMP directives for irregular data access loops
Labarta Mancho, Jesús José; Ayguadé Parra, Eduard; Oliver, José; Henty, David
Universitat Politècnica de Catalunya. Departament d'Arquitectura de Computadors; Universitat Politècnica de Catalunya. CAP - Grup de Computació d´Altes Prestacions
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, 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.
Peer Reviewed
Àrees temàtiques de la UPC::Informàtica
Àrees temàtiques de la UPC::Informàtica::Arquitectura de computadors::Arquitectures paral·leles
Parallel programming (Computer science)
Programació en paral·lel (Informàtica)
Attribution-NonCommercial-NoDerivs 3.0 Spain

Show full item record

Related documents

Other documents of the same author

Ciesko, Jan; Mateo, Sergi; Teruel, Xavier; Beltran, Vicenç; Martorell Bofill, Xavier; Badia,, R.M.; Ayguadé Parra, Eduard; Labarta Mancho, Jesús José
Planas, Judit; Badia Sala, Rosa Maria; Ayguadé Parra, Eduard; Labarta Mancho, Jesús José
Guitart Fernández, Jordi; Torres Viñals, Jordi; Ayguadé Parra, Eduard; Oliver, Jose; Labarta Mancho, Jesús José
Guitart Fernández, Jordi; Torres Viñals, Jordi; Ayguadé Parra, Eduard; Oliver, Jose; Labarta Mancho, Jesús José