面向投机并行的点点同步算法

摘要

线程级投机并行可以利用多核系统的计算能力提高应用程序的性能。串行程序被分割为多个线程并行执行，通过运行时系统保证对包含数据依赖代码按照其串行次序执行。投机成功时，可以极大增加系统并发度，但是投机失败时开销较大。对于一类发生次数不多的数据依赖，采用线程间同步机制，可以避免投机失败，从而减少开销。本文提出了一种把循环转换为线程投机执行的框架LLSM。LLSM可以把常规编译方法难以并行的循环切割转换为多线程并行执行。为保证准确性，在并行执行中保持具有数据依赖的指令按照串行次序执行。通过执行中缓冲对数据的写请求，同时在提交这些写请求时，各线程间保持循环迭代间的依赖关系，这样保持了串行程序的W-W和R-W依赖关系。基于LLSM，提出了一种点点同步算法，在具有W-R数据依赖关系的线程间传递依赖数据，以避免投机执行失败。对于所选Spec测试程序，投机并行可以达到21%的性能增长。