基于长并行距离优先的确定性多线程调度

随着多核技术的不断发展,多线程技术更加广泛地应用于计算机软件中.但由于执行的不确定性,多线程程序的排错和调试存在着很大的困难.确定性多线程系统可以使多线程程序以确定的方式执行,即多次执行同一个多线程程序的顺序和结果是相同的,这可以大大简化多线程程序的排错和调试.但是,确定性多线程系统会导致多线程程序性能的下降.本文提出一种基于长并行距离优先的确定性多线程调度算法,优先执行并行距离长的线程,减少线程总体等待时间,从而提高多线程程序的效率.实验结果表明,本文方法可以使多线程程序的性能提升10%,并且具有很好的可扩展性.

确定性多线程编程模型的可编程性及其实现性能的探索

传统的多线程程序存在许多不确定性,导致编程困难,易出错.确定性并行编程模型是保证并行程序确定执行的有效途径之一.针对所提出的确定性消息传递多线程编程模型Det MP及它在确定性生产-消费虚拟内存模型SPMC上的实现,本文探索Det MP的可编程性和实现机制对性能的影响.包括:总结了用Det MP改写现有Pthreads多线程程序的方法,并在32核计算机上用7个MapReduce应用程序和1个流水线并行程序dedup对比改写前后的性能.实验表明用Det MP改写后的程序在多数情况下比原来的Pthreads程序有好的性能.为了分析这种性能差异是否因使用了SPMC虚拟内存模型而引起,本文进一步基于传统Pthreads共享内存来实现Det MP应用编程接口,并用所改写的应用程序集评测它们在Det MP的两种实现上运行的性能.实验表明,当CPU核数为16和32时,基于SPMC的Det MP实现在除Matrix Multiply和String Match外的6个程序上有更好的性能,最高甚至比基于Pthreads的实现快9.5倍;而在Matrix Multiply和String Match上或者核数低于16时,两种实现的性能相当.