Krishnendu Chatterjee
email: krishnendu.chatterjee@ist.ac.at

Kafshdar Amir

Nastaran Goharshady
email: nastaran.okati@mail.um.ac.ir

Andreas Okati

Pavlogiannis

Andreas Pavlogiannis
email: andreas.pavlogiannis@epfl.ch.

A K Goharshady
email: amir.goharshady@ist.ac.at

N Okati

Efficient Parameterized Algorithms for Data Packing

Keywords:

come

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.

Additional Key Words and Phrases: compilers, data packing, cache management, parameterized algorithms, data locality

INTRODUCTION

We consider the problem of Data Packing over a two-level memory system consisting of a small cache and a large main memory. Given a reference sequence of memory accesses to data elements, the goal is to organize the data elements into blocks in order to minimize cache misses. Intuitively, putting contemporaneously-accessed elements in the same block reduces the number of cache misses, but existing heuristic-based results do not present any theoretical guarantees. In this paper, we consider this problem from a theoretical perspective and establish its complexity by presenting exact algorithms and stronger hardness results. We also complement our theoretical results with an experimental evaluation.

• Profiling: Programs usually have similar memory-access behaviors over different inputs [START_REF] Petrank | The hardness of cache conscious data placement[END_REF]. Hence, an effective approximate approach for the online cache management problem is to consider several representative inputs, then run an optimal offline algorithm for profiling, and then synthesize an answer to the online problem from optimal offline solutions [START_REF] Calder | Cache-conscious data placement[END_REF][START_REF] Petrank | The hardness of cache conscious data placement[END_REF]. Previous theoretical results on data packing have all been negative (hardness) results.

Heuristics and Affinity. Given the hardness of cache management and Data Packing, the research in this area has been mostly focused on developing heuristics. The intuition behind many of these heuristics is to exploit the underlying affinities between data elements or blocks by trying to place elements that are commonly accessed together in the same block or evicting the block that is less frequently accessed in conjunction with the rest of the blocks in the cache [START_REF] Calder | Cache-conscious data placement[END_REF][START_REF] Ding | Improving cache performance in dynamic applications through data and computation reorganization at run time[END_REF][START_REF] Ding | CApRI: CAche-conscious data reordering for irregular codes[END_REF][START_REF] Han | Exploiting locality for irregular scientific codes[END_REF][START_REF] Zhong | Array regrouping and structure splitting using whole-program reference affinity[END_REF]. Some approaches, such as [START_REF] Zhang | A hierarchical model of data locality[END_REF]], provide more sophisticated heuristics and construct a hierarchy of affinities. However, none of the existing heuristics provide any theoretical guarantees.

Access Graphs. The concept of access graph [START_REF] Borodin | Competitive paging with locality of reference[END_REF] has been introduced to model the affinities between data elements or blocks. An access graph is simply a graph in which there is a vertex corresponding to every data item and two vertices are connected by an edge if their respective items appear consecutively in the reference sequence. Access graphs might be weighted to model how many times every pair of elements have appeared consecutively. Similar structures and extensions of access graphs to access hypergraphs have been introduced in [START_REF] Lavaee | The hardness of data packing[END_REF][START_REF] Khalid | Cache management by the compiler[END_REF] where they are called proximity (hyper)graphs. Moreover, most of the heuristic-based approaches also consider variants of the notion of access graphs.

Cache Misses vs Cache Hits. We consider the Data Packing problem, which asks to minimize the cache misses. Its natural dual problem is to maximize cache hits. While the two problems are equivalent in case of exact algorithms, an approximation algorithm for maximum cache hits does not necessarily lead to an approximation for minimum cache misses [START_REF] Lavaee | The hardness of data packing[END_REF]]. For example, if in an access sequence of length N we have N -

√

N cache hits and √ N cache misses, an approximation of N -√ N hits can lead to an arbitrarily bad approximation of √ N cache misses. In practice, cache misses occur much less frequently than cache hits, but contribute significantly to the overhead. Thus, approximation of cache misses is more important than approximation of cache hits, and the Data Packing problem is defined in terms of cache misses.

Previous Results on Cache Management. To the best of our knowledge, all theoretical results on minimizing cache misses are negative or hardness results. We summarize some of the main results in this area. Given a reference sequence R of length N and a cache with a capacity of m blocks, the following results have been shown:

(i) In [START_REF] Petrank | The hardness of cache conscious data placement[END_REF], the authors considered the problem of Cache-conscious Data Placement, which is a somewhat different formulation of cache-miss minimization and is intuitively similar and related to Data Packing. In Cache-conscious Data Placement, a cache consists of m lines, each capable of holding up to p data items at any given time. The problem is to assign each data item d to a cache line l d . When the program wants to access the data item d, it should be present in cache line l d , otherwise a cache miss occurs and d is copied to l d , potentially by evicting another data item from l d . Given an eviction strategy, the goal is to assign data items to cache lines in a manner that minimizes cache misses. In [START_REF] Petrank | The hardness of cache conscious data placement[END_REF] it was shown that the problem is NP-hard and unless P=NP, it cannot even be approximated within a factor of O(N 1-ϵ ).

(ii) In the same paper, it was shown that any algorithm that does not process the entire sequence, but instead relies on pairwise affinity information on data items, such as the access graph, cannot find a solution within a factor of m -3 from the optimal, even with unbounded time. (iii) In [START_REF] Lavaee | The hardness of data packing[END_REF]], the author showed that Data Packing is NP-hard for any cache size and hard to approximate within a factor of O(N 1-ϵ ) unless P = NP. Given these hardness results, Data Packing is usually handled by heuristic-based algorithms that do not provide any theoretical guarantee. The only positive theoretical result deals with approximating maximum cache hits: (iv) In [START_REF] Lavaee | The hardness of data packing[END_REF]] it was established that the dual problem of Data Packing with the goal of maximizing cache hits, instead of minimizing cache misses, is approximable within a constant factor. However, this does not approximate the optimal number of cache misses. Exploiting Structural Properties. Data Packing is a notoriously difficult computational problem. In dealing with this problem, a direction that has not been pursued is to exploit structural properties of the access graphs. In many cases, structural properties of graphs help in obtaining efficient parametrized algorithms for computationally-hard problems. Specifically, a well-studied structural property in graph theory, which is frequently applied to computationally-hard graph problems, is the notion of treewidth. We present this notion below. Treewidth. Treewidth [START_REF] Robertson | Graph minors. III. Planar tree-width[END_REF] is a well-known and extensively-studied parameter in graph theory. The treewidth of a graph is a measure of how tree-like the graph is. Specifically, trees and forests are the only graphs with a treewidth of 1. The importance of treewidth in algorithm design stems from the fact that many NP-hard graph problems (e.g., Vertex Cover and Hamiltonian Cycle) can be solved in polynomial time if the input graphs have constant treewidth and moreover, many other graph problems can be solved in a lower complexity [START_REF] Abboud | Approximation and fixed parameter subquadratic algorithms for radius and diameter in sparse graphs[END_REF][START_REF] Hans | Treewidth: Algorithmic techniques and results[END_REF][START_REF] Chatterjee | Algorithms for Algebraic Path Properties in Concurrent Systems of Constant Treewidth Components[END_REF][START_REF] Cygan | Parameterized algorithms[END_REF][START_REF] Fedor V Fomin | Fully polynomial-time parameterized computations for graphs and matrices of low treewidth[END_REF][START_REF] Robertson | Graph minors. II. Algorithmic aspects of tree-width[END_REF]. The formal definition of treewidth is presented in the next section. Treewidth in Program Analysis. Many important families of graphs that arise commonly in algorithm design are shown to have constant treewidth, e.g., series-parallel and outer-planar graphs [START_REF] Hans | A partial k-arboretum of graphs with bounded treewidth[END_REF]]. Perhaps the most important example in program analysis is that the control-flow graphs of structured goto-free programs in many languages such as Pascal and C++ have constant treewidth [START_REF] Thorup | All structured programs have small tree width and good register allocation[END_REF]]. The same result was also shown experimentally for most Java programs [START_REF] Gustedt | The treewidth of Java programs[END_REF]. This led to algorithmic advances in verification and program analysis [Chatterjee et al. 2015a]. Moreover, treewidth has also been exploited to obtain faster algorithms for static analysis of recursive state machines [Chatterjee et al. 2015b] and concurrent systems [START_REF] Chatterjee | Algorithms for algebraic path properties in concurrent systems of constant treewidth components[END_REF][START_REF] Chatterjee | JTDec: A Tool for Tree Decompositions in Soot[END_REF]. Treewidth in Data Packing. In this work we show that Data Packing can be reduced to a graph problem. In many cases when a graph arises from a structured process, the treewidth of the graph is not very large [START_REF] Hans | A partial k-arboretum of graphs with bounded treewidth[END_REF]]. For Data Packing, the access graphs arise from structured program accessing data from a well-defined data structure. Thus, it is natural to study the problem of Data Packing in terms of the treewidth property of the arising graphs, as we do in this work. Our Contributions. Our contributions include (a) polynomial algorithms for Data Packing in constant treewidth access (hyper)graphs, (b) stronger hardness results, and (c) experimental results demonstrating that our approach leads to considerably fewer cache misses in comparison with previously-known heuristic-based approaches. Concretely, consider that the cache has size m, every block can hold p data items and the reference sequence is of length N with n distinct items. We consider the access hypergraph of order q, where each vertex of the graph is a data item, and an edge connects a set of q distinct data items if they appear contiguously in the reference sequence. We show that the Data Packing problem can be reduced to a graph partitioning problem of the Here m is the cache size and q is the highest order for which the access hypergraph has constant treewidth. For a formal definition of order see Section 2.1. Theorem 2.1 was established in [START_REF] Lavaee | The hardness of data packing[END_REF]]. The rest of the picture is filled by this paper. Our results are shown in bold.

access (hyper)graph and we study whether the constant treewidth property can be exploited for polynomial-time algorithms. Our main results, assuming constant m and p, are as follows:

(1) Results on Access Graphs. We first consider q = 2. Note that order-2 access hypergraphs are basically access graphs. We establish the following results:

• Linear-time algorithm. We present a linear-time algorithm for Data Packing when the access graph is of constant treewidth and m = 1 (Theorem 3.1). • Hardness of the exact problem. The Data Packing problem remains NP-hard for m ≥ 2 and p ≥ 3 even if the underlying access graph is a tree (which has treewidth 1) (Theorem 3.2). • Hardness of approximation. Unless P=NP, for any m ≥ 6, p ≥ 2 and any constant ϵ > 0, the Data Packing problem is hard to approximate within a factor of O(N 1-ϵ ) even if the underlying access graph is a tree (Theorem 3.2). (2) Results on Access Hypergraphs. We define access hypergraphs of higher orders and consider their treewidth. Let q * = (m -1)p + 2. Note that q * depends only on the cache parameters, and not on n or N . We consider the access hypergraph of order q * . Intuitively, every edge of this access hypergraph contains all the necessary historical cache data for determining whether a miss occurs at a corresponding memory access. Formally, we establish the following results:

