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 operations. 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 granularity 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.

28 pages

Return to: SCS Technical Report Collection
School of Computer Science homepage

This page maintained by [email protected]