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

A FCM-Based Thread Partitioning Algorithm for Speculative Multithreading

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

Speculative multithreading （SpMT） technology is an effective mechanism for automat ic parallelization of irregular programs. Selecting optimal thread partitioning solution by effectively assessing the speculative parallelization overheads is a key issue for the speedup performance improvement. However, most existing thread partitioning methods are still based on simple heu- ristics rules to select speculative threads. Because these heuristics rules can only be used to indirectly estimate the speculative multithreaded execution overheads and simply tackle individual overheads, these methods can only get the empirical optimal speculative thread solution. To over- come the limitation of these existing methods, in this paper, we first propose a fuzzy c-means （FCM） algorithm based thread partitioning method which can be used to effectively search the solution space of speculative threads and get the optimal solution. In this method, we effectively determine the solution space of speculative threads based on the analysis of several overheads. Meanwhile, we design and implement the cluster validity function by building a cost estimation model. The experimental results show that the proposed method can effectively search the solution space of speculative threads and we can indeed get better performance. On average, we achieve an average speedup of 1.85 on Olden benchmark suits.