• Linear-time algorithm. We present a linear-time algorithm for Data Packing when the access hypergraph of order q * has constant treewidth (Theorem 4.1). • Hardness of the exact problem. For m ≥ 2 and p ≥ 3, the Data Packing problem remains NP-hard even if the access hypergraph of order q * -1 has constant treewidth (Theorem 4.2). • Hardness of approximation. Unless P=NP, for m ≥ 6 and p ≥ 2 and any constant ϵ > 0, the Data Packing problem is hard to approximate within a factor of O(N 1-ϵ ) even if the access hypergraph of order q * -4p -1 has constant treewidth (Theorem 4.3). Note that while constant treewidth has been exploited to obtain polynomial-time algorithms for NP-complete graph problems such as Vertex Cover and Hamiltonian Cycle, we show that for Data Packing the constant treewidth property does not always help, and the problem remains hard even when the access hypergraph of order q * -1 has constant treewidth. Our hardness result and linear-time algorithm present a sharp boundary (or fine-grained dichotomy) that shows when the treewidth can be exploited. Concretely, the hardness of the Data Packing problem can be captured by a single parameter, namely, the highest order amongst access hypergraphs that have constant treewidth. We establish the optimal value q * of this parameter which is the necessary and sufficient condition for existence of efficient parameterized algorithms that exploit treewidth.

(3) Experimental results. We present an experimental evaluation of a prototype implementation of our algorithm on a variety of benchmarks from linear algebra, sorting algorithms, dynamic programming, recursive algorithms, string matching, computational geometry and algorithms on tree data-structures. Our results show that the access hypergraphs of most of the benchmarks have small treewidth. We compare our approach with several state-of-theart heuristic-based algorithms. The experimental results show that on average our optimal algorithms obtain 15-30% imporvement over the previous heuristic-based approaches. Novelty and Significance. In this paper, we define a novel and rich structural property of programs, i.e. access hypergraphs and their treewidth, and show that it can be exploited to obtain faster algorithms for Data Packing. We present the first positive theoretical results for Data Packing, i.e., for cache-miss minimization. We also enrich the complexity landscape as shown in Figure 1. Only the results of Theorem 2.1 were known before, and all other results (which are shown in bold) are established in the present work.

PRELIMINARIES

Data Packing

In this section, we define the problem of data packing and fix our notation. We also present several previously-known results. The problem was first studied in [START_REF] Khalid | Cache management by the compiler[END_REF]]. Here, we present an adaptation of its definition as formalized in [START_REF] Lavaee | The hardness of data packing[END_REF]]. Notation. We use Z to denote the set of integers and N to denote the set of positive integers. Let G = (V , E) be a (hyper)graph, and X ⊆ V , then we denote by G[X ], the induced subgraph of G over X , i.e. G[X ] = (X , {e ∈ E | e ⊆ X }). Given two (hyper)graphs G 1 = (V 1 , E 1 ) and G 2 = (V 2 , E 2 ), we define their union and intersection in the natural way, i.e.

G 1 ∪ G 2 = (V 1 ∪ V 2 , E 1 ∪ E 2 ) and G 1 ∩G 2 = (V 1 ∩V 2 , E 1 ∩ E 2 ).
If F is a family of sets, we write ∪F (resp. ∩F ) to denote ∪ A∈ F A (resp. ∩ A∈ F A). Given two functions f , д : A → Z, equality and summation are defined in a pointwise manner, i.e. f ≡ д ⇔ ∀a ∈ A; f (a) = д(a) and for any a ∈ A, we have (f + д)(a) = f (a) + д(a). Given a function f : A → B and a subset A ′ ⊆ A, we use f |A ′ to denote the restriction of f to A ′ . This restriction is a function of the form f |A ′ : A ′ → B that agrees with f on every point in A ′ . For a set X , we write P(X ) to denote the power set of X , i.e., the set of all subsets of X . Data Placement Schemes. Given a set D of size n of data items and a positive integer p, a data placement scheme σ is a partitioning of D into blocks of size at most p. We call p the packing factor. It is often useful to think of σ as an equivalence relation on D whose equivalence classes are the blocks. Hence, following the usual notation, we write xσy to denote that x and y are in the same block, [x] σ to denote the block of σ that contains the data element x and D/σ to denote the set of blocks or equivalence classes of σ .

Replacement Policies. Given a set D of n data items, a cache of size m, a data placement scheme σ , and a sequence R ∈ D N of accesses to data items, a replacement policy is a function that decides which block must be evicted from the cache at each time. Formally, a replacement policy is a function π : {0, 1, 2, . . . , N } → P(D/σ ) that assigns to each time point i, the set of blocks that are present in the cache right after the access R[i]. Any such policy must satisfy the following:

• π (0) = ∅, i.e. the cache must be empty at the beginning;

• For all 1 ≤ i ≤ N , |π (i)| ≤ m, i.e. there are at most m blocks in the cache at each time;

• For all 1 ≤ i ≤ N , |π (i) \ π (i -1)| ≤ 1 and |π (i -1) \ π (i)| ≤ 1, i.e. at most one block can be added to the cache and at most one block can be evicted at each step; • For all 1 ≤ i ≤ N , R[i] ∈ ∪π (i), i.e. the block containing an access R[i] must be in the cache right after that access.

Remark 2.1. Note that the replacement policy only matters when the cache has a size of at least 2. When the cache has unit size, there is always a unique choice for the block that must be evicted.

Cache Misses. Given a data placement scheme σ and a replacement policy π as above, the number of cache misses caused by σ and π over R is defined as the number of times a new block is loaded into the cache. Formally, misses(σ , π

) = | {i | 1 ≤ i ≤ N , π (i) \ π (i -1) ∅} |.
The LRU Policy. Due to its popularity, we assume throughout this paper that the replacement policy is LRU, i.e. the Least-Recently-Used block is always evicted from the cache. However, most of our results carry over to First-In-First-Out (FIFO) and the Optimal Offline Policy (OOP), as well. Recall that FIFO evicts the oldest block in the cache and OOP evicts the block that is going to be used furthest in the future. The Data Packing Optimization Problem. Consider a memory subsystem that consists of n distinct data elements and a fully-associative cache with a capacity of m blocks and a packing factor of p. Given a sequence R of length N of references to data elements, the Data Packing problem asks for a data placement scheme σ that minimizes the number of cache misses incurred by the reference sequence R, using LRU as the replacement policy. We denote an instance of the Data Packing problem by I = (n, m, p, R). Parameters. In the sequel, we consider the parameters m and p to be small constants and try to find polynomial algorithms in terms of N and n.

We now define the concepts of access graph and access hypergraph. Various similar notions have been defined in the past, and are sometimes called affinity graphs or proximity graphs. These hypergraphs will later serve as a basis for reducing the Data Packing problem to a graph problem. Access Graph. Given a sequence R of length N of accesses to data elements from a set D of size n, the access graph of R is a simple graph G R = (V , E) in which V consists of n vertices, each corresponding to one of the data elements in D, and there is an edge between two distinct vertices iff their corresponding data elements appear consecutively somewhere in R. More formally, {u, v} ∈ E iff u v and there exists an index i, such that {R

[i], R[i + 1]} = {u, v}.
Intuitively, one can think of the graph G R as the structure on data elements that is respected by the access sequence R, in the sense that R can only go from a vertex in G R to one of its neighbors. Moreover, G R is the sparsest graph over which R is a (non-simple) path. b,c,a,b,b,d,b,d,e,c,b,f >. There are 6 data elements in this sequence and its access graph G R is shown in Figure 2. Note that R is a path on this graph and every edge appears somewhere along R, hence no subgraph of G R has the same property. We now extend the concept of access graphs to higher order affinity relations between data items, resulting in access hypergraphs. Hypergraphs and Ordered Hypergraphs. A hypergraph G = (V , E) consists of a set V of vertices and a multiset E of hyperedges. Each hyperedge e ∈ E is in turn a subset of the vertices of G. An ordered hypergraph G = (V , E) consists of a set V of vertices and a set E of ordered hyperedges. Each ordered hyperedge e ∈ E is a sequence of distinct vertices of G, i.e. a hyperedge together with an order on its vertices. Intuitively, hypergraphs are natural extensions of graphs, where each edge can connect more than two vertices. Given a hypergraph G, its primal graph G p is a graph on the same set V of vertices, where two vertices u and v are connected by an edge iff there exists a hyperedge e ∈ E containing both u and v. We shall simply refer to hypergraphs and hyperedges as graphs and edges when there is no fear of confusion. Access Hypergraph. Given a natural number q and an access sequence R as above, the access hypergraph G q R = (V , E) is a hypergraph defined as follows:

• There are n vertices in V , each corresponding to one data element;

• For each data access R[i], there is a corresponding hyperedge e i in E. The hyperedge e i consists of R[i] and the q -1 distinct data elements that are accessed right before R[i]. If there are less than q -1 such elements, e i will include all of them. Concretely, e i is defined as follows:

e i := {R[j] | j ≤ i ∧ |{R[j], R[j + 1], . . . , R[i]}| ≤ q}.
We call q the order of the access hypergraph. It is easy to verify that removing repeated edges from the access hypergraph G 2 R leads to the access graph G R . Given an access sequence R as above, the ordered access hypergraph Ĝq R is defined similarly to G q R , except that each hyperedge is ordered in the natural way, i.e. in the order of appearance of its corresponding data elements in R. Formally, for every access

R[i], there is a corresponding ordered hyperedge e i in Ĝq R . The ordered hyperedge e i is a sequence < v 1 , v 2 , . . . , v l > of vertices of Ĝq R such that v l = R[i], v l -1 is the first distinct data element accessed before R[i], v l -2
is the second distinct element, etc. Moreover, l is the maximum between q and the number of distinct elements accessed up until R[i].

Tree Decompositions and Treewidth

In parameterized complexity, treewidth is one of the most widely-used parameters for graph problems. It is a measure of how "tree-like" a given graph is. In this section, we provide a quick overview of tree decompositions and treewidth. For an in-depth treatment see [START_REF] Cygan | Parameterized algorithms[END_REF]]. Tree Decomposition. Given a (hyper

)graph G = (V , E), a tree decomposition of G is a pair (T , {X t | t ∈ T })
where T is a tree and each node t of T is associated with a subset X t ⊆ V of vertices of G, such that the following conditions are met:

(i) Every vertex appears in some X t , i.e.

∪ t ∈T X t = V ; (ii) Every (hyper)edge appears in some X t , i.e. ∀e ∈ E ∃X t e ⊆ X t ; (iii) For every vertex v ∈ V , the set T v = {t ∈ T |v ∈ X t }
of all nodes of the tree T that contain v in their corresponding X t , forms a connected subtree of T . It is evident from the definition that (T , {X t }) is a tree decomposition of a hypergraph G iff it is a tree decomposition of its primal graph G p . To avoid confusion, we reserve the word "vertex" for vertices of G and use the word "node" for vertices of T . Moreover, we call each X t a "bag".

