Data Recomputation for Multithreaded Applications

Gulsum Gudukbay Akbulut, Mahmut T. Kandemir, Mustafa Karakoy, Wonil Choi

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish (US)
Title of host publication2023 42nd IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2023 - Proceedings
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9798350315592
StatePublished - 2023
Event42nd IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2023 - San Francisco, United States
Duration: Oct 28 2023Nov 2 2023

Publication series

NameIEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD
ISSN (Print)1092-3152


Conference42nd IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2023
Country/TerritoryUnited States
CitySan Francisco

All Science Journal Classification (ASJC) codes

  • Software
  • Computer Science Applications
  • Computer Graphics and Computer-Aided Design

Cite this