Data locality exploitation in algorithms including sparse communications
Gerardo Bandera, Emilio L. Zapata · 2002
Complexity in real codes is sometimes due to the utilization of multi-vector data structures, but there are not many compile-time approaches dealing with this problem, Moreover current compilation techniques only analyze single vectors. This paper describes how the performance can be improved if semantical bindings are taken into account during the parallelization. Our approach is a first step to converge from the data-parallel paradigm to the automatic parallelization, by reducing the number of directives on code. We apply a multi-loop analysis and a sparse privatization to replace the owner computes rule. Additionally, our support will be able to parallelize loops with some of levels of indirections on a left-hand side. In this paper, we also present three alternatives to store the sending information, and two algorithms to calculate coordinates from pointers. Both issues have a critical importance when the parallelized algorithm requires a sparse communication.