Streams as an alternative to halo exchange

摘要

Many scientific problems can be solved computationally by using linear algebra to calculate numerical solutions. The data dependencies in linear algebra operations are often expressed in a stencil structure. The ubiquitous parallelisation technique for stencil codes, to enable the solution of large problems on parallel architectures, is domain decomposition. One of the limitations of domain decomposition, affecting the scalability and overall performance of any stencil code, is the necessity to transmit information from neighbouring stencil grid points between the domains, and in particular between processes, known as halo exchange. The necessity of halo exchange limits the size of problems that can be solved numerically as the performance often scales poorly, in particular in poorly load balanced systems. Extensive work has been done to improve the performance of such codes, such as multi-depth halos and dynamic load balancing by changing the domain size, however, these methods all use the concept of halos for the basic communication pattern. In this paper we propose an alternative to the traditional halo exchange method of transmitting data between processes. In our model inter-process communication becomes a uni-directional stream, and not an exchange, in that it is transmitted in one direction only. This removes the pair-wise synchronisation between neighbouring processes inherent in the halo exchange pattern. As all communication is unidirectional, data can be updated in place, rather than double-buffered, resulting in half the memory usage of the traditional approach. In this paper we also present our preliminary findings which show that for a one-dimensional implementation of this model using a Jacobi-stencil code, that the streaming method is consistently faster than the exchange pattern. At 16,000 processes, for both strong and weak scaling, streaming is over ten times faster than halo exchange. We are currently investigating further optimisation strategies and extending to multi-dimensional domain decomposition.