Treewidth. The width of a tree decomposition (T , {X t }) is the size of its largest bag minus 1, i.e. min t ∈T |X t | -1. The treewidth of a graph G is the smallest width among all tree decompositions of G and is denoted tw(G).

Example 2.4. Figure 5 shows the graph G R (as in Figure 2) and a tree decomposition of G R . This tree decomposition has a width of 2 and is an optimal tree decomposition. Hence, the treewidth of G R is 2. To simplify the algorithms that exploit tree decompositions, we now define the notions of labeling and nice tree decomposition. Nice Tree Decompositions. A nice tree decomposition [START_REF] Cygan | Parameterized algorithms[END_REF]] of a (hyper)graph G is a tree decomposition (T , {X t }) in which a specific node is designated as the root and every node t ∈ T is "labeled" by a subgraph G t of G, such that the following rules are obeyed:

(1) If t is a leaf in T , then X t = ∅ and G t = (∅, ∅).

(2) Otherwise, t satisfies one of the following cases:

• Join Node. The node t has two children, t 1 and t 2 ,

X t = X t 1 = X t 2 and G t = G t 1 ∪ G t 2 .
• Introduce Vertex Node. The node t has a single child t 1 and X t = X t 1 ∪ {v} for some vertex v X t 1 . In this case, we say that t introduces v. Moreover, G t = G t 1 ∪ {v}, i.e. G t is defined as the graph resulting from adding v as an isolated vertex to G t 1 . • Introduce Edge Node. Similar to the previous case, t has a single child t 1 . This time, X t = X t 1 , but G t is defined as the graph resulting from adding a new edge e to G t 1 . All vertices of e must be present in X t . We say that t introduces e. • Forget Vertex Node. The node t has a single child t 1 and X t = X t 1 \ {v} for some vertex v ∈ X t 1 . We say that t forgets v. Moreover, G t = G t 1 .

(3) Each edge is introduced exactly once. Intuitively, the label graph G t is the subgraph of G consisting of all the vertices and edges that are introduced in the subtree of T rooted at t. Remark 2.2. Note that in our (ordered) hypergraphs in this paper, we might have multiple copies of the same (ordered) hyperedge. We treat these as distinct edges and require that each of them be introduced separately in nice tree decompositions.

Remark 2.3. The notion of label graphs G t is solely defined for theoretical purposes and used in our proofs of correctness. In practice, our implementation avoids the overhead of constructing G t 's.

Example 2.5. Figure 6 shows a nice tree decomposition of the graph G of Figure 2. In each node t of the tree, its label subgraph G t is illustrated and the vertices of the bag X t are shown in red. Intuitively, a nice tree decomposition constructs the graph in small increments and the bag X t contains the vertices that can participate in the incremental change.

Existing Results

We now formally present known results regarding Data Packing and Tree Decompositions that will be used in the sequel. The Hardness of Data Packing. Note that we are considering the problem of minimizing cache misses, not that of maximizing cache hits. While the two problems are equivalent in terms of exact algorithms, approximating the minimal number of cache misses is much harder than approximating the maximal number of cache hits. The latter problem admits a polynomial-time constant-factor approximation [START_REF] Lavaee | The hardness of data packing[END_REF]]. In contrast, the following theorem shows that the former problem is hard to even approximate. Theorem 2.1 ( [START_REF] Lavaee | The hardness of data packing[END_REF]). Assuming either LRU, FIFO or OOP as the replacement policy, we have the following hardness results:

• For any m and any p ≥ 3, Data Packing is NP-hard.

• Unless P=NP, for any m ≥ 5, p ≥ 2 and any constant ϵ > 0, there is no polynomial algorithm that can approximate the Data Packing problem within a factor of O(N 1-ϵ ).

We now turn to tree decompositions. What makes tree decompositions a very useful tool is the fact that one can perform bottom-up dynamic programming on them in a manner similar to trees. This is due to an property of tree decompositions, called the separation lemma. Separators. Given a (hyper)graph G = (V , E), and two sets of vertices A, B ⊆ V , we say that the pair (A, B) is a separation of G if A ∪ B = V and no (hyper)edge in E contains vertices of both A \ B and B \ A. We call A ∩ B the separator corresponding to the separation (A, B) and the order of the separation (A, B) is the size of its separator |A ∩ B|.

Lemma 2.1 (Separation Lemma, [START_REF] Hans | Dynamic programming on graphs with bounded treewidth[END_REF][START_REF] Cygan | Parameterized algorithms[END_REF]). Let (T , {X t }) be a tree decomposition of G, where G is a graph or a hypergraph, and let {a, b} be an edge of T . By removing the edge {a, b}, T breaks into two connected components T a and T b , respectively containing a and b.

Let A = t ∈T a X t and B = t ∈T b X t . Then (A, B) is a separation of G with separator X a ∩ X b .
In our algorithms in the rest of this paper, we assume that whenever a (hyper)graph G of constant treewidth appears as an input to an algorithm, the input also contains an optimal nice tree decomposition (T , {X t }) of G. This is justified by the following two lemmas that show one can obtain (T , {X t }) from G in linear time.

Lemma 2.2 ([Bodlaender 1996] ).

There is an algorithm that given a (hyper)graph G = (V , E) and a constant k, decides in linear time whether G has treewidth at most k and if so, produces a tree decomposition of G with optimal width and O(k

• |V |) nodes.

DATA PACKING ON CONSTANT-TREEWIDTH ACCESS GRAPHS

We now consider the problem of Data Packing when parameterized by the treewidth of the underlying access graph. In Section 3.1, we provide a linear-time algorithm when m = 1 and the access graph has constant treewidth. Note that this problem is NP-hard for general access graphs, as demonstrated by Theorem 2.1. Then, in Section 3.2 we show that for m ≥ 2 the problem remains NP-hard and hard-to-approximate even when the access graph is a tree, i.e. has treewidth 1.

Algorithm for m = 1 and Constant-treewidth Access Graph

We are given a Data Packing instance I = (n, 1, p, R), its access graph G R and a nice tree decomposition (T , X t ) of the access graph with width k and O(n • k) nodes. We first reduce the problem of Data Packing to a graph problem over G R and then provide a linear-time fixed-parameter algorithm for solving the graph problem. We start by defining the minimum-weight p-partitioning problem. p-partitionings. Given an integer p > 0 and a graph G = (V , E), a p-partitioning of G is a partitioning ψ of the set V of vertices such that each partition set has a size of at most p. In other words, a p-partitioning of G is a data placement scheme where the vertices of G are the data elements and p is the packing factor. Cross Edges. Given a p-partitioning ψ of the graph G = (V , E), an edge e = {u, v} ∈ E is called a cross edge if its two endpoints are in different partition sets, i.e. if [u] ψ [v] ψ . Minimum-weight p-partitioning. Given a simple graph G = (V , E), a weight function w : E → N and a positive integer p, the minimum-weight p-partitioning problem asks for a p-partitioning of G in which the total weight of cross edges is minimized.

R : E → N as w R ({u, v}) := |{i | {R[i], R[i + 1]} = {u, v}}|.
Informally, the weight of an edge is the number of times its two endpoints have appeared consecutively in R. The reduction is now complete.

Lemma 3.1. The optimal number of cache misses in a Data Packing instance I = (n, 1, p, R) is 1 plus the total weight of cross edges in a minimum-weight p-partitioning of G R with weight function w R .

Proof. Every p-partitioning ψ of G R is a data placement scheme for I and vice versa. Given that m = 1, the replacement policy does not matter (Remark 2.1) and a cache miss occurs each time R accesses a new block. If we consider R as a path on G R , a cache miss occurs at the very beginning and then each time this path goes from one equivalence class of ψ to another. Therefore, the number of cache misses of ψ is 1 plus the total weight of cross edges in ψ .

□ Example 3.1. Consider the access sequence R =< a, b, c, a, b, b, d, b, d, e, c, b, f > of Example 2.
1 and the Data Packing instance I = (6, 1, 2, R), i.e. each block can store up to 2 data elements. Figure 7 shows the graph G R in which every edge is weighted by the number of times it is traversed in R. An optimal 2-partitioning of G R is shown in which vertices of the same color are in the same partition. The total weight of cross edges in this partitioning is 7. The corresponding data placement scheme is {{a, c}, {b, d }, {e}, { f }} which leads to 8 cache misses on R. The cache misses are underlined.

We will provide an algorithm for solving the Minimum-weight p-partitioning problem on a graph G using an optimal nice tree decomposition of G. Our algorithm employs a bottom-up dynamic programming technique. We first need several basic concepts to define the algorithm. States over a Set of Vertices. Given a graph G = (V , E), a natural number p and a subset A ⊆ V of vertices, a state over A is a pair s = (φ, sz) such that (i) φ is a partitioning of A in which every equivalence class has a size of at most p, and (ii) sz is a size enlargement function sz

: A/φ → {0, . . . , p -1} that maps each equivalence class [v] φ to a number which is at most p -|[v] φ |.
Intuitively, the idea is to take A to be one of the bags in the tree decomposition and later extend a state over A to a p-partitioning of G by adding the vertices in V \ A. So, a state over A partitions the vertices of A into sets of size at most p and for each partition [v] φ fixes the exact number sz([v] φ ) of vertices from V \ A that should be added to [v] φ . We denote the set of all states over A by S A,p or simply S A when p is clear from the context. Realization. We say that a p-partitioning ψ realizes the state s = (φ, sz) over A, if (i) the restriction of ψ to A is equal to φ, i.e. ψ |A = φ and (ii) for all vertices v ∈ A, sz ([v]

φ ) = |[v] ψ | -|[v] φ |.
Intuitively, ψ realizes s if (i) ψ partitions the vertices in A in the same manner as φ and (ii) if a partition [v] ψ of ψ intersects A, then [v] ψ contains as many vertices from outside of A as fixed by sz.

Example 3.2. Figure 8 shows all 14 possible states over the set A = {a, b, c} of vertices with p = 2. In each case, each row denotes one partition set and hence the order of rows and the order of squares in a row does not matter. Empty squares correspond to the possibility of extension of the set, as defined Compatibility. We say that two states s and s ′ , respectively over the sets A and A ′ , are compatible if there exists a p-partitioning that realizes both of them. We write s ⇆ s ′ to show compatibility.

Example 3.3. Intuitively, two states are compatible if they can fit into each other. Figure 9 shows the states realized by the 2-partitioning of Figure 7 above over the sets A = {a, b, c} and A ′ = {d, e, f } and how they can be fitted together to create the entire 2-partitioning.

Algorithm 1. We are now ready to describe our algorithm in detail. Given a graph G, a weight function w and an optimal nice tree decomposition T of G, our algorithm performs a bottom-up dynamic programming on T . This is broken into three steps.

