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

摘要：

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

关键词：推测多线程、线程划分、模糊聚类、自动并行化、代价评估

所属期刊栏目：37

分类号：TP314(计算技术、计算机技术)

资助基金：国家“八六三”高技术研究发展计划项目基金2008AA01Z136;国家自然科学基金61173040;the National High Technology Research and Development Program 863 Program of China under Grant No.2008AA01Z136,and the National Natural Science Foundation of China under Grant No.61173040

在线出版日期：2014-07-10（万方平台首次上网日期，不代表论文的发表时间）

页数：共11页

页码：580-590