Broadcasting Algorithm of Constant Complexity for Fully-Switched Clusters

Abstract:- Clusters are high performance computation systems, built up out of standard off-the-self workstations connected with fast, but standard communication devices. This structure allows higher pure processing power and lower hardware costs compared to other supercomputers. One main disadvantage of clusters is the lower communication throughput between the processing elements, as standard methods usually provide weaker performance than the much more expensive special communication devices of supercomputers. Because of this it is very important to take the most advantage of the existing communication potential in cluster environment. This paper presents a method of enhancing the performance of the broadcast group communication primitive by using a new algorithm that takes advantage of message decomposition and asynchronous communication. When used in fully switched cluster environment the new solution provides a constant execution time independent of the number of participants. Test measurements show that the algorithm follows well the predicted behavior, and has superior performance, compared to the widely used binomial tree method used in standard message passing libraries. As broadcasting is a building block of various group communication primitives, improving its performance may have beneficial effect on several routine of message passing libraries