非规则算法已在复杂网络分析、机器学习、图像处理、生物信息、分子动力学和气候模拟等领域有着广泛的应用,如何有效地通过线程级推测技术提升非规则算法的执行效率已成为当前研究的热点。然而,现有的线程级推测调度策略没有考虑非规则算法自身特征,推测并行时采用“一刀切”策略进行线程调度,导致执行效果不佳。为了得到更好的推测执行性能,本文从非规则算法样本集和线程级推测调度领域和实验论证三个方面展开研究,论文主要工作总结如下:（1）提出一种面向线程级推测（Thread Level Speculative,TLS）的样本集构建方法。针对现有的非规则算法与其最优线程级推测调度策略不对应的问题。首先,通过对线程级推测技术的研究,基于扩展支持TLS技术的Open MP编程模型,将非规则算法转化为推测并行版本,然后利用特征提取技术对非规则算法的特征信息进行提取,进而对非规则算法的特征进行表示,建立非规则算法的特征集;然后,通过采用不同的TLS调度策略对非规则算法进行反复调度执行,为非规则算法选择最优TLS调度策略作为其标签;最终将非规则算法特征集合与其对应的标签进行组合,构建出基于TLS的非规则算法样本集,为后续模型的训练提供数据集。（2）提出一种基于KNN的线程级推测调度方法。针对线程级推测调度方法未考虑非规则算法特征信息的情况,本文将机器学习引入到线程级推测调度领域,首先,以非规则算法样本集作为训练样本,然后,对样本进行预处理,最后基于KNN方法为非规则算法构建预测模型并通过实验确定K值。当新的非规则算法需要执行时,通过预测模型为新的非规则算法预测适合它自身特征的最优TLS调度策略。（3）KNN调度方法性能研究与分析。针对KNN的调度方法,设计多组实验对其进行测试与结果分析,评估KNN预测模型的准确率,验证所提出的样本构建方法的有效性;采用量化数据验证所提出的基于KNN的线程级推测调度方法推测执行时的正确性和推测性能收益。实验结果表明,本文提出的基于KNN的非规则算法线程级推测调度方法在不同线程下对于非规则算法的推测执行效率均有所提升。KNN模型准确率达到78.95%,推测增长率最差表现是在8线程下对于非规则算法推测执行效率提升为17.3%,在4线程下增长率可以达到最高55.9%。实验证明本文所提方法可以克服现有TLS调度策略的“一刀切”现象,通过KNN预测模型可以根据非规则算法自身特征为它预测最优TLS调度策略,有效的提升非规则算法在推测并行执行时的执行速率,缩短执行时间。