Parallelizing the construction of indirect access arrays for shared‐memory machines

Abstract

A way has been found to form indirect addressing lists in parallel on shared-memory parallel machines. The maximum possible speed-up for typical tetrahedral grids is approximately 1:23. The algorithm requires an additional scratch array to shift from the serial ‘elements surrounding points’ to the parallel ‘elements surrounding processors surrounding points’ paradigm. The algorithm developed is general in nature, i.e. applicable to all indirect addressing lists. All numerical methods requiring the construction of indirect data structures, such as sparse matrix linear algebra procedures, field and particle solvers operating on unstructured grids, and network flow applications should see a benefit from this algorithm when running on shared-memory parallel machines.

Full Document