---
_id: '6380'
abstract:
- lang: eng
text: '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. '
article_number: '53'
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Amir Kafshdar
full_name: Goharshady, Amir Kafshdar
id: 391365CE-F248-11E8-B48F-1D18A9856A87
last_name: Goharshady
orcid: 0000-0003-1702-6584
- first_name: Nastaran
full_name: Okati, Nastaran
last_name: Okati
- first_name: Andreas
full_name: Pavlogiannis, Andreas
id: 49704004-F248-11E8-B48F-1D18A9856A87
last_name: Pavlogiannis
orcid: 0000-0002-8943-0722
citation:
ama: Chatterjee K, Goharshady AK, Okati N, Pavlogiannis A. Efficient parameterized
algorithms for data packing. Proceedings of the ACM on Programming Languages.
2019;3(POPL). doi:10.1145/3290366
apa: Chatterjee, K., Goharshady, A. K., Okati, N., & Pavlogiannis, A. (2019).
Efficient parameterized algorithms for data packing. Proceedings of the ACM
on Programming Languages. ACM. https://doi.org/10.1145/3290366
chicago: Chatterjee, Krishnendu, Amir Kafshdar Goharshady, Nastaran Okati, and Andreas
Pavlogiannis. “Efficient Parameterized Algorithms for Data Packing.” Proceedings
of the ACM on Programming Languages. ACM, 2019. https://doi.org/10.1145/3290366.
ieee: K. Chatterjee, A. K. Goharshady, N. Okati, and A. Pavlogiannis, “Efficient
parameterized algorithms for data packing,” Proceedings of the ACM on Programming
Languages, vol. 3, no. POPL. ACM, 2019.
ista: Chatterjee K, Goharshady AK, Okati N, Pavlogiannis A. 2019. Efficient parameterized
algorithms for data packing. Proceedings of the ACM on Programming Languages.
3(POPL), 53.
mla: Chatterjee, Krishnendu, et al. “Efficient Parameterized Algorithms for Data
Packing.” Proceedings of the ACM on Programming Languages, vol. 3, no.
POPL, 53, ACM, 2019, doi:10.1145/3290366.
short: K. Chatterjee, A.K. Goharshady, N. Okati, A. Pavlogiannis, Proceedings of
the ACM on Programming Languages 3 (2019).
date_created: 2019-05-06T12:18:17Z
date_published: 2019-01-01T00:00:00Z
date_updated: 2024-03-25T23:30:18Z
day: '01'
ddc:
- '004'
department:
- _id: KrCh
doi: 10.1145/3290366
ec_funded: 1
file:
- access_level: open_access
checksum: c157752f96877b36685ad7063ada4524
content_type: application/pdf
creator: dernst
date_created: 2019-05-06T12:23:11Z
date_updated: 2020-07-14T12:47:29Z
file_id: '6381'
file_name: 2019_ACM_POPL_Chatterjee.pdf
file_size: 1294962
relation: main_file
file_date_updated: 2020-07-14T12:47:29Z
has_accepted_license: '1'
intvolume: ' 3'
issue: POPL
language:
- iso: eng
month: '01'
oa: 1
oa_version: Published Version
project:
- _id: 25892FC0-B435-11E9-9278-68D0E5697425
grant_number: ICT15-003
name: Efficient Algorithms for Computer Aided Verification
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
publication: Proceedings of the ACM on Programming Languages
publication_identifier:
issn:
- 2475-1421
publication_status: published
publisher: ACM
pubrep_id: '1056'
quality_controlled: '1'
related_material:
record:
- id: '8934'
relation: dissertation_contains
status: public
status: public
title: Efficient parameterized algorithms for data packing
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 3
year: '2019'
...