---
res:
  bibo_abstract:
  - 'There is a huge gap between the speeds of modern caches and main memories, and
    therefore cache misses account for a considerable loss of efficiency in programs.
    The predominant technique to address this issue has been Data Packing: data elements
    that are frequently accessed within time proximity are packed into the same cache
    block, thereby minimizing accesses to the main memory. We consider the algorithmic
    problem of Data Packing on a two-level memory system. Given a reference sequence
    R of accesses to data elements, the task is to partition the elements into cache
    blocks such that the number of cache misses on R is minimized. The problem is
    notoriously difficult: it is NP-hard even when the cache has size 1, and is hard
    to approximate for any cache size larger than 4. Therefore, all existing techniques
    for Data Packing are based on heuristics and lack theoretical guarantees. In this
    work, we present the first positive theoretical results for Data Packing, along
    with new and stronger negative results. We consider the problem under the lens
    of the underlying access hypergraphs, which are hypergraphs of affinities between
    the data elements, where the order of an access hypergraph corresponds to the
    size of the affinity group. We study the problem parameterized by the treewidth
    of access hypergraphs, which is a standard notion in graph theory to measure the
    closeness of a graph to a tree. Our main results are as follows: We show there
    is a number q* depending on the cache parameters such that (a) if the access hypergraph
    of order q* has constant treewidth, then there is a linear-time algorithm for
    Data Packing; (b)the Data Packing problem remains NP-hard even if the access hypergraph
    of order q*-1 has constant treewidth. Thus, we establish a fine-grained dichotomy
    depending on a single parameter, namely, the highest order among access hypegraphs
    that have constant treewidth; and establish the optimal value q* of this parameter.
    Finally, we present an experimental evaluation of a prototype implementation of
    our algorithm. Our results demonstrate that, in practice, access hypergraphs of
    many commonly-used algorithms have small treewidth. We compare our approach with
    several state-of-the-art heuristic-based algorithms and show that our algorithm
    leads to significantly fewer cache-misses. @eng'
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Krishnendu
      foaf_name: Chatterjee, Krishnendu
      foaf_surname: Chatterjee
      foaf_workInfoHomepage: http://www.librecat.org/personId=2E5DCA20-F248-11E8-B48F-1D18A9856A87
    orcid: 0000-0002-4561-241X
  - foaf_Person:
      foaf_givenName: Amir Kafshdar
      foaf_name: Goharshady, Amir Kafshdar
      foaf_surname: Goharshady
      foaf_workInfoHomepage: http://www.librecat.org/personId=391365CE-F248-11E8-B48F-1D18A9856A87
    orcid: 0000-0003-1702-6584
  - foaf_Person:
      foaf_givenName: Nastaran
      foaf_name: Okati, Nastaran
      foaf_surname: Okati
  - foaf_Person:
      foaf_givenName: Andreas
      foaf_name: Pavlogiannis, Andreas
      foaf_surname: Pavlogiannis
      foaf_workInfoHomepage: http://www.librecat.org/personId=49704004-F248-11E8-B48F-1D18A9856A87
    orcid: 0000-0002-8943-0722
  bibo_doi: 10.1145/3290366
  bibo_issue: POPL
  bibo_volume: 3
  dct_date: 2019^xs_gYear
  dct_isPartOf:
  - http://id.crossref.org/issn/2475-1421
  dct_language: eng
  dct_publisher: ACM@
  dct_title: Efficient parameterized algorithms for data packing@
...