In previous chapter, we show that congestion loss is a serious threat to the communication performance. A good rule of thumb in achieving high-performance on communication is to avoid congestion build up. Hence, we should avoid contention in the first place. We have stressed in early chapters that contention is a phenomenon which exists everywhere. Contention can happen in host node, network link and within the switch. Node contention happens when multiple data packets contend for the receive channel of a node, while link contention occurs when two or more packets share a communication link. And switch contention is induced by the unbalance of traffic flow through the switch, which results in overflow of the switch buffer. In fact, it is impractical to think that we can eliminate contention completely, unless we sacrifice our performance objective.
In this chapter, we carry on with our studies of the contention issue as well as the performance issue by focusing on the most demanding communication pattern on all message-passing machines - the Complete Exchange operation. We make use of our communication model to design and analyze several complete exchange algorithms, and accurately demonstrate their relative performance. These algorithms feature their own communication schedules to avoid node, link and switch contention on a non-blocking network. The network is said to be non-blocking if all disjoint point-to-point connections are compatible, such that there exists a disjoint path between each node-pair which are interconnected by this network. Besides the contention issue, our modeling works uncover other internal factors that have significant influence on the communication performance.
This chapter is organized as follows. We start the discussion by having a brief overview on the complete exchange operation together with some related work. Then, follow by some discussions on the network issue in Section 5.2. In Section 5.3, we present and analyze various communication schedules for the complete exchange operation with respect to our communication model. Section 5.4 contains our experimental validations and analyses of these algorithms on a real cluster platform. Finally, summaries are presented in Section 5.5.
