A Lightweight Model for Software Thread-Level Speculation (TLS)

Rundberg and Stenstrom 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.