Step 0: Initialization. We define several variables at each node of our tree T . These variables are meant to be computed in a bottom-up manner. Concretely, for every t ∈ T and every state s over the bag X t , we define a variable dp[t, s] and initialize it to +∞. Invariant. Formally, our algorithm satisfies the following invariant for every dp variable right after the end of its computation: dp[t, s] = The minimum total weight of cross edges over all p-partitionings of G t that realize s.

Intuitively, we are considering the states over the bag X t and extending them by adding vertices that were introduced in the subtree of t in T .

Step 1: Computation of dp. The algorithm starts from the bottom of the tree T and computes the dp variables bottom up, i.e. with an order such that for every node t ∈ T the dp variables at its children are computed before the dp variables of t. For every node t ∈ T and state s = (φ, sz) ∈ S X t , we show how dp[t, s] is computed based on the type of the node t: Note that the summation and equality above are pointwise. (1.3) if t is an Introduce Vertex node, introducing v, with a single child t 1 :

(1.1) if t is a Leaf: dp[t, s] = 0; (1.2) if
dp[t, s] = dp[t 1 , (φ |X t 1 , sz |X t 1 )];
(1.4) if t is an Introduce Edge node, introducing e, with a single child t 1 :

dp[t, s] = dp[t 1 , s] + w(e, φ),
where w(e, φ) is equal to w(e) if e is a cross edge in φ and zero otherwise;

(1.5) if t is a Forget Vertex node, forgetting v, with a single child t 1 :

dp[t, s] = min s ′ ∈S X t 1 ∧s ′ ⇆s dp[t 1 , s ′ ].
Recall that ⇆ denotes compatibility.

Step 2: Computing the Output. The algorithm computes the output, i.e. the optimal weight of a p-partitioning, using the values stored at dp variables. If r is the root node of T , then the algorithm outputs the following value: min s ∈S Xr dp[r , s]. This concludes Algorithm 1. We now prove the correctness of our algorithm.

Lemma 3.2. Algorithm 1 correctly computes the total weight of cross edges in a minimum-weight p-partitioning.

Proof. We prove this lemma in two steps. First, we show that the invariant defined above holds after computing dp[t, s] assuming that it was satisfied for all dp variables in the children of t (Correctness of Step 1). Then, assuming that the invariant holds for dp variables at the root, we show that the output is the total weight of an optimal p-partitioning (Correctness of Step 2).

Intuitively, the invariant says that if we only consider the graph G t , i.e. the part of G that was introduced in the subtree of T rooted at t, and those p-partitionings of G t that realize the state s, then dp[t, s] holds the minimum total weight of cross edges among these p-partitionings. Correctness of Step 1. As in the algorithm, we break this part into several cases: (1.1) Computations at Leaves. The node t is a leaf in T , hence G t is the empty graph and X t is the empty set. Therefore, S X t contains a single trivial state s ∅ and we have dp[t, s ∅ ] = 0 because the total weight of cross edges in an empty graph is zero. (1.2) Computations at Join Nodes. The node t is a join node with children t 1 and t 2 . We want to compute dp[t, s] where s = (φ, sz). Therefore, we only consider those p-partitionings that realize s. Given that X t = X t 1 = X t 2 , φ imposes itself on both X t 1 and X t 2 . However, each partition in φ must be extended by a number of vertices as defined by sz. These vertices must come from either G t 1 or G t 2 and must not already be present in X t . According to the separation lemma (Lemma 2.1), the only vertices that are in both G t 1 and G t 2 are precisely those of X t . Hence, each new vertex comes either from G t 1 or G t 2 but not from both. Therefore, we should minimize our total cross edge weights wrt dp variables of the form dp[t 1 , (φ, sz 1 )] and dp[t 2 , (φ, sz 2 )] where sz 1 +sz 2 ≡ sz. The function sz 1 defines the number of vertices that should be added from G t 1 -X t to each partition of φ and sz 2 does the same for G t 2 -X t . Formally, if we let w(φ) be the total weight of cross edges caused by φ in

G t 1 ∩ G t 2 = G t 1 [X t ] ∩ G t 2 [X t ],
then we should let:

dp[t, s] = dp[t, (φ, sz)] = min sz 1 +sz 2 ≡sz dp[t 1 , (φ, sz 1 )] + dp[t 2 , (φ, sz 2 )] -w(φ).
The reason we are subtracting w(φ) at the end is that the weights of its corresponding edges are taken into account twice, i.e. once in each of dp[t 1 , (φ, sz 1 )] and dp[t 2 , (φ, sz 2 )].

We now show it is always the case that w(φ) = 0. If an edge contributes to w(φ), then it must be present in both G t 1 and G t 2 . However, by property (3) of a nice tree-decomposition, each edge is introduced exactly once. Hence, G t 1 and G t 2 do not share any edges and w(φ) = 0.

G t = G t 1 , but X t = X t 1 \ {v}.
Correctness of Step 2. Given that r is the root node of T , we have G r = G. Since every ppartitioning of G realizes some state over X r , it follows that the optimal weight of a p-partitioning is min s ∈S Xr dp[r, s]. This concludes the proof. □ Remark 3.1. Algorithm 1 computes the total weight of cross edges in a minimum-weight ppartitioning. As is common with dynamic programming algorithms, an optimal p-partitioning itself can be obtained by keeping track of the choices made during the computation of dp variables, i.e. keeping track of the cases that led to the minimal values in each computation.

We now establish the complexity of our approach and present the main theorem of this section. Proof. Given a Data Packing instance I = (n, 1, p, R), we first apply the reduction of Lemma 3.1 which takes O(N ). We then use Algorithm 1 to solve the resulting minimum-weight p-partitioning problem. The correctness of this algorithm was established in Lemma 3.2. The only remaining part is to find the runtime of Algorithm 1. Note that the time spent for computing a nice tree decomposition, as in Lemmas 2.2 and 2.3 are linear and dominated by the rest of our runtime.

The algorithm needs values of dp variables for all nodes of the tree decomposition which are at most O(n • k). We obtain upper-bounds for the runtime of our algorithm on each type of node:

• Leaves. There is a single state at each leaf and its dp is zero. Hence we spend O(1) at each leaf.

(n • k 2 • C k • p k ) time.
Finally, the algorithm spends O(C k ) time computing the final result using the dp values at the root. □ Remark 3.2. By exploiting treewidth, we provided a linear-time algorithm for finding the exact solution to the Data Packing problem when m = 1. Note that in the general case, i.e. without considering parameterization by treewidth, this problem is NP-hard as mentioned in Theorem 2.1.

Remark 3.3. We assumed LRU as the replacement policy. However, given that the replacement policy does not matter when the cache has unit size (Remark 2.1), our algorithm is applicable to any replacement policy, including FIFO and OOP.

Hardness of Data Packing on Trees

In this section, we provide a reduction from the general problem of Data Packing to the special case where the access graph is a tree, i.e. has treewidth 1. This reduction leads to hardness results that enhance those of [START_REF] Lavaee | The hardness of data packing[END_REF]] by showing that the problem remains hard even on trees. This indicates that although considering constant treewidth access graphs led to efficient algorithms for the case of m = 1, constant treewidth access graphs alone are not sufficient for m ≥ 2. Theorem 3.2 (Hardness of Data Packing on Trees). Given a Data Packing instance I = (n, m, p, R), we have the following hardness results:

• Hardness of the Exact Problem. For any m ≥ 2 and any p ≥ 3, Data Packing is NP-hard even if the underlying access graph G R is a tree. • Hardness of Approximation. Unless P=NP, for any m ≥ 6, p ≥ 2 and any constant ϵ > 0, there is no polynomial approximation algorithm for the Data Packing problem with an approximation factor of O(N 1-ϵ ) even if the access graph G R is a tree.

Proof. We provide a linear-time reduction that transforms a Data Packing instance I = (n, m, p, R) to another instance I ′ = (n + (m + 1)p, m + 1, p, R ′ ) such that the access graph G R ′ is a tree. Both hardness results can then be obtained by applying this reduction to the hardness results of Section 2.1. Given I , we introduce (m + 1)p new data elements d 1 , d 2 , . . . , d (m+1)p . Let X be the sequence d 1 , d 2 , . . . , d (m+1)p , d (m+1)p-1 , . . . , d 1 . We form the sequence R ′ as follows:

d 1 , R[1], d 1 , R[2], d 1 , . . . , d 1 , R[N ], d 1 , X , X , . . . , X 2N +m+2 times ,
i.e. we take R and add d 1 at its beginning, end and between every two elements of it, then we concatenate the result with 2N + m + 2 copies of X . We let

I ′ = (n + (m + 1)p, m + 1, p, R ′ ).
Note that the cache in I ′ has one spot more than the cache of I . By construction, G R ′ is a tree, because it consists of a path d 1 , . . . , d (m+1)p and every other vertex of the graph is only connected to d 1 . We now show that the optimal number of cache misses in I ′ is exactly m + 1 plus the optimal number of cache misses in I .

Let σ be an optimal data placement scheme for I ′ , then σ must necessarily put the d i 's in exactly m + 1 blocks, otherwise each X in the sequence R ′ will lead to at least one cache miss for a total of at least 2N + m + 2. On the other hand, putting the d i 's in m + 1 blocks leads to at most 2N + m + 1 cache misses, even if all accesses before the X 's are missed. In particular, σ does not put any element of R in the same block as d 1 . Therefore, σ first leads to a cache miss on the first access to d 1 , then keeps d 1 in the cache forever. Hence, σ fills one spot of the cache with the block of d 1 and has m spots left for scheduling R. Finally, σ loads the other m blocks that contain some d i 's but not d 1 .

