In this chapter, we propose an efficient communication schedule for running the complete exchange operation on clusters, which are interconnected by the Ethernet-based hierarchical network. The essential feature of this communication scheme is the proactive approach in handling congestion. We consider the contention effect at three different stages. At the first stage, we experience no contention and the performance of the network is bounded by its hardware performance only. For example, the network load is light and there are no conflicting traffic. At the second stage, we have mild contention with slight decrease in performance due to the experience of contention delay. At the third stage, we experience significant performance loss as the severity of the contention has induced the congestion loss problem. Therefore, to achieve good performance, we try to avoid contention in the first place by having a communication schedule, which prevents contention at the node and switch. If congestion does develop, our communication scheme regulates the traffic to avoid further building up of congestion that results in congestion loss.
Our complete exchange algorithm on hierarchical network is based on the synchronous shuffle exchange algorithm, which is developed on a theoretical non-blocking network. By introducing a global windowing concept to all participating nodes, they are responsible to monitor and regulate the traffic loads to avoid congestion. Based on architectural features like the network buffering capacity and the balancing of upstream and downstream flows, we derive the global windowing scheme and the contention-aware permutation, which transform the algorithm to work efficiently on the hierarchical network.
This chapter is organized as follows. Section 6.1 lays down the architectural characteristics of the Ethernet-based hierarchical network, and describes a simple abstract model of the hierarchical network to aid our analysis. Section 6.2 describes how to augment the original synchronous shuffle exchange algorithm to run efficiently on both Ethernet-based hierarchical networks and non-blocking networks. Then, the experimental results of the modified algorithm are presented in Section 6.3. Finally, summaries are presented in Section 6.5.