基于斐波那契序列的多播算法  

Fibonacci Series-Based Multicast Algorithm

作　　者：顾乃杰[1] 李伟[1] 刘婧[1] 

机构地区：[1]中国科学技术大学计算机科学与技术系,合肥230027

出　　处：《计算机学报》2002年第4期365-372,共8页Chinese Journal of Computers

摘　　要：该文提出了一种基于斐波那契序列的多播算法 ,并在 log P模型 [1 ] 下对算法的性能进行了分析 .log P模型是一种广泛使用的并行计算模型 ,它利用 L,o,g,P四个参数来分别表示发送一条消息的等待时间或最大延迟、处理器的开销、源结点发送消息的时间间隔、处理器 /存储器模块数 .在 log P模型下 ,该文所述的基于斐波那契序列的多播算法的时间复杂度为 0 .72 0 2 2· log2 K· (g+m ax{ L+2· o,2· g} ) ,而传统的采用均匀二分的多播算法时间复杂度为 log2 K· (L+2· o) ,其中 K为结点数 .当 g 0 .3884· (L+2· o)时 ,基于斐波那契序列的多播算法性能将优于采用均匀二分策略的多播算法 .由于实际情况中 L +2 o g,因此 ,基于斐波那契序列的多播算法性能更优 .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 g0.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·og , 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.

关 键 词：LOGP模型 并行算 多播算法 斐波那契序列 计算机网络 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]