Hence, the number of cache misses caused by σ is 1 (for the first d 1 ) plus the optimal number of misses in I plus m (for the X 's). □ Remark 3.4. As mentioned before, we are considering the LRU replacement policy in this paper. However, the reduction above works for the OOP replacement policy as well. Hence, the hardness results are established for both policies.

DATA PACKING ON CONSTANT-TREEWIDTH ACCESS HYPERGRAPHS

In this section, we exploit constant treewidth of higher-order access hypergraphs for solving Data Packing. Section 4.1 extends our linear-time algorithm to every m, when the access hypergraph of order q * := (m -1)p + 2 has constant treewidth. As indicated by Theorem 2.1, this problem is hard to even approximate in the general case. In Section 4.2 we argue that q * is the optimal order for exploiting treewidth in the sense that the problem remains NP-hard even if the access hypergraph of order q * -1 has constant treewidth. This also leads to a new hardness-of-approximation result.

Algorithm for Constant-treewidth Access Hypergraph

In this section we extend the algorithm of Section 3.1 to any cache size m, provided that the hypergraph G q * R is of constant treewidth, where q * = (m -1)p + 2. Note that Theorem 3.2 implies such an extension cannot be made if we only consider constant-treewidth G R . Intuition on Cache Misses. The main intuition behind our algorithm is the following: given an instance I = (n, m, p, R) and a data placement scheme σ for I , we can deduce whether an access R[i] leads to a cache miss by looking at only the (m -1)p + 1 = q * -1 previous accesses to distinct data elements. We now formalize this intuition. Previous Access of a Block. Consider a Data Packing instance I = (n, m, p, R), a data placement scheme σ for I and an access R[i]. Let B := [R[i]] σ be the block of σ containing R[i]. We define prev σ (i) as the index of the previous access to B or 0 if no such access exists, i.e. prev σ (i)

:= max{j < i | j = 0 ∨ [R[j]] σ = [R[i]] σ }.
Lemma 4.1. Given a data placement scheme σ for I , an access R[i] leads to a cache miss if and only if prev σ (i) = 0 or there are at least m distinct blocks of σ whose elements appear in the range

R[prev σ (i) + 1] . . . R[i -1].
Proof. We are assuming LRU as the replacement policy and the cache starts empty. If prev σ (i) = 0, then R[i] is the first access to its block and will definitely lead to a cache miss. We now consider the case where prev σ (i) 0. Let j := prev σ (i) and assume that

B := [R[i]] σ = [R[j]] σ is the block containing R[i] and R[j]. By definition, none of the elements R[j + 1], . . . , R[i -1] belong to B. If there are at most m -1 blocks between R[j + 1] and R[i -1], then R[i]
cannot lead to a cache miss. This is because right after the access R[j], the block B is present in the cache and is the most recently used block of the cache. Hence, in order for it to be evicted, at least m other blocks must be accessed. On the other hand, if there are at least m blocks between R[j + 1] and R[i -1], then all of these blocks will be loaded into the cache and hence B will be evicted before the access R[i] leading to an eventual cache miss on R [i]. □ Corollary 4.1. Given a data placement scheme σ , an access R[i] and the q * -1 distinct elements that were accessed before R[i] (or all of the previous distinct elements if there is less than q * -1 of them) in the order of their last access time, one can deduce whether R[i] leads to a cache miss.

Proof. If R[prev σ (i)] is one of these previous elements, then we can simply check whether at least m different blocks appear between R[prev σ (i)] and R[i]. Otherwise, either R[i] is the first access to its block or all the q * -1 elements are appearing between R[prev σ (i)] and R[i]. In the first case R[i] leads to a cache miss. In the second case, by pigeonhole principle, there are at least m blocks between the two elements R[prev σ (i)] and R[i] and hence there is a cache miss at R[i]. □ Remark 4.1. Note that the previous access to the block containing R[i] might be an access to R[i] itself. Hence, R[i] might itself appear in the q * -1 distinct elements that were accessed before R[i].

As in Section 3.1, we are going to reduce Data Packing to a graph problem and then exploit treewidth to obtain a linear-time algorithm. Corollary 4.1 suggests that in order to detect cache misses, one only needs to consider the ordered access hypergraph of order q * = (m -1)p + 2, i.e.

Ĝq * R . However, in order to address the corner case mentioned in then the edge e i corresponding to R[i], will also contain R[j] (in its natural position according to the order of vertices in e i ).

Example 4.1. Consider the access sequence R =< d, c, a, b, c > and let m = p = 2. Hence, we have q * = (m -1)p + 2 = 4. In the graph Ĝq * R the edge corresponding to the second c is e 5 =< d, a, b, c >. However, there are less than q * distinct data elements appearing between the two accesses to c, i.e. there are only two such elements, namely, a and b. Hence, in G, the previous access to c appears in this edge as well. Therefore, in G, the edge e 5 is of the form e 5 =< d, c, a, b, c >.

The intuition behind the way G is defined comes from Corollary 4.1 and Remark 4.1. The idea is to have the edge e i contain all the data necessary to decide whether a cache-miss will happen at the access R [i]. We now formalize this concept. Missed Edges. Given an ordered hyperedge e i of G and a data placement scheme σ , we can deduce whether a cache miss happens at R[i] using Corollary 4.1, because the edge e i contains an ordered list of at least (m -1)p + 1 = q * -1 distinct data elements that were accessed right before R[i]. We say that an ordered hyperedge e i is missed in σ , if the corresponding R[i] is a cache miss. Identifying Missed Edges. Consider the data placement scheme σ as a p-partitioning of vertices of G. Based on Lemma 4.1 and Corollary 4.1, an ordered hyperedge e i =< v 1 , . . . , v l > is missed iff the sequence of vertices < v l , v l -1 , . . . , v 1 > in G visits at least m distinct partitions before getting back to the partition [v l ] σ or if it never comes back. Note that this determination can be done in O(m • p) and only depends on the p-partitioning of {v 1 , . . . , v l }.

We now define our graph problem as follows: Minimum-miss p-partitioning. Given a hypergraph G = (V , E) with ordered hyperedges, partition V into sets of size at most p in a manner that minimizes the number of missed edges.

As a direct result of the previous discussion, we have the following lemma:

Lemma 4.2. The optimal number of cache misses in a Data Packing instance I = (n, m, p, R) is equal to the optimal number of missed edges in a p-partitioning of G.

Proof. Any data placement scheme σ for I is also a p-partitioning of G. As shown above, σ misses an edge e i in G iff it causes a cache miss at R[i] in I . Hence, the number of cache misses caused by σ in I is equal to the number of missed edges caused by σ in G. □

States over a Set of Vertices. We define states in the exact same manner as in Section 3.1, i.e. a state over a set A of vertices is a pair s = (φ, sz) consisting of an equivalence relation φ and a size enlargement function sz. The concepts of realization and compatibility are also defined similarly. Algorithm 2. We now provide a linear-time algorithm for solving the Minimum-Miss p-partitioning problem, assuming that the hypergraph G has constant treewidth. The algorithm is an extension of the one provided in Section 3.1. In the following, we let (T , {X t |t ∈ T }) be an optimal nice tree decomposition of G. Our algorithm performs a bottom-up dynamic programming on T .

Step 0: Initialization. We define several variables at each node of the tree T . Concretely, for every node t ∈ T and every state s over X t , we define a variable dp[s, t], initially holding a value of +∞.

Invariant. The most different aspect of our algorithm compared to Section 3.1 is the invariant. Formally, we require our algorithm to satisfy the following invariant for every dp variable right after the end of its computation: dp[t, s] := The minimum number of missed edges over all p-partitionings of G t that realize s.

Step 1: Computation of dp. The dp variables are computed in a bottom-up manner. Given a node t ∈ T and a state s = (φ, sz) ∈ S X t , we show how dp[s, t] is computed in terms of the dp variables at the children of t. This computation depends on the type of the node t.

(1.1) if t is a Leaf: dp[t, s] = 0;

(1.2) if t is a Join node with children t 1 and t 2 :

dp[t, s] = min sz 1 +sz 2 ≡sz dp[t 1 , (φ, sz 1 )] + dp[t 2 , (φ, sz 2 )];
(1.3) if t is an Introduce Vertex node, introducing v, with a single child t 1 :

dp[t, s] = dp[t 1 , (φ |X t 1 , sz |X t 1 )];
(1.4) if t is an Introduce Edge node, introducing e, with a single child t 1 :

dp[t, s] = dp[t 1 , s] + 1 missed_edge(e, φ) 0 otherwise ;
(1.5) if t is a Forget Vertex node, forgetting v, with a single child t 1 :

dp[t, s] = min s 1 ∈S X t 1 ∧s 1 ⇆s dp[t 1 , s 1 ].
Recall that ⇆ denotes compatibility of states.

Step 2: Computing the Output. The algorithm computes the output, i.e. the minimum number of missed edges in a p-partitioning of G, using the values of dp variables at the root node r of T . Formally, the output is min s ∈S Xr dp [r , s].

This concludes Algorithm 2. While most of the computations are similar to Algorithm 1, the argument for correctness of Algorithm 2 and its runtime are rather different. We first prove the correctness of our approach and then establish its time complexity. Lemma 4.3. Algorithm 2 correctly computes the total number of missed edges in a Minimum-Miss p-partitioning.

Proof. Our proof heavily depends on the invariant defined above. Intuitively, the invariant says that dp[t, s] must be filled with the minimum number of edges that are missed in a p-partitiong realizing s, over the subgraph G t of G, which consists of all the vertices and hyperedges that are introduced below t in T . We prove the lemma in two steps. First, we prove that the invariant is satisfied after computing dp[t, s], assuming that it were satisfied for all dp variables in the children of t (Correctness of Step 1). Then, we prove that assuming the invariant holds for dp variables at the root node r of T , the algorithm computes the right output (Correcntess of Step 2). Correctness of Step 1. We break the proof into several cases: (1.1) Computations at Leaves. The node t is a leaf in T . So G t is the empty graph and hence there are no missed edges in G t . Moreover, there is exactly one state over X t , i.e. the trivial state s ∅ . Hence, we should let dp[t, s ∅ ] = 0. (1.2) Computations at Join Nodes. A join node t has two children t 1 and t 2 with

X t = X t 1 = X t 2 .
When computing the value of dp[t, s] for a state s = (φ, sz), we only have to consider those states over X t 1 and X t 2 that are compatible with s. However, X t 1 = X t 2 = X t , hence the partitioning φ is also imposed on X t 1 and X t 2 . The function sz specifies how many new vertices must be added to each partition of φ from G t 1 and G t 2 . Note that by the separation lemma (Lemma 2.1), the only vertices that belongs to both G t 1 and G t 2 are already included in X t , hence no new vertex can be in both. Therefore, we have to look into dp variables of the form dp[t 1 , (φ, sz 1 )], dp[t 2 , (φ, sz 2 )] where sz 1 + sz 2 ≡ sz. Concretely, we should let:

dp[t, s] = dp[t, (φ, sz)] = min sz 1 +sz 2 ≡sz dp[t 1 , (φ, sz 1 )] + dp[t 2 , (φ, sz 2 )].
Note that the two graphs G t 1 and G t 2 do not share any edges as argued in Lemma 3.2. (1.3) Computations at Introduce Vertex Nodes. In this case, t is a node, with a single child t 1 , that introduces the vertex v. Then v G t 1 and G t = G t 1 ∪ {v}, i.e. G t is obtained by adding v to G t 1 as an isolated vertex. Given that G t has no new edges in comparison with G t 1 , it follows that the missed edges in G t are precisely those that were missed in G t 1 . Also, X t = X t 1 ∪ {v} and so given a state s = (φ, sz) over X t , there is only one compatible state over X t 1 , i.e.

s 1 = (φ |X t 1 , sz |X t 1 ). Therefore, we must let dp[t, s] = dp[t 1 , s 1 ].
(1.4) Computations at Introduce Edge Nodes. The node t has one child t 1 , X t = X t 1 and G t = G t 1 ∪ {e}, where e is the newly introduced hyperedge. Note that, by property (2) of nice tree decompositions, all vertices of e must appear in X t . So φ gives us enough information to know whether e is a missed edge. Also, given that X t 1 = X t , the state s forces itself on X t 1 and therefore, letting

dp[t, s] = dp[t 1 , s] + 1 missed_edge(e, φ) 0 otherwise .
preserves the invariant. (1.5) Computations at Forget Vertex Nodes. This case is handled in the exact same manner as in Section 3.1. Given that G t = G t 1 and X t ⊂ X t 1 , the value of dp[t, s] should be set to the minimum value of dp[t 1 , s 1 ] over all states s 1 that are compatible with s. Formally,

dp[t, s] = min s 1 ∈S X t 1 ∧s 1 ⇆s dp[t 1 , s 1 ].
Correctness of Step 2. Let r be the root node of T , then G r = G and every p-partitioning of G realizes exactly one state over X r . Hence, the minimum number of missed edges in the entire graph G is min s ∈S Xr dp [r , s]. □ Remark 4.2. Algorithm 2 computes the optimal number of missed edges in a p-partitioning of G. As is common in dynamic programming approaches, an optimal p-partitioning itself can be obtained by keeping track of the choices that led to minimum values during the computation of dp variables.

We conclude this section by establishing the complexity of Algorithm 2. Theorem 4.1. Given a Data Packing instance I = (n, m, p, R) as input, where n is the number of distinct data items, p is the packing factor, R is the reference sequence with a length of N and the cache has a capacity of m blocks, the Data Packing problem, i.e. finding the minimal number of cache misses, can be solved in linear time, i.e. in time O(n

• k 2 • C k • p k + N • C k • (k + m • p)),
(n • k 2 • C k • p k • +N • C k • (k + m • p)).
Finally, it takes O(C k ) time to compute the final answer using dp variables at the root node. □

Remark 4.3. The runtime above is linear in n and N , given that C k is bounded by a function of p and k (see Appendix A for bounds on C k ). Hence, by exploiting the treewidth of G, we were able to obtain an exact linear-time algorithm for Data Packing. Note that by Theorem 2.1, the general problem, i.e. without parameterization by treewidth, is hard to even approximate.

Remark 4.4. Note that every hyperedge of the access hypergraph G q * R connects q * distinct vertices. Hence, the treewidth of this access hypergraph is at least q * -1 = (m -1)p + 1. Both m and p are assumed to be constants. However, this dependency means that the algorithm cannot scale to caches of large size or large packing factor.

Hardness of Data Packing on Constant-treewidth Access Hypergraphs

In Section 3.2, we showed that Data Packing is hard even if the access graph G R is a tree, i.e. even if G 2 R has treewidth 1. Section 4.1 provided a linear-time algorithm for Data Packing when G q * R has constant treewidth. This naturally leads to the question whether q * = (m -1)p + 2 is the optimal order for exploiting treewidth. Note that this is a well-posed problem because for every i, the primal graph of

G i R is a subgraph of the primal graph of G i+1 R and hence tw(G i R ) ≤ tw(G i+1 R ).
Formally, the question is whether there exists a polynomial algorithm for Data Packing assuming that the hypergraph G q * -1 R has constant treewidth. In this section, we show that this problem is NP-hard and hence, unless P=NP, there is no such algorithm and q * is the optimal order. We then show that for a slightly smaller order, i.e. q * -4p -1 = (m -5)p + 1, the problem becomes hard to approximate. Proof. By Theorem 2.1, we know that Data Packing is NP-hard for any p ≥ 3 and m = 1. We use this problem to obtain our reduction. Formally, for every m, we provide a linear-time reduction that transforms the Data Packing instance I = (n, 1, p, R) to a new instance

I ′ = (n ′ , m, p, R ′ ) such that the access hypergraph G q * -1 R ′ is of constant treewidth.
constant ϵ > 0, unless P=NP, Data Packing cannot be approximated within a factor of O(N 1-ϵ ) even if the underlying access hypergraph G q * -4p-1 R = G (m-5)p+1 R has constant treewidth. Here, N is the length of the reference sequence R.

Proof. We know from Theorem 2.1 that for m = 5, and p ≥ 2, it is hard to approximate Data Packing within a factor of O(N 1-ϵ ). We reduce this problem to Data Packing on a constanttreewidth G (m-5)p+1 R

. Formally, for every m ≥ 6, we provide a linear-time reduction from every instance I = (n, 5, p, R) to an instance

I ′ = (n ′ , m, p, R ′ ) such that G (m-5)p+1 R ′
has constant treewidth. The reduction and the argument for its correctness are similar to those of Theorem 4.2. Given an instance I as above, we introduce (m + 5)p new data elements d 1 , d 2 , . . . , d (m+5)p . We then define the following four sequences in a manner similar to Theorem 4.2:

X := d 1 , d 2 , . . . , d (m-5)p , Y := d (m-5)p+1 , d (m-5)p+2 , . . . , d mp , Z := d mp+1 , d mp+2 , . . . , d (m+5)p ; R ′ := X , R[1], X , R[2], . . . , X , R[N ], X , Y , X , Y , . . . , X , Y a times , X , Z , X , Z , . . . , X , Z b times
, where a = N (m -5)p + N + 2m + 1 and b = N (m -5)p + N + amp + m + 1. The reduction is then from I = (n, 5, p, R) to I ′ = (n + (m + 5)p, m, p, R ′ ). It is straightforward to check that every optimal data placement scheme σ has to put each of X ∪ Y and X ∪ Z in exactly m blocks. Hence, it has to put X in exactly m -5 blocks. Therefore, the optimal number of cache misses in I ′ is m -5 (for loading the first X ) plus the optimal number of cache misses in I plus 10 (5 misses for loading the first Y and 5 for the first Z ). Finally, the same tree decomposition as in Figure 14, shows that tw(G

(m-5)p+1 R ′ ) ≤ mp -1 = O(1)
. □

IMPLEMENTATION AND EXPERIMENTAL EVALUATION

Implementation and Machine. We implemented our approach (i.e. Algorithms 1 and 2) in C++.

We used a Java library called LibTW [START_REF] Thomas Van Dijk | Computing treewidth with LibTW[END_REF]] to obtain the tree decompositions. All results are obtained using an Intel Xeon E5-1650v3 3.5GHz processor running 64-bit Debian 8.

