Fine-granular computation and data layout reorganization for improving locality

Mahmut Kandemir, Xulong Tang, Jagadish Kotra, Mustafa Karakoy

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

Abstract

While data locality and cache performance have been investigated in great depth by prior research (in the context of both high-end systems and embedded/mobile systems), one of the important characteristics of prior approaches is that they transform loop and/or data space (e.g., array layout) as a whole. Unfortunately, such coarsegrain approaches bring three critical issues. First, they implicitly assume that all parts of a given array would equally benefit from the identified data layout transformation. Second, they also assume that a given loop transformation would have the same locality impact on an entire data array. Third and more importantly, such coarse-grain approaches are local by their nature and difficult to achieve globally optimal executions. Motivated by these drawbacks of existing code and data space reorganization/optimization techniques, this paper proposes to determine multiple loop transformation matrices for each loop nest in the program and multiple data layout transformations for each array accessed by the program, in an attempt to exploit data locality at a finer granularity. It leverages bipartite graph matching and extends the proposed fine-granular integrated loop-layout strategy to a multicore setting as well. Our experimental results show that the proposed approach significantly improves the data locality and outperforms existing schemes - 9.1% average performance improvement in single-threaded executions and 11.5% average improvement in multi-threaded executions over the state-of-the-art.

Original languageEnglish (US)
Title of host publicationProceedings of the 41st IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2022
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9781450392174
DOIs
StatePublished - Oct 30 2022
Event41st IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2022 - San Diego, United States
Duration: Oct 30 2022Nov 4 2022

Publication series

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

Conference

Conference41st IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2022
Country/TerritoryUnited States
CitySan Diego
Period10/30/2211/4/22

All Science Journal Classification (ASJC) codes

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

Cite this