Cécile Germain and Damien Gautier de Lahaut
Irregular problems are widely regarded as especially difficult for data-parallel compilers targeting the message-passing communication model. The inspector/executor code generation scheme successfully tackles irregular problems exhibiting a high level of data sharing, but little has been done for irregular problems without spatial or temporal locality. This paper proposes a technique based on sorting. The complexity of the method is shown to be better than that of the naive method. Experimental results compare the sorting method with a commercial implementation of the naive method, and shows the efficiency of the sorting method in practice.