Benchmarks. We used a variety of classical algorithms to generate the access sequences R for the Data Packing problem. For each classical algorithm, we generated random inputs of various sizes, which in turn led to random access sequences of varying lengths. We included algorithms from the following categories in our benchmark set: (i) linear algebra algorithms, (ii) sorting algorithms, (iii) dynamic programming, (iv) recursive algorithms, (v) string matching algorithms, (vi) computational geometry algorithms, (vii) algorithms on trees and (viii) algorithms on sorted arrays. For a complete list of the classical algorithms we used to generate benchmarks, see Appendix C. We implemented these classical algorithms in C++ and obtained reference sequences from their traces. Moreover, each generated sequence R was executed for all 1 ≤ m ≤ 5 and 2 ≤ p ≤ 5. We did excluded p = 1, because Data Packing is trivial in this case, i.e., each data item forms its own block. Treewidth of Benchmarks. We observed that in many cases, by increasing the length of the access sequence R, the treewidth of the access graph G R and the access hypergraph G q * R first slowly increase and then stabilize at a small value. Generally, we observe this phenomenon when the underlying data structure has small treewidth, which is the case in many real-world programs and most of our benchmarks. Figure 15 shows some of our benchmark algorithms, together with the treewidth of the resulting access (hyper)graphs of order q * . The benchmark at the bottom-right corner of Figure 15, i.e., finding the Closest Pair among a given set of points in the plane, is an example of a real-world algorithm that does not have small treewidth. Hence, while programs might not necessarily have access hypergraphs with small treewidth, programs that access lists or tree-like data structures tend to have this property and our algorithm can be applied to them. R wrt the length N of the access sequence R generated from several classical algorithms. We have slightly offset the lines in order to make sure all of them remain visible.

Previous Approaches. We implemented several different state-of-the-art heuristic-based algorithms for data placement. These include CCDP [START_REF] Calder | Cache-conscious data placement[END_REF]], CPACK [START_REF] Ding | Improving cache performance in dynamic applications through data and computation reorganization at run time[END_REF], CPACK+, GPART+, CApRI+ † [START_REF] Ding | CApRI: CAche-conscious data reordering for irregular codes[END_REF] and two methods based on affinity hierarchies, namely the k-Distance method of [START_REF] Zhong | Array regrouping and structure splitting using whole-program reference affinity[END_REF]] and the Sampling method of [START_REF] Zhang | A hierarchical model of data locality[END_REF]]. We apply the latter algorithm with a sampling rate of 1, i.e., the highest possible sampling rate, to obtain the minimal number of cache misses it can produce. To be able to compare the algorithms, we also implemented a virtual cache system to simulate and count the number of misses caused by each approach. Running Time. Note that the Data Packing formulation as considered in the literature [START_REF] Lavaee | The hardness of data packing[END_REF][START_REF] Khalid | Cache management by the compiler[END_REF] is an offline problem, and these algorithms run once, but the output data placement schemes can lead to a reduction of cache-miss overheads every time the instance is run. Thus the main goal is to obtain optimal results within reasonable time limit. We set a runtime limit of 5 minutes per instance for each of the algorithms. In cases where only a single heuristic fails to terminate within 5 minutes, we report the result of the best-performing heuristic instead. This ensures we do not unfairly report too many misses for a heuristic. With the time limit above, our algorithm produces results on 2726 instances, and in most of these cases, the previous known optimal algorithm, i.e., an exhaustive search, does not terminate even in a day. Experimental Results. Our experimental results over all instances are illustrated in Figure 16. Each row of Figure 16 shows a comparison between our algorithm and a number of heuristics. The x-axis denotes the optimal number of cache misses and the y-axis the number of cache misses incurred by the heuristic algorithm. Therefore, our algorithms' results correspond to the y = x line, and, as expected, all heuristic-based results are above or on this line, i.e., they lead to more † The + in the names of these algorithms comes from applying the CApRI method which takes a data placement scheme created by a previous heuristic as its input and attempts to optimize it and produce a better data placement scheme. CApRI+ is the result of applying CApRI to an initial data placement scheme with unary blocks. For more information, see [START_REF] Ding | CApRI: CAche-conscious data reordering for irregular codes[END_REF]. Fig. 16. Experimental Results over all instances. In each plot, the x-axis is the optimal number of cache misses, i.e., the number of cache misses incurred by our algorithm, and the y-axis is the number of cache misses incurred by the heuristic-based algorithm. Each dot corresponds to a single instance. Each row begins with a plot of all instances at the left and then zooms into areas with a high density of points (center and right).

cache misses than optimal. To give a better view of the results, each row starts with a full plot of all the instances (on the left) and then zooms into the areas with a high density of points (which correspond to the instances that led to relatively few cache misses). In this figure, we did not include the points corresponding to heuristics that timed out, e.g., Sampling timed out on several larger instances, therefore there are few blue points in the leftmost plot of the second row of Figure 16.

