Rundberg and Stenstr?om introduced one of the first models for software TLS. This increases the loop parallelism by speculatively executing iterations while keeping a log of reads and writes; if a conflict occurs then mis-speculated iterations are re-executed (rollback). This is useful for code falling outside the traditional static dependence analysis framework. Their technique simulates cache-coherency hardware and is exact in that rollback only takes place when a dependence violation occurs, but the coherency overheads are too large for general practical use.

Our contribution is a family of abstract coherency algorithms; while being safe (detect all violations), these trade false positives (which cause unnecessary rollbacks) against coherency algorithm space and time.

This paper gives one such algorithm.