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. Experiemtnal results compare the sorting method with a commercial implementation of the naive method, and shows the efficiency of the sorting method in practice.
展开▼
