next up previous
Next: Introduction Up: C. Germain Home Page

Improving Irregular Parallel
Communication through Sorting

Cécile Germain and Damien Gautier de Lahaut

Abstract:

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.





Cecile Germain
Fri May 23 17:53:23 MET DST 1997