We found that in total, our algorithm reduces the number of cache misses by between 15% (over Sampling) to 31% (over k-Distance). We also found that our algorithm is effective on every category of benchmarks. These results are illustrated in Figure 17.

DISCUSSION AND CONCLUSION

We discuss some aspects of our results and conclude with some open directions. Remark 6.1. Note that while in our algorithms, we focused on LRU as the replacement policy, our results also extend to FIFO and OOP. In particular our first linear-time algorithm (Algorithm 1, Theorem 3.1) applies to all replacement policies, and our second linear-time algorithm (Algorithm 2, Theorem 4.1) applies both to LRU and FIFO, with minor modifications. In each case we report the number of cache misses incurred by an algorithm as a percentage of the optimal number of cache misses. The optimal total number of cache misses over all the instances was 145544. See Appendix C for all the numbers. We observe that there is no best heuristic that works better than others in all cases. Each heuristic-based algorithm works best on some specific categories of benchmarks. Our algorithm significantly outperforms the heuristics in all cases, and especially more so in benchmarks from Recursion, Computational Geometry and Sorted Arrays.

Remark 6.2. We studied if the treewidth property of access hypergraphs can be exploited for efficient algorithms for Data Packing. We showed a fine-grained dichotomy, i.e., we established an optimal value q * of the order of the access hypergraphs, such that (a) if the access hypergraph of order q * has constant treewidth, then Data Packing admits a linear-time algorithm; and (b) even if the access hypergraph of order q * -1 has constant treewidth, in general, the Data Packing problem remains NPhard. Moreover, we showed a hardness-of-approximation result that holds even if the access hypergraph of order q * -4p -1 has constant treewidth. These results are summarized in Figure 1 on Page 5. Remark 6.3. While we studied the treewidth property of access hypergraphs from a theoretical perspective, in the experimental results we observed that in practice, many real-world algorithms exhibit the desired property, i.e., the access hypergraphs of the required order have small treewidth. Thus the usefulness of parameterization by the treewidth property is also validated experimentally.

Concluding Remarks. In this work, we presented the first positive theoretical results and efficient parameterized algorithms for Data Packing. There are several directions of future work. First, whether other structural properties of access hypergraphs can be exploited for efficient algorithms is an interesting direction. Second, studying the extension of the Data Packing problem for multilevel caches and algorithms for them is another interesting direction. Third, while we provided linear-time algorithms for data packing in constant treewidth, their runtime dependency on constant factors m, p and the treewidth are non-polynomial. Improving this aspect of the runtime is another interesting direction of future work. Finally, studying the Data Packing problem in an online setting where the access sequence is not known in advance is a very challenging direction to pursue.

A BOUNDS ON THE NUMBER OF STATES

In this section, assuming a packing factor of p, we establish bounds on the number C k of states over the set {1, 2, . . . , k} of k vertices. We present two different bounds as lemmas: Consider a state s = (φ, sz) over {1, 2, . . . , k}. Either k is in a singleton partition in s or it is put together with some other elements of {1, 2, . . . , k -1}. In the former case, removing k leads to a state s ′ over {1, 2, . . . , k -1} that is compatible with s. In the latter, removing k and incrementing sz ([k] φ ) leads to a similarly compatible s ′ . Therefore, each state s over {1, 2, . . . , k} can be obtained by taking a state s ′ over {1, 2, . . . , k -1} and adding k to it either (i) as a separate partition with any sz value, or (ii) inside another partition that has an sz value of at least 1 and decrementing its sz value. Given a state s ′ , there are p ways of doing (i), corresponding to the different values that can be assigned to sz({k }), and at most k -1 ways of doing (ii), because there are at most k -1 partitions in s ′ . Hence,

C k ≤ (p + k -1) • C k -1 ≤ (p + k -1) • (p + k -2)! (p -1)! = (p + k -1)! (p -1)! .
For the last part, we have Proof. The bounds above can be obtained by applying Lemmas A.1 and A.2 to C k in Theorem 3.1. □

B PSEUDOCODES

In this section, we provide simple pseudocodes of the algorithms described above.

Algorithm 1: Computing the total weight of cross edges in an optimal p-partitioning 1 function Main (G,T , w, p); Input : A graph G = (V , E), a nice tree-decomposition T of G, a weight function w : E → N and a positive integer p. Output : Total weight of cross-edges in an optimal p-partitioning of G wrt w.

1

  Efficient Parameterized Algorithms for Data Packing KRISHNENDU CHATTERJEE, IST Austria (Institute of Science and Technology Austria), Austria AMIR KAFSHDAR GOHARSHADY, IST Austria (Institute of Science and Technology Austria), Austria NASTARAN OKATI, Ferdowsi University of Mashhad, Iran ANDREAS PAVLOGIANNIS, École Polytechnique Fédérale de Lausanne (EPFL), Switzerland

Fig. 1 .

 1 Fig. 1. The complexity of Data Packing for p ≥ 3.Here m is the cache size and q is the highest order for which the access hypergraph has constant treewidth. For a formal definition of order see Section 2.1. Theorem 2.1 was established in[START_REF] Lavaee | The hardness of data packing[END_REF]]. The rest of the picture is filled by this paper. Our results are shown in bold.

Example 2. 1 .

 1 Consider the access sequence R =< a,

Fig. 2 .

 2 Fig. 2. The access graph G R of R =< a, b, c, a, b, b, d, b, d, e, c, b, f >

Example 2. 2 .

 2 Fig. 3. Segments of R corresponding to edges in the hypergraph G 3 R

Example 2. 3 .Fig. 4 .

 34 Fig. 4. Ordered Hyperedges of G and the segments in R to which they correspond

Fig. 5 .

 5 Fig.5. A graph G R (left) and one of its optimal tree decompositions (T , {X t }) (right).

Fig. 6 .

 6 Fig.6. A nice tree decomposition of the graph in Figure2. The leftmost node is the root. The graph G t is illustrated in each node t. The vertices of the bags X t are shown in red.

  Lemma 2.3 ([START_REF] Cygan | Parameterized algorithms[END_REF]). There is a linear-time algorithm that given a graph G = (V , E) and a tree decomposition(T , {X t }) of G of width k with O(k • |V |) nodes, produces a nice tree decomposition (T ′ , {X t ′ }) of Gwith the same width k and O(k • |V |) nodes. This algorithm can also be applied if G is a hypergraph, in which case the output tree decomposition (T ′ , {X t ′ }) will have width k and O(k • |V | + |E|) nodes.

Fig. 7 .

 7 Fig. 7. An optimal 2-partitioning

Fig. 8 .Fig. 9 .

 89 Fig. 8. All possible states over A = {a, b, c} with p = 2

  Number of States. For a fixed p, let C p k denote the number of different possible states over a set of size k, i.e. C p k := |S {1,2, ...,k } |. We write C k instead of C p k when p can be inferred from the context. Appendix A establishes bounds on the value of C k . Note that this value only depends on p and k. Theorem 3.1. Given a Data Packing instance I = (n, 1, p, R) as input, where n is the number of distinct data elements, p is the packing factor, R is the reference sequence with a length of N and the cache has unit size, the Data Packing problem, i.e. finding the minimal number of cache misses, can be solved in linear time, i.e. in time O(N + n • k 2 • C k • p k ), when the underlying access graph G R has treewidth k -1.

  Remark 4.1, we define an ordered hypergraph G by a slight change to the edges of Ĝq * R and then reduce Data Packing to a graph problem over G. The Ordered Hypergraph G. We define the ordered hypergraph G as having the same vertices and edges as the ordered access hypergraph Ĝq * R , except in the following case: • Given an access R[i] to a data element d, let R[j] be the last access before R[i] to the same data element d. If there are at most q * distinct data elements accessed in the range R[j+1] . . . R[i-1],

  when the underlying access hypergraph G q * R has treewidth k -1. Proof. Creating the ordered hypergraph G and the reduction from Data Packing to Minimum-Miss p-partitioning using Lemma 4.2 takes linear time, i.e. O(N • m • p). Note that G is obtained by ordering the vertices of G q *R and then adding duplicated vertices to some of the edges, hence tw(G) = tw(G q * R ). As before, the optimal tree decomposition (T , {X t }) can be computed in linear time by Lemmas 2.2 and 2.3. Since there are N hyperedges in G, the tree T will have O(n • k + N ) nodes, where N of them are introduce edge nodes and O(n • k) of them are of the other types.The times spent at leaves, join nodes, introduce vertex nodes and forget vertex nodes are exactly the same as those established in Theorem 3.1. In an introduce edge node, the algorithm has to compute C k different dp values, each taking time O(k + m • p) due to the call to the missed_edge subprocedure. Hence, processing each introduce edge node takes O(C k • (k + m • p)). Therefore, the total time spent on computing dp values is O

  Theorem 4.2 (Hardness of Data Packing in Constant Treewidth). Given a Data Packing instance I = (n, m, p, R), for any cache size m ≥ 2 and any packing factor p ≥ 3, Data Packing is NP-hard even if the underlying access hypergraph G q * -1 R has constant treewidth.

Finding

  Fig. 15. Treewidth of the hypergraph G q *

  1)! = O e p-k • k k +0.5 , C 1 = p. We prove that C k ≤ (p + k -1) • C k -1and the desired inequality follows by a simple induction.

