Irregular problems without locality cannot really benefit from parallelism in the message-passing programming model, because they fully undergoe the imbalance between the network and the processors throughputs. Not only the appropriate data are to be bought, but a lot of communication overhead is required to find out the location of the data. One-sided communications [4] will perhaps be the key to boost the performance of such problems. However, at the present time, the message-passing model is the most widely used both for concurrent programming and as a target and run-time support for data-parallel compiler. This paper has shown that, even in the non-local case, there is still room for improving the implementation of irregular problems.
Acknowledgements
The experiments were performed on the IBM SP-2 of Centre National Universitaire Sud de Calcul.