This paper proposes a technique to increase parallellism for irregular applications. Like the TLS technique (thread level speculation) we discussed in the last class, the proposed technique lets threads iterate in parallel over elements of a set under the optimistic assumption that the iterations do not conflict in their access to shared data. It then validates that no conflicting accesses have happened during an iteration and aborts the iteration if conflict is detected. A key difference between TLS and the proposed technique is the definition of what constitutes a conflict. Where TLS tracks conflicting accesses by concurrent treads at the level of reads and writes to shared memory locations, the proposed technique tracks conflicting accesses at the level of abstract object operations.
a) Why is this beneficial? Give a concrete example.
b) How does this benefit depend on what cores the concurrent threads run on? Explain your answers.