Exploring Thread-Level Speculation in Software: The Effects of Memory Access Tracking Granularity
Spiros I. Papadimitriou, Todd C. Mowry · 2001
Speculative execution is often the only way to overcome dataflow-imposed limitations and exploit par-allelism when dependences can be discovered only at run-time. It also facilitates automatic paralleliza-tion of programs that exhibit complicated memory access patterns, which make complete compile-time dependence analysis either impossible or extremely complicated. A number of approaches for coarse-grained data and control speculation have been proposed, mainly in hardware. A few software-only methods exist, but they usually rely on certain assumptions about control flow or memory access patterns. We investigate the possibility of supporting speculation in software, without making any such assumptions. The main motivation is the success of a number of software DSM systems. Our approach utilizes the virtual memory hardware to track memory opera-tions. The goal is to provide the necessary support through a software library, instead of specialized hardware. We found that a low overhead mechanism that can track memory accesses at a small gran-ularity is necessary, thus making the virtual memory mechanism unsuitable. In this paper we explore the various overheads and, in particular, those related to the granularity of memory access tracking.