Message Passing with Communication Structures

During my doctoral research, I investigated the effects of communication patterns on message passing applications. I demonstrated with empirical results that applications developed with group-based message passing interfaces (such as the MPI) are prone to performance degradation. I showed that this problem is inherent in the ambiguity of defining communication patterns using process groups; and to resolve this, I introduced the concept of communication structures. The following is the thesis abstract:

Abstraction concepts based on process groups have largely dominated the design and implementation of communication patterns in message passing systems. Although such an approach seems pragmatic--given that participating processes form a ‘group’--in this dissertation, we discuss subtle issues that affect the qualitative and quantitative aspects of this approach. To address these issues, we introduce the concept of a ‘communication structure,’ which defines a communication pattern as an implicit runtime composition of localised patterns, known as ‘roles.’

During application development, communication structures are derived from the algorithm being implemented. These are then translated to an executable form by defining process specific data structures, known as ‘branching channels.’ The qualitative advantages of the communication structure approach are that the resulting programming model is non-ambiguous, uniform, expressive, and extensible. To use a pattern is to access the corresponding branching channels; to define a new pattern is simply to combine appropriate roles. The communication structure approach therefore allows immediate implementation of ad hoc patterns. Furthermore, it is guaranteed that every newly added role interfaces correctly with all of the existing roles, therefore scaling the benefit of every new addition.

Quantitatively, branching channels improve performance by automatically overlapping computations and communications. The runtime system uses a receiver initiated communication protocol that allows senders to continue immediately without waiting for the receivers to respond. The advantage is that, unlike split-phase asynchronous communications, senders need not check whether the send operations were successful. Another property of branching channels is that they allow communications to be grouped, identified, and referenced. Communication structure specific parameters, such as message buffering, can therefore be specified immediately. Furthermore, a ‘commit’ based interface optimisation for send-and-forget type communications--where senders do not reuse sent data--is presented. This uses the referencing property of branching channels, allowing message buffering without incurring performance degradation due to intermediate memory copy.

Source code

git clone

Selected publications

  • Yaikhom, G. (2006). Message Passing with Communication Structures. PhD thesis, School of Informatics, University of Edinburgh.

  • Yaikhom, G. (2005). Shared Message Buffering without Intermediate Memory Copy. In Tiskin, A. and Loulergue, F., editors, Proceedings of the Intl. Conference on High-level Parallel Programming and Applications (HLPP), pp. 61-73, Coventry, UK.

  • Yaikhom, G. (2005). Buffered Branching Channels with Rendezvous Message Passing. In Fahringer, T. and Hamza, M., editors, Proceedings of the Intl. Conference on Parallel and Distributed Computing and Networks (PDCN), pp. 184-192. ACTA Press, Innsbrück, Austria.