Fibonacci Series-Based Multicast Algorithm
Gu Nai · Chinese Journal of Computers · 2002
Multicast is an operation which sends the same message from one source node to several arbitrary destination nodes. It is a common operation in MPI standard, and is very important in parallel and distributed systems, so the research on this operation is of great significance. In this paper, a new multicast algorithm based on the Fibonacci series is proposed, and the performance of the algorithm is analyzed with the Log P model. The performance analysis with this model shows that the communication complexity of the Fibonacci series based multicast algorithm proposed in this paper is 0.72022 ·log 2 K·(g +max {L+2·o,2g }), whereas the communication complexity of the traditional binomial tree based multicast algorithm is log 2 K·(L+2·o) , here K is the number of nodes. From this result we can know that: as long as g0.3884·(L+2·o) , the performance of the Fibonacci series based multicast algorithm can exceed that of the original binomial tree based multicast algorithm. And in the practical conditions, there is always L+2·og , so the new multicast algorithm based on the Fibonacci series is a better algorithm compared with the traditional multicast algorithm based on the binomial tree. And the experiment results we obtained in this paper also support this conclusion very well. On the other hand, by making the source node do more sending work, the communication resources can be used more efficiently with this new algorithm. Moreover in practice, the new multicast algorithm based on the Fibonacci series is quite easy to implement in the parallel and distributed systems. In a word, the new multicast algorithm proposed here is a better technique for the multicast operation.