一种非可规约循环的投机并行方法

Exploiting Speculative Parallelism in Irreducible Loops

传统的并行编译器在处理非可规约循环时一般使用结点分割法,但由此带来的代码复制是不可避免的。本文使用投机的方法来挖掘非可规约循环的并行性,该方法在编译时查找程序中的非可规约循环,在运行时使用"持续引用"策略预测该循环的入口,进而实现非可规约循环的并行化。

Irreducible loop is a kind of loop with multi-entries. These loops are called irreducible because dominated relationship does not exist among the nodes in them. Traditional paralhlized compiler techniques use node splitting to make irreducible loops reducible, but will make code duplicate inevitably. This paper proposes a speculative method to exploit parllelism in irredudbh loops. This method finds irreducible loops at compile time and predicts the entry at run time using a strategy called＂persistency reference＂, then parallelizes irreducible loops as natural loops. Experimental results show that the method is effective and efficient.