.=

  Combining the two and ignoring the constants, we get the desired result:O (0.792 • p • k) k .Proof. Let B k be the k-th Bell number, i.e. the number of different partitions of {1, 2, . . . , k}. Given a partition φ, we can form the enlargement function sz in at most p k ways, i.e. there are at most k partitions and we have at most p choices for the sz value of each partition. Hence,C k ≤ p k • B k . Finally, in[START_REF] Berend | Improved bounds on Bell numbers and on moments of sums of random variables[END_REF], it was established that B k ≤ 0We have the following upperbounds on the runtime of Algorithm 1:O N + n • k k +2.5 • p k • e p-k • p n • k k+2 • p 2k • (0.792) k .

  30 for i ← 0 to p -1 do 31 φ ′ = φ ∪ {{v}}; 32 sz ′ = sz ∪ {({v}, i)}; 33 dp[t, s] = min{dp[t, s], dp[t 1 , (φ ′ , sz ′ )]}; 34 forall Y ∈ φ do 35 if |Y | < p ∧ sz(Y ) ≥ 1 then 36 φ ′ = φ ∪ {Y ∪ {v}} \ {Y }; 37 sz ′ = sz ∪ {(Y ∪ {v}, sz(Y ) -1)} \ {(Y , sz(Y )};

  30 for i ← 0 to p -1 do 31 φ ′ = φ ∪ {{v}}; 32 sz ′ = sz ∪ {({v}, i)}; 33 dp[t, s] = min{dp[t, s], dp[t 1 , (φ ′ , sz ′ )]}; 34 forall Y ∈ φ do 35 if |Y | < p ∧ sz(Y ) ≥ 1 then 36 φ ′ = φ ∪ {Y ∪ {v}} \ {Y }; 37 sz ′ = sz ∪ {(Y ∪ {v}, sz(Y ) -1)} \ {(Y , sz(Y )}; 38 dp[t, s] = min{dp[t, s], dp[t 1 , (φ ′ , sz ′ )]};

  t is a Join node with children t 1 and t

2 : dp[t, s] = min sz 1 +sz 2 ≡sz dp[t 1 , (φ, sz 1 )] + dp[t 2 , (φ, sz 2 )];

  Therefore, by setting dp[t, s] = dp[t, (φ, sz)] = min sz 1 +sz 2 ≡sz dp[t 1 , (φ, sz 1 )] + dp[t 2 , (φ, sz 2 )], we satisfy the invariant. Fig.10. In a join node t, G t 1 and G t 2 do not share any edges and their shared vertices are in X t . Computations at Introduce Vertex Nodes. The node t is an introduce vertex node. So, it has a single child t 1 and X t = X t 1 ∪ {v} for some v X t 1 . We know that the vertex v cannot possibly appear in G t 1 because every vertex appears in a connected subtree of T and v X t 1 . the minimum among the values of dp variables of all states s ′ over X t 1 that are compatible with s. More precisely, we let dp[t, s] = min s ′ ∈S X t 1 ∧s ′ ⇆s dp[t 1 , s ′ ]. Fig. 13. When a vertex v is forgotten by t, we have

	t
	t t 1
	t 1	t 2

(1.3) Hence, G t is obtained by adding v as an isolated vertex to G t 1 . Again, we want to compute dp[t, s] and should hence only consider the p-partitionings that realize s. Given that X t 1 ⊂ X t , s imposes a unique compatible state on X t 1 . Moreover, G t has no new edges in comparison with G t 1 , so the total weight of cross edges should only be computed in G t 1 . Hence, we let

dp[t, s] = dp[t, (φ, sz)] = dp[t 1 , (φ |X t 1 , sz |X t 1 )].

Intuitively, this is equivalent to removing v from its partition and then computing the dp in t 1 . t t 1 Fig. 11. In an introduce vertex node t, the newly introduced vertex is isolated and there are no new edges. (1.4) Computations at Introduce Edge Nodes. The node t has a single child t 1 and X t = X t 1 . Moreover, the only difference between G t and G t 1 is in a single edge e. When computing dp[t, s], the state s forces itself on X t 1 = X t . Hence we should let dp[t, s] = dp[t 1 , s] +w(e, s), where w(e, s) is the contribution of the edge e to the total weight of cross edges in s. It is zero if the two sides of e are put in the same partition set by s and is equal to w(e) otherwise. t t 1

Fig.

12

. A new edge is introduced in the node t. The states are only dependent on vertices and hence are the same over X t and X t 1 . However, we have to account for the weight of the new edge.

(1.5) Computations at Forget Vertex Nodes. In this case the node t has a single child t 1 and X t = X t 1 \ {v} for some v ∈ X t 1 . However, G t = G t 1 . Hence, when computing dp[t, s], it is sufficient to take

  • Join Nodes. At a join node t, there are at most C k states and for each state s = (φ, sz) we have to look into the states corresponding to every possible size enlargement function sz 1 ≤ sz. As in the proof of Lemma A.2, there are at most p k such functions. Creating each corresponding state takes O(k). Hence, we spend O(k • C k • p k ) at each join node. • Introduce Vertex Nodes. At a node t, there are C k states and we spend O(k) computing the unique corresponding state over X t 1 . Thus, each introduce vertex node takes O(k • C k ). • Introduce Edge Nodes. This case is similar to the previous one and takes O(k • C k ). • Forget Vertex Nodes. At a node t, there are C k states and for each of them we have to look into all its compatible states over X t 1 . Note that such compatible states can be obtained either by putting the vertex v in its own partition set, which can have any size between 1 and p, or by adding it to the partition set of another vertex in X t . Hence, there are at most p + k such states and the total processing time of a forget vertex node is O(k • (p + k) • C k ). Note that the runtime for join nodes dominates the rest. Given that there are O(n • k) nodes in total, the whole computation takes O

  2 initialize dp[, ]; 3 r ← T .root; 4 compute_dp(r ); 5 return min s ∈S Xr dp[r , s]; 6 function compute_dp (t); Input : A node t of the tree-decomposition T Result : Fills in dp[t, s] for all s ∈ S t 7 forall t ′ ∈ t .children do 8 compute_dp(t ′ ); 9 if t is a leaf then 10 dp[t, s ∅ ] ← 0; 11 else if t is a join node then = (φ, sz) ∈ S X t do 15 dp[t, s] ← min sz 1 +sz 2 ≡sz dp[t 1 , (φ, sz 1 )] + dp[t 2 , (φ, sz 2 )]; 16 else if t is an introduce vertex node then = (φ, sz) ∈ S X t do 19 dp[t, s] ← dp[t 1 , (φ |X t 1 , sz |X t 1 )]; 20 else if t is an introduce edge node, introducing e = (u, v) then = (φ, sz) ∈ S X t do 23 dp[t, s] ← dp[t 1 , s]; 24 if [u] φ [v] φ then 25 dp[t, s] ← dp[t, s] + w(e) 26 else if t is a forget vertex node, forgetting v then 27 t1 ← t .children[1]; 28 forall s = (φ, sz) ∈ S X t do

	17	t1 ← t .children[1];
	21	t1 ← t .children[1];

12 t1 ← t .children[1]; 13 t2 ← t .children[2]; 14 forall s 18 forall s 22 forall s 29 dp[t, s] ← ∞;

  = min{dp[t, s], dp[t 1 , (φ ′ , sz ′ )]}; compute_dp(t ′ ); 9 if t is a leaf then 10 dp[t, s ∅ ] ← 0; 11 else if t is a join node then = (φ, sz) ∈ S X t do 15 dp[t, s] ← min sz 1 +sz 2 ≡sz dp[t 1 , (φ, sz 1 )] + dp[t 2 , (φ,sz 2 )]; 16 else if t is an introduce vertex node then = (φ, sz) ∈ S X t do 19 dp[t, s] ← dp[t 1 , (φ |X t 1 , sz |X t 1 )]; 20 else if t is an introduce edge node, introducing e = (u, v) then = (φ, sz) ∈ S X t do 23 dp[t, s] ← dp[t 1 , s]; ← dp[t, s] + 1 26 else if t is a forget vertex node, forgetting v then 27 t1 ← t .children[1]; 28 forall s = (φ, sz) ∈ S X t do

	17	t1 ← t .children[1];
	21	t1 ← t .children[1];
	24	if missed_edge(e, φ) then
	25	dp[t, s]

38 dp[t, s] 12 t1 ← t .children[1]; 13 t2 ← t .children[2]; 14 forall s 18 forall s 22 forall s 29 dp[t, s] ← ∞;

* This necessarily means that there is a limit on the size of data items and a large item should be broken into smaller parts, each of which is considered a distinct data item.Proceedings of the ACM on Programming Languages, Vol. 1, No. POPL, Article 1. Publication date: January 2019.

Proceedings of the ACM on Programming Languages, Vol. 1, No. POPL, Article 1. Publication date: January 2019.

ACKNOWLEDGMENTS

We are very thankful to the reviewers for their insightful comments. The research was partially supported by Vienna Science and Technology Fund (WWTF) Project ICT15-003, Austrian Science Fund (FWF) NFN Grant No S11407-N23 (RiSE/SHiNE), ERC Starting Grant (279307: Graph Games), and the IBM PhD Fellowship program.

with constant width mp -1.

Given a positive integer m and an instance I as above, we introduce (m + 1)p new data elements d 1 , d 2 , . . . , d (m+1)p . We then define three sequences X , Y and Z as follows: and construct the reference sequence R ′ as:

, X , Z , X , Z , . . . , X , Z b times , i.e. R ′ is obtained by adding X before every element of R and then appending the result with a copies of X , Y and b copies of X , Z . The instance I is then reduced to

Our goal is to set the right values for a and b in a way that forces any optimal data packing scheme σ to put X in exactly m -1 blocks. We set a := N (m -1)p + N + 2m + 1 and b := N (m -1)p + N + amp + m + 1. Using these parameters, every optimal data packing scheme σ has to put X ∪ Z in exactly m blocks. This is because using more than m blocks for them leads to at least b misses in the last part of the sequence R ′ , while putting them in exactly m blocks can cause a maximum of N (m -1)p + N + amp + m = b -1 misses overall, i.e. even if every access up until the end of the last Y leads to a miss. Given that σ puts X ∪ Z in exactly m blocks, we also infer that σ causes at most m misses over the b repetitions of X , Z .

We now prove that σ has to put X ∪ Y in exactly m blocks. The reasoning is similar. If σ puts X ∪ Y in more than m blocks, it causes at least a cache misses, but if it puts them in exactly m blocks the number of cache misses is at most N (m -1)p + N + 2m = a -1, i.e. even if every access up until R[N ] is missed and σ misses m times over the repetitions of X , Z . Given that X ∪ Z and X ∪ Y are both put into m blocks, it follows that σ puts X in exactly m -1 blocks.

We claim that the optimal number of cache misses in I ′ is m + 1 plus the optimal number of cache misses in I . To see this, we track the behavior of σ over the access sequence R ′ . First, the m -1 blocks of X are loaded into the cache causing m -1 cache misses. These remain in the cache forever because of the way X is repeated in R ′ . Therefore, σ has filled m -1 spots of the cache with X and has only 1 spot for handling the R[i]'s. This leads to exactly as many cache misses as in the optimal solution to I . Finally, σ causes two more cache misses, one on the first access to Y and the other one on the first access to Z . Therefore, the optimal number of cache misses in I ′ is equal to the optimal number of cache misses in I plus m + 1. The reduction is now complete.

It remains to show that G

has constant treewidth. Figure 14 shows a tree decomposition of this graph with width mp -1. Therefore, tw(G

□

We now turn to the hardness of approximation. We provide a reduction that follows the same intuition as in the previous theorem. Input : An ordered hyperedge e =< v 1 , . . . , v q > and a p-partitioning σ Output : Whether e is missed in σ

9 return true;

C DETAILS OF EXPERIMENTAL RESULTS

C.1 Benchmark Programs

We used the following programs for generating the access sequences for our experiments:

• Linear Algebra:

(1) Various types of Multiplications (between scalars, vectors and matrices)

(2) Gram-Schmidt Orthonormalization process • Sorting:

(1) Bubble Sort Figure 17 provided a comparison between our algorithms and heuristic-based algorithms. In each case, the percentage of cache misses wrt the optimal number of cache misses was reported. Here, we provide detailed tables that contain the concrete number of cache misses for each category, and also the number of benchmarks (#) and the total length of the reference sequences ( N ) in the category.

Category