一种基于路径优化的推测多线程划分算法

推测多线程(speculative multithreading,简称SpMT)技术是一种实现非规则程序自动并行化的有效途径.然而,基于控制流图和分支预测技术的线程划分方法,不可避免地会受到划分路径上所存在的控制依赖和数据依赖的制约.目前,在传统的线程划分算法中存在的一个重要问题是,在对划分路径进行选取时只考虑了控制依赖影响却不能有效地综合考虑数据依赖的影响,进而导致不能选取最佳的划分路径.因此,针对传统方法中这种依赖评估方法效率低下的问题,设计并实现了一种基于路径优化的线程划分算法.该算法通过引入基于程序切片技术的预计算方法,建立一种路径评估方法来评估程序间的控制和数据依赖.同时,引入控制线程体大小的启发式规则,以便有效地解决负载不平衡的问题.基于Olden测试集的测试结果表明,所提出的算法可以有效地对非规则程序进行划分,其平均加速比可以达到1.83.

Thread Partitioning Algorithm for Speculative Multithreading Based on Path Optimization

Speculative multithreading(SpMT) technology is an effective mechanism for automatic parallehzation of irregular programs.However,just generating speculative threads based on the control flow graph which only contains branch probability information is not enough.It is inevitable that there may be excessive constraints resulting from control dependence and data dependence in practice.In the traditional thread partitioning algorithms, a key problem is that these existing evaluation methods do not integrate the data dependence with the control speculation in order to obtain the maximum benefit.In order to solve the inefficiency of evaluation for control dependence and data dependence,this paper proposes a path optimization based thread partitioning algorithm.In this algorithm,by introducing pre-computation technique and discussing the trade-offs between different speculative paths the study establishes an evaluation model to evaluate the control dependence and data dependence. Meanwhile,in order to reduce the side-effect of workload imbalance,some heuristics rules are designed.The experimental results show that there are interesting trade-offs between different speculative paths and it is possible to achieve a better performance.On average,the study achieved an average speedup of 1.83 on Olden benchmark suits.