Reference idempotency analysis: A framework for optimizing speculative execution

Recent proposals for multithreaded architectures allow threads with unknown dependences to execute speculatively in parallel. These architectures use hardware speculative storage to buffer uncertain data, track data dependenc es and roll back incorrect executions. Because all memory references access the speculative storage, current proposals implement this storage using sm all memory structures for fast access. The limited capacity of the speculat ive storage causes considerable performance loss due to speculative storage overflow whenever a thread's speculative state exceeds the storage capacit y. Larger threads exacerbate the overflow, problem but axe preferable to sm aller threads, as larger threads uncover more parallelism. In this paper, we discover a new program property called memory reference i dempotency. Idempotent references need not be tracked in the speculative st orage, and instead can directly access non-speculative storage (i.e., the c onventional memory hierarchy). Thus, we reduce the demand for speculative s torage space. We define a formal frame-work for reference idempotency and p resent a novel compiler-assisted speculative execution model. We prove the necessary and sufficient conditions for reference idempotency using our mod el. We present a compiler algorithm to label idempotent memory references f or the hardware. Experimental results show that for our benchmarks, over 60 % of the references in non-parallelizable program sections axe idempotent.