Dynamic Concurrency Discovery for Very Large Windows of Execution

Dynamically finding parallelism in sequential applications with hardware mechanisms is typically limited to short windows of execution due to resource limitations. This is because pre-cisely keeping track of memory dependences is too expensive. We propose trading off precision for efficiency. The key idea is to encode a superset of the dependences in a way that saves storage and makes traversal for concurrency discovery efficient. Our proposal includes two alternative hardware structures: the first is a FIFO of Bloom Filters; the second is an imprecise map of memory addresses to timestamps that summarizes de-pendences on-the-fly. Our evaluation with SPEC2006 applica-tions shows that they lead to little imprecision in the dependence graph and find similar parallelization opportunities as an exact approach. 1