基于模糊聚类的推测多线程划分算法

• 作者: 李远成 赵银亮 阴培培
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 推测多线程 线程划分 模糊聚类 自动并行化 代价评估
• 年，卷（期）: 2014,（3）
• 所属期刊栏目: 软件工程
• 页码范围: 580-590
• 页数: 11页
• 分类号: TP314
• 字数: 10328字
• 语种: 中文
• DOI: 10.3724/SP.J.1016.2014.00580

摘要

推测多线程(Speculative Multithreading,SpMT)技术是一种实现非规则程序自动并行化的有效途径.然而,如何有效评估由诸如控制、数据依赖等因素导致的多种并行开销并实现最优线程划分一直是制约加速比性能提升的关键问题.基于启发式规则的传统划分方法虽然可以取得一定的加速效果,但由于启发式规则只能对多种并行开销进行定性评估,因而导致只能得到经验上较优的线程划分.针对传统划分方法的局限性,文中首次提出并实现了一种基于模糊聚类的线程划分方法.在该方法中,作者首先提出一种评估模型来定量评估各种并行开销,然后通过深入分析各种并行开销来确定最佳的线程解搜索空间,最终利用聚类方法实现有效线程解空间搜索以求取更优的线程划分.基于Olden程序集的测试结果表明,文中提出的线程划分方法可以有效地对非规则程序进行划分,其平均加速比可达到1.85.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	赵银亮	西安交通大学计算机科学与技术系	52	517	12.0	21.0
2	李远成	西安交通大学计算机科学与技术系	5	44	4.0	5.0
3	阴培培	西安交通大学计算机科学与技术系	3	29	1.0	3.0