随机算法异步并行化的效率分析

• 作者: 张强峰 徐云 陈国良 顾钧
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 随机算法 异步并行 运行时间分布 SAT问题 NP完全问题
• 年，卷（期）: 2003,（5）
• 所属期刊栏目: 算法设计与分析
• 页码范围: 871-876
• 页数: 6页
• 分类号: TP301
• 字数: 2589字
• 语种: 中文

摘要

随机算法的执行时间具有不确定性,这种不确定性为随机算法的异步并行提供了良好的基础,已有许多计算实验表明了随机算法的异步并行可以达到线性甚至超线性的加速.对于求解SAT问题的随机算法RDP,研究了异步并行效率与运行时间分布和处理器数目之间的关系.应用一种单峰分布──分段线性分布模型来模拟随机算法的运行时间分布.理论分析和计算结果均表明:当处理器数目k较小和单峰位于分布的前部时,随机算法的异步并行具有近线性加速.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	陈国良	中国科学技术大学计算机科学与技术系	123	2142	20.0	43.0
2	徐云	中国科学技术大学计算机科学与技术系	79	411	13.0	16.0
3	顾钧	中国科学技术大学计算机科学与技术系	5	43	4.0	5.0
7	张强峰	中国科学技术大学计算机科学与技术系	1	3	1.0	1.0