Data Recomputation for Multithreaded Applications

Increasing dataset sizes put tremendous pressure on cache hierarchies of multicore and manycore systems, which requires going beyond the current hardware and compiler-based data locality optimization techniques. Data recomputation, which aims to eliminate costly data accesses by replacing each such access with multiple, less costly data accesses plus some computation, is one such technique. However, existing data recomputation techniques are single-thread centric and they do not take advantage of the recomputation opportunities that exist across threads. We propose a novel compiler-guided data recomputation approach that works across threads. Our fully-automated approach has two major components. The first component catches the data recomputation opportunities enabled by a multithreaded execution and takes advantage of them. The second component implements a novel compiler-guided cache replacement strategy that is 'recomputation-aware'. The unique aspect of our strategy is that it makes its block/line replacement decisions in the cache based on not only recency information (as in the case of LRU) but also future data recomputation opportunities. Our proposed compiler algorithm improves application performance by an average of 13.25% over the conventional optimizations that do not use data recomputation and 7.68% over a single-thread centric data recomputation scheme. The corresponding improvements when also employing recomputation-conscious caching are 19.12% and 11.63%, respectively.