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

被引：38

作者：

李远成

阴培培

赵银亮

机构：

[1] 西安交通大学计算机科学与技术系

来源：

计算机学报 | 2014年 / 37卷 / 03期

关键词：

推测多线程; 线程划分; 模糊聚类; 自动并行化; 代价评估;

D O I：

暂无

中图分类号：

TP311.1 [程序设计];

学科分类号：

081205 [计算机软件];

摘要：

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

引用

页码：580 / 592

页数：13

共 4 条

[1]

Exploiting thread-level parallelism in the iterative solution of sparse linear systems.[J]..Parallel Computing.2010, 3

[2]

Adaptive execution techniques of parallel programs for multiprocessors.[J].Jaejin Lee;Jung-Ho Park;Honggyu Kim;Changhee Jung;Daeseob Lim;SangYong Han.Journal of Parallel and Distributed Computing.2009, 5

[3]

Precise slicing of concurrent programs..[J].Dennis Giffhorn;Christian Hammer.Automated Software Engineering.2009, 2

[4]

SpMT WaveCache:开发数据流计算机中的推测多线程 [J].

裴颂文 ;

吴百锋 .

计算机学报, 2009, 32 (07) :1382-1392

← 1 →