M.Sc Thesis

M.Sc StudentFuchs Adi
SubjectDifferentials: Loop Aware Prefetching Using Memory Working-
Set Compaction and Prediction
DepartmentDepartment of Electrical and Computer Engineering
Supervisors ASSOCIATE PROF. Yoav Etsion


Current memory prefetching techniques do not associate memory locations with specific code blocks. Instead, they are tuned to predict streams of memory addresses that will likely be accessed in the near future. The memory streams are then opportunistically prefetched into the processor caches to potentially eliminate future cache misses, irrespective of the code blocks that will use them.This thesis presents a novel memory prefetching technique that predicts the working set associated with pending loop iterations.

The scheme presented constructs code block working sets (CBWS), which constitute the stream of addresses accessed by a dynamic instance of a code block.Our prefetcher is based on the observation that code block working sets are highly interdependent across tight loop iterations.

The CBWS prefetcher is evaluated using a set of memory intensive benchmarks from the SPEC 2006, PARSEC, SPLASH and PARBOIL suites. Our evaluation shows that CBWS-based prediction accuracy is higher than all other schemes tested, and that integrating CBWS into an existing scheme saves an average 56% fraction of the wrongly predicted prefetches.

Finally, evaluation shows that applying CBWS prefetching on loops speeds up overall execution by up to 4.00x (1.24x average on all benchmarks), compared to the best performing prefetcher tested.