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

• 作者: 刘婧 李伟 顾乃杰
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: LogP模型 并行算法 多播 通信算法
• 年，卷（期）: 2002,（4）
• 所属期刊栏目: 研究论文与技术报告
• 页码范围: 365-372
• 页数: 8页
• 分类号: TP393
• 字数: 6719字
• 语种: 中文
• DOI: 10.3321/j.issn:0254-4164.2002.04.005

摘要

该文提出了一种基于斐波那契序列的多播算法,并在logP模型[1]下对算法的性能进行了分析.logP模型是一种广泛使用的并行计算模型,它利用L,o,g,P四个参数来分别表示发送一条消息的等待时间或最大延迟、处理器的开销、源结点发送消息的时间间隔、处理器/存储器模块数.在logP模型下,该文所述的基于斐波那契序列的多播算法的时间复杂度为0.72022* log2K*(g+max{L+2*o,2*g}),而传统的采用均匀二分的多播算法时间复杂度为log2K*(L+2*o),其中K为结点数.当g0.3884*(L+2*o)时, 基于斐波那契序列的多播算法性能将优于采用均匀二分策略的多播算法.由于实际情况中L+2og, 因此, 基于斐波那契序列的多播算法性能更优.实验结果也验证了这一结论.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李伟	中国科学技术大学计算机科学与技术系	315	4950	35.0	61.0
2	顾乃杰	中国科学技术大学计算机科学与技术系	83	347	9.0	12.0
3	刘婧	中国科学技术大学计算机科学与技术系	4	32	2.0	4.0