Communication mechanisms and algorithms for supporting scalable collective communication on parallel system

With the tremendous increase in computing power of processors, efficient inter-processor communication has become critical to the performance of parallel systems. Therefore, a well-designed communication subsystem is highly desirable for parallel machines. A typical communication subsystem consists of interconnection hardware and system software support. Interconnection technology can be broadly classified into two categories: direct router-based networks and indirect switch-based networks. The system software support primarily consists of the communication mechanism, collective communication (communication operations involving groups of nodes) algorithms, and the routing scheme.;The goal of this thesis is to propose efficient multicast (the most common and fundamental collective communication operation) for both kinds of interconnection networks by focusing on the three components of the system software support. The default unicast (point-to-point) communication mechanism has the inherent drawback that it delivers a message to only a single destination in one step. To overcome this, two new communication mechanisms are proposed. The first one, called multi-destination messaging, uses extra hardware support at the router/switch to deliver message to multiple destinations in one step. The second, called smart network interface (NI) messaging, involves modification of the firmware running at the NI processor to enable delivery of message to multiple destinations with lower software overhead.;Efficient multicast algorithms using all three communication mechanisms (unicast, multidestination, and smart NI messaging) are proposed for both kinds of interconnection technology. The proposed algorithms and mechanisms are evaluated using extensive experiments. The multicast algorithms are shown to be efficient for the cases of single and multiple multicast. A comprehensive comparison of the two new communication mechanisms is presented in terms of performance and cost. Also, a sample proof-of-concept implementation of smart NI messaging is described. The proposed communication mechanisms, collective communication algorithms, and their extensive evaluation demonstrate significant potential to be applied to the design of communication support for current and future generation parallel systems.