Ali Ahmadi

Majid Daliri

Kafshdar Amir

Andreas Goharshady

Pavlogiannis

Efficient Approximations for Cache-conscious Data Placement

published or not. The documents may come

Efficient Approximations for Cache-conscious Data Placement ALI AHMADI * , Sharif University of Technology, Iran MAJID DALIRI, University of Tehran, Iran AMIR KAFSHDAR GOHARSHADY † , The Hong Kong University of Science and Technology, China

ANDREAS PAVLOGIANNIS, Aarhus University, Denmark

There is a huge and growing gap between the speed of accesses to data stored in main memory vs cache. Thus, cache misses account for a significant portion of runtime overhead in virtually every program and minimizing them has been an active research topic for decades. The primary and most classical formal model for this problem is that of Cache-conscious Data Placement (CDP): given a commutative cache with constant capacity 𝑘 and a sequence Σ of accesses to data elements, the goal is to map each data element to a cache line such that the total number of cache misses over Σ is minimized. Note that we are considering an offline single-threaded setting in which Σ is known a priori. CDP has been widely studied since the 1990s. In POPL 2002, Petrank and Rawitz proved a notoriously strong hardness result: They showed that for every 𝑘 ≥ 3, CDP is not only NP-hard but also hard-to-approximate within any non-trivial factor unless P = NP. As such, all subsequent works gave up on theoretical improvements and instead focused on heuristic algorithms with no theoretical guarantees.

In this work, we present the first-ever positive theoretical result for CDP. The fundamental idea behind our approach is that real-world instances of the problem have specific structural properties that can be exploited to obtain efficient algorithms with strong approximation guarantees. Specifically, the access graphs corresponding to many real-world access sequences are sparse and tree-like. This was already well-known in the community but has only been used to design heuristics without guarantees. In contrast, we provide fixed-parameter tractable algorithms that provably approximate the optimal number of cache misses within any factor 1 + 𝜖, assuming that the access graph of a specific degree 𝑑 𝜖 is sparse, i.e. sparser real-world instances lead to tighter approximations. Our theoretical results are accompanied by an experimental evaluation in which our approach outperforms past heuristics over small caches with a handful of lines. However, the approach cannot currently handle large real-world caches and making it scalable in practice is a direction for future work.

CCS Concepts: • Theory of computation → Parameterized complexity and exact algorithms; • Software and its engineering → Memory management.

Additional Key Words and Phrases: cache management, parameterization, data placement, treewidth, cache misses, approximation [START_REF] Alambardar | Optimal Mining: Maximizing Bitcoin Miners' Revenues[END_REF]

INTRODUCTION

Cache Misses. Most modern memory systems consist of a large but relatively slow main memory and one or more small but much faster cache levels. When a program wants to access a specific data item during its execution, the accessed data must first be present in the cache. Otherwise, it will be copied from the main memory to the cache, possibly causing the eviction of other data from the cache. This copying is called a "cache miss". Given the low speed of main memory, the back-and-forth copying between cache and main memory caused by cache misses is a significant contributor to runtime overheads in virtually all programs.

Hence, minimizing cache misses has been a central problem in various communities, including programming languages [START_REF] Calder | Cache-Conscious Data Placement[END_REF][START_REF] Chatterjee | Efficient parameterized algorithms for data packing[END_REF][START_REF] Ding | Improving Cache Performance in Dynamic Applications through Data and Computation Reorganization at Run Time[END_REF][START_REF] Lavaee | The hardness of data packing[END_REF][START_REF] Petrank | The hardness of cache conscious data placement[END_REF][START_REF] Zhang | A hierarchical model of data locality[END_REF][START_REF] Zhong | Array regrouping and structure splitting using whole-program reference affinity[END_REF], compilers [START_REF] Calder | Cache-Conscious Data Placement[END_REF][START_REF] Mendlson | Compile Time Instruction Cache Optimizations[END_REF][START_REF] Rubin | Virtual Cache Line: A New Technique to Improve Cache Exploitation for Recursive Data Structures[END_REF][START_REF] Thabit | Cache management by the compiler[END_REF] and operating systems [START_REF] Borghorst | CyPhOS -A Component-Based Cache-Aware Multi-core Operating System[END_REF][START_REF] Romer | Dynamic Page Mapping Policies for Cache Conflict Resolution on Standard Hardware[END_REF][START_REF] Vaswani | The Implications of Cache Affinity on Processor Scheduling for Multiprogrammed, Shared Memory Multiprocessors[END_REF] for many decades.

Cache-conscious Data Placement (CDP). In this work, we focus on Cache-conscious Data Placement (CDP). CDP is arguably the most classical formulation for the problem of minimizing cache misses. It was first introduced in ASPLOS 1998 by Calder et al [START_REF] Calder | Cache-Conscious Data Placement[END_REF] and then further formalized by Petrank and Rawitz in POPL 2002 [START_REF] Petrank | The hardness of cache conscious data placement[END_REF]. In this model, the memory system consists of two levels: a large main memory storing a set 𝑂 of 𝑛 distinct objects 𝑜 1 , 𝑜 2 , . . . , 𝑜 𝑛 , and a small cache with 𝑘 lines. Depending on the variant, each cache line can hold 1 or 𝑡 objects. A placement map is a function 𝑓 : 𝑂 → {1, 2, . . . , 𝑘 } that maps each object to a cache line. When a placement map 𝑓 is fixed and an access to an object 𝑜 𝑖 is requested, the system first checks to see whether 𝑜 𝑖 is already present in its corresponding cache line 𝑓 (𝑜 𝑖 ). If so, the access is successful. Otherwise, a cache miss happens and 𝑜 𝑖 must first be copied from the main memory to line 𝑓 (𝑜 𝑖 ) of the cache, potentially evicting another object that was already in this cache line. Only after this copying can the access go through. Given a sequence Σ = ⟨𝜎 1 , 𝜎 2 , . . . , 𝜎 𝑁 ⟩ ∈ 𝑂 𝑁 of accesses, CDP asks for a placement map 𝑓 that minimizes cache misses over Σ.

Hardness of CDP. When considering the CDP problem, it is usually assumed that 𝑘 and 𝑡 are small constants and the complexity is studied with respect to the number of objects, i.e. 𝑛, and the length of the access sequence, i.e. 𝑁 . In [START_REF] Petrank | The hardness of cache conscious data placement[END_REF], Petrank and Rawitz showed that the CDP problem is NP-hard for any cache with more than two lines. They also showed that not only is the problem NP-hard, but it is also hard-to-approximate within any non-trivial factor 𝑂 (𝑁 1-𝜖 ) unless P=NP. This became a notorious and well-known hardness result, causing all further works to focus on heuristics with no worst-case bounds on their approximation ratio. Some examples of this approach are [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] Zhang | A hierarchical model of data locality[END_REF][START_REF] Zhong | Array regrouping and structure splitting using whole-program reference affinity[END_REF]. These heuristics try to identify and exploit affinities between data items to minimize cache misses.

Access Graphs and Their Sparsity. A recurring structure in the cache management literature is that of an access graph [START_REF] Borodin | Competitive Paging with Locality of Reference[END_REF][START_REF] Lavaee | The hardness of data packing[END_REF][START_REF] Thabit | Cache management by the compiler[END_REF]. Simply put, an access graph is an undirected graph which has one vertex corresponding to each object 𝑜 𝑖 ∈ 𝑂 and an edge between two vertices if they appear consecutively in the access sequence Σ. Informally, the access graph models the simplest type of affinity between data items. Several previous works also consider extensions of access graphs to hypergraphs whose edges model affinities between more than two data items [START_REF] Chatterjee | Efficient parameterized algorithms for data packing[END_REF][START_REF] Lavaee | The hardness of data packing[END_REF][START_REF] Thabit | Cache management by the compiler[END_REF]. It is well-known that access graphs of real-world sequences are often sparse, opening the door to heuristics based on graph sparsity. Moreover, the optimal algorithm for data packing, which is another formalism for minimizing cache misses, is also based on the sparsity of access (hyper)graphs [START_REF] Chatterjee | Efficient parameterized algorithms for data packing[END_REF].

Our Focus. In this work, we consider the classical problem of Cache-conscious Data Placement (CDP) from an algorithmic and complexity point-of-view. Note that our setting is single-threaded and offline and we assume that the entire sequence Σ of accesses is given as part of the input. We focus on obtaining efficient algorithms that provably approximate the optimal number of cache misses within a constant multiplicative factor, assuming that the instance has sparse access (hyper)graphs. This assumption was already shown to hold for real-world instances in several previous works, such as [START_REF] Chatterjee | Efficient parameterized algorithms for data packing[END_REF]. We use the treewidth of the access (hyper)graphs as a measure of their sparsity.

Treewidth. Treewidth [START_REF] Hans | Discovering treewidth[END_REF][START_REF] Robertson | Graph minors. III. Planar tree-width[END_REF][START_REF] Robertson | Graph minors. II. Algorithmic aspects of tree-width[END_REF] is a well-known and oft-used graph sparsity parameter. Intuitively, the treewidth of a graph is a measure of its tree-likeness. Only trees and forests have a treewidth of 1 and if a graph's treewidth is 𝑤, then the graph can be decomposed into parts of size 𝑤 + 1 that are connected to each other in a tree-like manner. See Section 2.2 for a more formal definition. The algorithmic importance of treewidth is due to the fact that many NP-hard graph problems are solvable in polynomial time over graphs of bounded treewidth [START_REF] Alambardar | Optimal Mining: Maximizing Bitcoin Miners' Revenues[END_REF][START_REF] Bodlaender | Treewidth: Algorithmic techniques and results[END_REF][START_REF] Hans | Dynamic programming on graphs with bounded treewidth[END_REF][START_REF] Hans | A tourist guide through treewidth[END_REF][START_REF] Goharshady | An efficient algorithm for computing network reliability in small treewidth[END_REF]. Moreover, many families of graphs that appear in real-world contexts are shown to have small treewidth. This includes series-parallel and outer-planar graphs [START_REF] Bodlaender | A Partial k-Arboretum of Graphs with Bounded Treewidth[END_REF]. Control flow graphs of structured programs also have bounded treewidth [START_REF] Burgstaller | On the tree width of Ada programs[END_REF][START_REF] Chatterjee | The treewidth of smart contracts[END_REF][START_REF] Chatterjee | JTDec: A tool for tree decompositions in soot[END_REF][START_REF] Gustedt | The treewidth of Java programs[END_REF][START_REF] Thorup | All Structured Programs have Small Tree-Width and Good Register Allocation[END_REF], leading to faster program analysis and model checking algorithms [2, 15-17, 20-24, 29-31, 36, 38, 43]. Finally, access (hyper)graphs of many classical algorithms and programs are also shown to have small treewidth [START_REF] Chatterjee | Efficient parameterized algorithms for data packing[END_REF]. This is the family that is most relevant to the current work.

Our Contributions. We present the first positive theoretical results for the classical and notoriously-hard problem of Cache-conscious Data Placement (CDP). Our detailed results are as follows:

• Approximation Scheme: For every constant 𝜖 > 0, we provide an efficient linear-time algorithm for CDP that is guaranteed to obtain a (1 + 𝜖)-approximation of the optimal number of cache misses, assuming that the access graph of a specific degree 𝑑 𝜖 has bounded treewidth. In other words, our scheme obtains tighter approximations for sparser instances. • Hardness Result: We provide a stronger hardness result and show that CDP is NP-hard even when restricted to instances in which access hypergraphs of a fixed degree 𝑑 have bounded treewidth.

Intuitively, this suggests that both parameterization (sparsity) and approximation are needed in solving CDP. It is impossible to approximate CDP without a sparsity assumption as shown by [START_REF] Petrank | The hardness of cache conscious data placement[END_REF].

On the other hand, our hardness result shows that it is also impossible to solve the problem exactly (without approximation) even when we assume that access hypergraphs of a fixed degree 𝑑 are sparse.

• Experimental Results: We provide experimental results on the benchmarks of [START_REF] Chatterjee | Efficient parameterized algorithms for data packing[END_REF] and caches with 3-6 lines. On these small caches, our approach beats several well-known heuristics in the literature in terms of the number of cache misses.

Novelty. In summary, we provide the first positive theoretical result for CDP through a combination of approximation and parameterization. We also show a stronger hardness result that suggests both approximation and parameterization are probably necessary. Our algorithms are the first to provide provable bounds on the approximation ratio. To the best of our knowledge, graph sparsity parameters such as treewidth were not previously used in the context of CDP. We are also not aware of any other systems problem that is solved by applying both parameterization and approximation.

Intuition behind the Parameter. At first sight, treewidth of the access graph might come off as a surprising parameter. However, it is quite natural to expect this parameter to be small and this expectation was already confirmed by experiments in [START_REF] Chatterjee | Efficient parameterized algorithms for data packing[END_REF]. The intuitive reason behind this is that most real-world algorithms manipulate linear or tree-based data structures, such as arrays, vectors, linked lists, heaps, binary search trees and tries. Hence, the resulting access sequences consist of accesses to these tree-like structures and other helper variables which often have a short lifetime. So, the access graph inherits much of the sparsity and tree-likeness of the underlying data structures and the additional complexity introduced by temporary variables does not make it significantly denser. Treewidth is the classical parameter for capturing and formalizing such tree-like properties.

Limitations. The primary limitation of our approach is that it is only applicable in the offline setting in which the entire access sequence is known a priori. Note that all previous hardness results were also for the same offline case. Our experimental results demonstrate that our approach leads to fewer misses than previous heuristics in the literature. However, it can currently handle only small caches with a handful of lines. More specifically, we provide algorithms with runtimes of either 𝑂 (𝑁 • 𝑘 𝑤+2 ) or 𝑂 (𝑛 • 𝑘 𝑤+1 • (𝑘 +𝑑 • 𝑤 𝑑 )), in which 𝑘 is the cache size, 𝑑 is the order of the access hypergraph and 𝑤 is the treewidth. Thus, while we overcome the hardness-of-approximation and provide the first polynomial-time algorithms with approximation-ratio guarantees, more improvement is needed to handle larger instances. Our results strongly indicate that solving real-world instances of CDP, within a provably-bounded approximation factor, is likely within reach and not as hard as previously thought. Moreover, they show that while the general case of the problem is NP-hard and hard-to-approximate, this is not the case for the sparse instances that are often encountered in practice. Another limitation is that our problem only models the single-threaded case and no parallelism is allowed in accesses to the cache. Offline vs Online. While it is more desirable to minimize cache misses in an online setting, where the entire access sequence Σ is not known in advance, the problem is often studied in offline mode and Σ is assumed to be part of the input. This applies not only to this work but also all previous theoretical results on both data packing [START_REF] Chatterjee | Efficient parameterized algorithms for data packing[END_REF][START_REF] Lavaee | The hardness of data packing[END_REF] and CDP [START_REF] Petrank | The hardness of cache conscious data placement[END_REF]. It is partly because the offline variants are already too hard, i.e. NP-hard and hard-to-approximate. On the other hand, solving the offline version is also useful in the following two cases (taken from [START_REF] Chatterjee | Efficient parameterized algorithms for data packing[END_REF]):

• Limit studies: To test the performance of a compiler for data placement, various inputs are generated as benchmarks, and the baseline comparison of the performance is performed against the best-known offline algorithm [START_REF] Petrank | The hardness of cache conscious data placement[END_REF]. Hence, an almost-optimal algorithm with guaranteed approximation ratio for the offline case is needed. • 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 approach for online cache management is to consider several representative inputs, run an almost-optimal offline algorithm for profiling, and then synthesize an answer to the online case from the offline solutions [START_REF] Calder | Cache-Conscious Data Placement[END_REF][START_REF] Petrank | The hardness of cache conscious data placement[END_REF]. Specifically, the traditional approach of [START_REF] Calder | Cache-Conscious Data Placement[END_REF] for online CDP is to assign a cost to each pair (𝑜 𝑖 , 𝑜 𝑗 ) of elements which roughly correlates with the number of extra cache misses that will be caused by assigning both 𝑜 𝑖 and 𝑜 𝑗 to the same cache line. This cost is always approximated using various profiling techniques. For example, we can run a program over thousands of random inputs and solve the offline variant of CDP for each run. Then, the cost we assign to (𝑜 𝑖 , 𝑜 𝑗 ) should be inversely correlated with the number of test cases in which 𝑜 𝑖 and 𝑜 𝑗 were put in the same cache line. The online algorithm will then simply work greedily and, upon the first access to an element 𝑜 𝑖 , assign it to a cache line that minimizes its cost. Alternatively, we can devise a supervised machine learning algorithm for the online case in which the outputs of the optimal offline algorithm are used as the training set.

As such, the offline case considered in this work, while not leading to practical algorithms that can be directly used for cache management, is still useful both theoretically and for the applications above.

Paging. Paging is a related well-studied problem, in which objects (or blocks) are not assigned to any specific cache line. This is equivalent to having a cache with a single line that can hold up to 𝑘 objects. The goal is to find an optimal replacement policy that minimizes the total number of cache misses [START_REF] Borodin | Competitive Paging with Locality of Reference[END_REF], i.e. to find the optimal policy for choosing which object should be evacuated each time new data is brought into the cache. Common replacement policies include FIFO, which evicts the object that has been in the cache for the longest, and LRU, which evicts the least-recently used/accessed object [START_REF] Chatterjee | Efficient parameterized algorithms for data packing[END_REF][START_REF] Lavaee | The hardness of data packing[END_REF][START_REF] Zhong | Array regrouping and structure splitting using whole-program reference affinity[END_REF]. In the offline case, where the sequence Σ of accesses is known in advance, the Optimal Replacement Policy (ORP) is to evict the object whose next access is furthest in the future [START_REF] Borodin | Competitive Paging with Locality of Reference[END_REF]. Data Packing. Data packing is another formulation of the problem of minimizing cache misses. In this case, the objects are not assigned to specific cache lines. Instead, they are "packed" into blocks of a fixed size and the cache can hold a fixed number of blocks. The goal is to find a packing that minimizes the total number of cache misses over a given access sequence Σ [START_REF] Thabit | Cache management by the compiler[END_REF]. Similar to CDP, data packing is also NP-hard and hard-to-approximate within any non-trivial factor unless P=NP [START_REF] Lavaee | The hardness of data packing[END_REF]. However, many real-world instances of data packing can be solved in polynomial time using parameterization [START_REF] Chatterjee | Efficient parameterized algorithms for data packing[END_REF].

Comparison with [START_REF] Chatterjee | Efficient parameterized algorithms for data packing[END_REF]. The work [START_REF] Chatterjee | Efficient parameterized algorithms for data packing[END_REF] provides an algorithm for the problem of data packing using a parameterization by the treewidth of the access hypergraphs. The parameter we use in this work is similar, but not exactly the same. Specifically, we consider the treewidth of a sparsified subgraph of the access hypergraphs (Section 3.2). This sparsification is a key part of our theoretical contribution and necessary for obtaining a constant-ratio approximation. Additionally, the two works also differ in the following ways:

• Modeling of the Cache: [START_REF] Chatterjee | Efficient parameterized algorithms for data packing[END_REF] considers the problem of Data Packing (DP), whereas we study Cacheconscious Data Placement (CDP). As mentioned above, DP and CDP model the cache differently. In CDP, each data item is mapped to a specific cache line, whereas in DP, the items do not have a fixed position in the cache but are instead grouped (packed) together to form blocks. • Hardness and Parameterized Complexity: While both CDP and DP are NP-hard and hard-to-approximate, the DP problem of [START_REF] Chatterjee | Efficient parameterized algorithms for data packing[END_REF] becomes fixed-parameter tractable and admits a polynomial-time algorithm when the treewidth is bounded. In contrast, our problem remains NP-hard even when limited to graphs of constant treewidth (Section 4) and can only be approximated. Hence, we are considering a strictly harder problem in terms of parameterized complexity and the techniques of [START_REF] Chatterjee | Efficient parameterized algorithms for data packing[END_REF] are not applicable to our setting.

• Solution Concepts: Both our solution and that of [START_REF] Chatterjee | Efficient parameterized algorithms for data packing[END_REF] reduce cache management problems to variants of graph coloring. In [START_REF] Chatterjee | Efficient parameterized algorithms for data packing[END_REF], the number of vertices of any given color is bounded, whereas in our case the number of colors is at most the cache size 𝑘.

PRELIMINARIES

In this section, we provide a formal definition of the CDP problem (mostly following [START_REF] Petrank | The hardness of cache conscious data placement[END_REF]) as well as the necessary background from parameterized complexity.

Cache-conscious Data Placement

Memory System. We consider a memory system consisting of a large main memory and a small cache with 𝑘 lines. We also fix a set 𝑂 = {𝑜 1 , 𝑜 2 , . . . , 𝑜 𝑛 } of objects (data items). We do not make any assumptions about the locations of objects in the main memory or its size. Placement Map. A placement map is a function 𝑓 : 𝑂 → {1, 2, . . . , 𝑘 } that maps each object to a cache line.

Direct Mapping vs 𝑡-way Mapping. In direct mapping, each cache line can hold at most one data item at a time. In 𝑡-way mapping, each cache line can hold up to 𝑡 objects. Our main focus is on the direct mapping case, but our approaches extend to 𝑡-way mapping as well.

Accesses and Cache Misses. Given a fixed placement map 𝑓 , when an access to an object 𝑜 𝑖 is requested, 𝑜 𝑖 must first be present in cache line 𝑓 (𝑜 𝑖 ). If this is not the case, then a cache miss occurs and 𝑜 𝑖 is copied from the main memory to cache line 𝑓 (𝑜 𝑖 ). If this cache line is already full, another data item will be evicted from it. Note that if each cache line can hold more than one object, then we should also fix a replacement policy for each line. In this work, we assume that the replacement policy is LRU, i.e. the least recently used element is always evicted. This is because LRU is the most commonly-used policy in practice [START_REF] Zhong | Array regrouping and structure splitting using whole-program reference affinity[END_REF]. Our algorithms are also extensible to FIFO and ORP with minimal changes1 . Access Seqence. An access sequence is simply a sequence Σ = ⟨𝜎 1 , 𝜎 2 , . . . , 𝜎 𝑁 ⟩ ∈ 𝑂 𝑁 of objects. Intuitively, Σ represents the order in which a program accesses the data items. We denote by Misses 𝑡 𝑘 (𝑓 , Σ) the number of cache misses that occur in a 𝑡-way cache with 𝑘 lines if the placement map is 𝑓 and the accesses are made according to Σ. We assume the cache is empty at the beginning and drop 𝑘 when it is clear from the context. We also drop 𝑡 = 1 in direct mapping.

Cache-conscious Data Placement (CDP). Given a set 𝑂 = {𝑜 1 , . . . , 𝑜 𝑛 } of objects, an access sequence Σ ∈ 𝑂 𝑁 , and cache parameters 𝑡 and 𝑘 as input, the Cache-conscious Data Placement problem asks for an optimal placement map 𝑓 * that minimizes the number of cache misses. More formally, it asks for a placement map 𝑓 * , such that for any other placement map 𝑓 , we have Misses 𝑡 𝑘 (𝑓 * , Σ) ≤ Misses 𝑡 𝑘 (𝑓 , Σ). Approximations. For an 𝜖 > 0, we say that an algorithm is a (1 + 𝜖)-approximation of CDP if given the same inputs, it always produces a placement map 𝑓 such that Misses 𝑡 𝑘 (𝑓 , Σ)

≤ (1 + 𝜖) • Misses 𝑡 𝑘 (𝑓 * , Σ).
Instances. An instance of the CDP problem is a tuple 𝐼 = (𝑛, 𝑂, 𝑁 , Σ, 𝑡, 𝑘) specifying all parts of the input.

Parameterized Complexity, Tree Decompositions and Treewidth

Parameterized Complexity. The central idea in parameterized complexity is to analyze the runtime of an algorithm not only based on its input size 𝑛, but also based on another parameter 𝑝 [START_REF] Downey | Parameterized complexity[END_REF]. The parameter itself can be explicit, i.e. part of the input, or implicit, e.g. a structural property.

Fixed-parameter Tractability (FPT).

A problem is called Fixed-parameter Tractable (FPT) wrt a parameter 𝑝, if there exists an algorithm that solves the problem in time 𝑂 (𝑛 𝑐 • 𝑔(𝑝)), where 𝑛 is the input size, 𝑐 is a constant that does not depend on either 𝑛 or 𝑝 and 𝑔 is an arbitrary computable function [START_REF] Cygan | Parameterized algorithms[END_REF][START_REF] Downey | Parameterized complexity[END_REF]. Intuitively, when a problem is FPT, the instances in which the parameter 𝑝 is small are easy to solve and can be handled in polynomial time.

When dealing with a hard problem, such as CDP, the main challenge is to come up with a suitable parameter 𝑝, such that (i) all or most real-world instances have a small 𝑝, and (ii) the problem becomes FPT wrt 𝑝. Finding such a parameter would effectively lead to efficient solutions for the real-world instances of the problem. We now define the parameter that will be used in this work, i.e. treewidth.

Graphs and Hypergraphs. A directed graph is a pair 𝐺 = (𝑉 , 𝐸) where 𝑉 is a finite set of vertices and 𝐸 ⊆ 𝑉 × 𝑉 is a finite set of edges. Each edge 𝑒 ∈ 𝐸 is an ordered pair of vertices. An undirected graph is defined similarly, except that each edge 𝑒 is a subset {𝑢, 𝑣 } ⊆ 𝑉 . An ordered hypergraph is a pair 𝐺 = (𝑉 , 𝐸) where 𝐸 ⊆ 𝑉 + , i.e. each hyperedge 𝑒 ∈ 𝐸 is an ordered tuple of vertices in 𝑉 . Similarly, in an unordered hypergraph, each edge 𝑒 is simply a subset of vertices. The base (hyper)graph of a directed graph/ordered hypergraph is obtained by ignoring the order of vertices in each edge.

𝑜 1 𝑜 2 𝑜 3 𝑜 4 𝑜 5 𝑜 6 𝑜 7 {𝑜 1 , 𝑜 3 , 𝑜 4 } 𝑏 1 {𝑜 1 , 𝑜 2 } 𝑏 2 {𝑜 3 , 𝑜 4 , 𝑜 6 } 𝑏 3 {𝑜 4 , 𝑜 5 , 𝑜 6 } 𝑏 4 {𝑜 4 , 𝑜 6 , 𝑜 7 } 𝑏 5
Tree Decompositions [START_REF] Cygan | Parameterized algorithms[END_REF]. Consider an undirected / unordered (hyper)graph 𝐺 = (𝑉 , 𝐸). A tree decomposition of 𝐺 is a rooted tree 𝑇 = (𝐵, 𝐸 𝑇 , 𝑟 ) where:

(1) 𝐵 is the set of nodes in the tree and 𝐸 𝑇 is the set of edges. We call each node in 𝐵 a bag and 𝑟 ∈ 𝐵 is the root bag.

(2) Each bag 𝑏 ∈ 𝐵 has an associated subset 𝑉 𝑏 ⊆ 𝑉 of vertices. We reserve the word vertex for vertices of 𝐺.

(3) Each vertex appears in at least one bag, i.e. 𝑏 ∈𝐵 𝑉 𝑏 = 𝑉 .

(4) Each (hyper)edge appears in at least one bag. Formally, for every 𝑒 ∈ 𝐸, there exists a bag 𝑏 ∈ 𝐵, such that 𝑒 ⊆ 𝑉 𝑏 . In other words, 𝑏 contains all endpoints of 𝑒.

(5) Each vertex appears in a connected subtree of 𝑇 . Equivalently, if a bag 𝑏 3 ∈ 𝐵 is on the unique path between the bags 𝑏 1 and 𝑏 2 in 𝑇 , then 𝑉 𝑏 3 ⊇ 𝑉 𝑏 1 ∩ 𝑉 𝑏 2 , i.e. if 𝑣 ∈ 𝑉 appears in the two bags 𝑏 1 and 𝑏 2 , then it must also appear on any bag 𝑏 3 that is on the unique path between them.

Note that tree decompositions do not distinguish between ordered/directed and unordered/undirected edges, i.e. a tree decomposition of an ordered/directed (hyper)graph is simply a tree decomposition of its base graph.

Example 1. Figure 1 shows a graph 𝐺 and one of its tree decompositions. Intuitively, in a tree decomposition the graph is broken into several small pieces (bags) that are connected to each other in a tree-like manner.

Treewidth [START_REF] Cygan | Parameterized algorithms[END_REF][START_REF] Robertson | Graph minors. III. Planar tree-width[END_REF]. The width of a tree composition is defined as the size of its largest bag minus 1, i.e. 𝑤 (𝑇 ) := max 𝑏 ∈𝐵 |𝑉 𝑏 | -1. The treewidth of a (hyper)graph 𝐺 is the smallest width among all of its tree decompositions.

Cut Property [START_REF] Bodlaender | Treewidth: Algorithmic techniques and results[END_REF][START_REF] Cygan | Parameterized algorithms[END_REF]. Consider a (hyper)graph 𝐺 and a tree decomposition 𝑇 of 𝐺 and suppose that the vertices 𝑣 1 , 𝑣 2 ∈ 𝑉 appear in bags 𝑏 1 , 𝑏 2 ∈ 𝐵 respectively. Then every path from 𝑣 1 to 𝑣 2 in 𝐺 has to pass through every bag 𝑏 3 that is on the path from 𝑏 1 to 𝑏 2 in 𝑇 . This is called the cut property of tree decompositions.

Example 2. The tree decomposition in Figure 1 has a width of 2 and is an optimal decomposition. So, the treewidth of the graph 𝐺 is also 2. Consider vertices 𝑜 1 ∈ 𝑉 𝑏 2 and 𝑜 7 ∈ 𝑉 𝑏 5 . Since 𝑏 1 and 𝑏 3 are on the unique path from 𝑏 2 to 𝑏 5 in 𝑇 , then any path that connects 𝑜 7 to 𝑜 1 in 𝐺 has to intersect both of these bags. As an example, consider the path ⟨𝑜 7 , 𝑜 6 , 𝑜 5 , 𝑜 4 , 𝑜 1 ⟩. It intersects 𝑏 3 in both 𝑜 4 and 𝑜 6 . Similarly, it intersects 𝑏 1 in both 𝑜 1 and 𝑜 4 .

Dynamic Programming. The cut property enables one to perform dynamic programming on low-treewidth graphs in a similar manner to trees. Intuitively, in dynamic programming approaches, each bag in a tree decomposition serves the same purpose as a vertex in a tree whose removal breaks the graph/tree down into several completely independent connected components. This can potentially lead to much faster algorithms, especially when the bags, and hence the treewidth, are small. See [START_REF] Bodlaender | Treewidth: Algorithmic techniques and results[END_REF][START_REF] Cygan | Parameterized algorithms[END_REF] for some examples and a more detailed treatment.

Nice Tree Decompositions [START_REF] Cygan | Parameterized algorithms[END_REF]. We say that a tree decomposition 𝑇 = (𝐵, 𝐸 𝑇 ) is nice if (i) the root bag and every leaf bag ℓ are empty, i.e. 𝑉 𝑟 = 𝑉 ℓ = ∅, (ii) every bag has at most two children, (iii) if a bag 𝑏 has a single child 𝑐, then 𝑏 and 𝑐 differ in exactly one vertex, i.e. |𝑉 𝑏 Δ 𝑉 𝑐 | = 1, and (iv) if a bag 𝑏 has two children

𝑐 1 and 𝑐 2 , then 𝑉 𝑏 = 𝑉 𝑐 1 = 𝑉 𝑐 2 .
Every tree decomposition can be easily converted to a nice decomposition of the same width in linear time [START_REF] Cygan | Parameterized algorithms[END_REF]. Nice decompositions help us in designing dynamic programming procedures in Section 3.3.

Computing Optimal Tree Decompositions. Given a graph 𝐺, computing its treewidth 𝑤 and an optimal tree decomposition are FPT problems wrt 𝑤. Specifically, [START_REF] Bodlaender | A linear-time algorithm for finding tree-decompositions of small treewidth[END_REF] provides a linear-time algorithm. Hence, we always assume that an optimal tree decomposition is given as part of the input.

AN EFFICIENT PARAMETERIZED APPROXIMATION SCHEME FOR CDP

In this section, we first define the notions of access graphs and their extensions. Then, we prove a sparsification lemma which reduces the approximation of CDP to a coloring problem over a "sparsified" subgraph of the access graphs. Finally, we provide a tree-decomposition-based dynamic programming algorithm that solves the coloring problem in linear time parameterized by the decomposition's width. Throughout this section, we assume that an input instance 𝐼 = (𝑛, 𝑂, 𝑁 , Σ, 𝑡, 𝑘) is fixed.

Access Graphs and Access Hypergraphs

Access Graph. The access graph of a CDP instance 𝐼 = (𝑛, 𝑂, 𝑁 , Σ, 𝑡, 𝑘) is a directed graph 𝐺 = (𝑂, 𝐸) in which every vertex is a data item and there is an edge between 𝑜 𝑖 and 𝑜 𝑗 if and only if 𝑜 𝑖 appears directly before 𝑜 𝑗 somewhere in the access sequence Σ. We do not add self-loops in 𝐺.

𝑜 1 𝑜 2 𝑜 3 𝑜 4 𝑜 5 Fig. 2. Access graph of the sequence Σ = ⟨𝑜 1 , 𝑜 2 , 𝑜 1 , 𝑜 4 , 𝑜 5 , 𝑜 3 , 𝑜 3 , 𝑜 1 , 𝑜 2 ⟩.
Example 3. Consider the access sequence

Σ = ⟨𝑜 1 , 𝑜 2 , 𝑜 1 , 𝑜 4 , 𝑜 5 , 𝑜 3 , 𝑜 3 , 𝑜 1 , 𝑜 2 ⟩.
Figure 2 shows the access graph of this sequence.

Access Hypergraphs. The access hypergraph of order 𝑑 of the instance 𝐼 is an ordered hypergraph 𝐺 𝑑 = (𝑂, 𝐸), in which there is an edge 𝑒 𝑖 corresponding to each access 𝜎 𝑖 in Σ = ⟨𝜎 1 , 𝜎 2 , . . . , 𝜎 𝑛 ⟩. The edge 𝑒 𝑖 is of the form ⟨𝜎 𝑗 , 𝜎 𝑗+1 , . . . , 𝜎 𝑖 ⟩ in which 𝑗 ≤ 𝑖 is the largest index where at least one of the following holds:

(1) ⟨𝜎 𝑗 , 𝜎 𝑗+1 , . . . , 𝜎 𝑖 ⟩ contains two accesses to 𝜎 𝑖 .

(2) ⟨𝜎 𝑗 , 𝜎 𝑗+1 , . . . , 𝜎 𝑖 ⟩ contains accesses to 𝑑 distinct objects.

(3) 𝑗 = 1.

Informally, to form the edge corresponding to 𝜎 𝑖 , we start from 𝜎 𝑖 and move backwards in the access sequence until we either reach another access to 𝜎 𝑖 or see 𝑑 distinct data items or get to the beginning of the sequence.

Example 4. Consider the same access sequence as in Example 3. Let 𝑑 = 3. The access hypergraph of order 3 has the following edges:

𝑒 1 = ⟨𝑜 1 ⟩ 𝑒 2 = ⟨𝑜 1 , 𝑜 2 ⟩ 𝑒 3 = ⟨𝑜 1 , 𝑜 2 , 𝑜 1 ⟩ 𝑒 4 = ⟨𝑜 2 , 𝑜 1 , 𝑜 4 ⟩ 𝑒 5 = ⟨𝑜 1 , 𝑜 4 , 𝑜 5 ⟩ 𝑒 6 = ⟨𝑜 4 , 𝑜 5 , 𝑜 3 ⟩ 𝑒 7 = ⟨𝑜 3 , 𝑜 3 ⟩ 𝑒 8 = ⟨𝑜 5 , 𝑜 3 , 𝑜 3 , 𝑜 1 ⟩ 𝑒 9 = ⟨𝑜 3 , 𝑜 1 , 𝑜 2 ⟩
It is well-known that access (hyper)graphs are often very sparse. In [START_REF] Chatterjee | Efficient parameterized algorithms for data packing[END_REF], the sparsity was formalized and it was shown that the access (hyper)graphs of many real-world algorithms and programs have bounded treewidth 2 . Based on this observation, we will design FPT algorithms using the treewidth of a sparsified subgraph of the access (hyper)graphs as our parameter.

Sparsification and Reduction to Graph Coloring

We now show how an approximation of the number of optimal cache misses in CDP can be obtained by reduction to a graph coloring problem over certain subgraphs of access hypergraphs.

Colorings from the cache and that the current access leads to a cache miss. Hence, we focus on minimizing the number of cache misses in accesses corresponding to 𝐸 2 only and assume all other accesses lead to cache misses. We will later see that discarding 𝐸 1 does not affect the optimal value too much, in the sense that the optimal solution to 𝐸 2 is always within a constant factor to the optimal solution overall. Hence, this leads to an approximation of the optimal number of cache misses within a constant multiplicative factor.

Canonical Hypergraphs. We say that an ordered hypergraph 𝐺 = (𝑉 , 𝐸) is canonical if every edge 𝑒 ∈ 𝐸 is of the form ⟨𝑣 1 , 𝑣 The following lemma establishes a correspondence between missed edges in G𝑑 and cache misses in the CDP instance 𝐼 .

Lemma 1. Let 𝑓 be a coloring of vertices in G𝑑 = (𝑂, 𝐸 2 ) or equivalently a placement map for 𝐼 = (𝑛, 𝑂, 𝑁 , Σ, 1, 𝑘). An edge 𝑒 𝑖 ∈ 𝐸 2 is missed in the coloring 𝑓 iff a cache miss occurs at its corresponding access 𝜎 𝑖 with placement map 𝑓 .

Proof. Recall that 𝑒 𝑖 is of the form ⟨𝜎 𝑗 , 𝜎 𝑗+1 , . . . , 𝜎 𝑖 ⟩ and since G𝑑 is canonical we have 𝜎 𝑖 = 𝜎 𝑗 . If 𝑒 𝑖 is a missed edge, then there is some index 𝑗 + 1 ≤ 𝑙 ≤ 𝑖 -1 such that 𝑓 (𝜎 𝑙 ) = 𝑓 (𝜎 𝑖 ). Hence, when an access to 𝜎 𝑙 is made, the data item 𝜎 𝑖 is evicted from the cache. As such, 𝜎 𝑖 leads to a cache miss. Conversely, if no such 𝑙 exists, then since 𝜎 𝑗 = 𝜎 𝑖 , this item has been moved to cache at time 𝑗 and remained there until time 𝑖. So, there is no cache miss at 𝜎 𝑖 .

□

Corollary 1. Misses 𝑘 (𝑓 * , Σ) ≤ Misses 𝑘 ( f , Σ) ≤ Cost( f , G𝑑 ) + |𝐸 1 |.
Proof. Recall that 𝑓 * is the optimal placement map that minimizes the number of cache misses and f is the optimal coloring that minimizes the number of missed edges in G𝑑 . Consider f as a placement map.

Based on the lemma above, it causes exactly Cost( f , G𝑑 ) cache misses in accesses corresponding to 𝐸 2 . It can also cause at most |𝐸 1 | cache misses in accesses corresponding to 𝐸 1 . □

This corollary allows us to bound the number of cache misses by solving the optimal coloring problem over the sparsified hypergraph G𝑑 . We will later provide an algorithm for optimal coloring in Section 3.3.

First, we provide a theorem showing that this approach leads to a constant approximation factor.

Theorem 1. We have

Misses 𝑘 (𝑓 * , Σ) ≤ Misses 𝑘 ( f , Σ) ≤ 𝑑 𝑑 -𝑘 • Misses 𝑘 (𝑓 * , Σ).
Proof. The first inequality follows from the definition of 𝑓 * . Let 𝑀 * be the set of indices of accesses that lead to a cache miss if we use the optimal placement map 𝑓 * and M be the set of indices of accesses that lead to a cache miss when the optimal coloring f is used as the placement map. So, |𝑀 * | = Misses 𝑘 (𝑓 * , Σ)

and | M | = Misses 𝑘 ( f , Σ). Moreover, let 𝐿 be the set of indices in Σ that correspond to edges in 𝐸 1 but did not lead to a cache miss in 𝑓 * . Note that we have

|𝑀 * | ≥ Cost( f , G𝑑 ) + |𝐸 1 | -|𝐿|. (1)
| M | ≤ |𝑀 * | + |𝐿|. (2)
So, it suffices to find a bound on |𝐿|. it would cause a cache miss with any placement map and hence 𝑖 could not possibly be in 𝐿. We put an edge from the vertex 𝑖 in 𝐿 to the vertex 𝑗 in 𝑀 iff 𝑖 ′ < 𝑗 < 𝑖. See Figure 3. Note that the edges of B do not exactly correspond to cache misses. The only reason behind this construction is that counting the number of edges in two different ways enables us to bound |𝐿| in terms of |𝑀 * |.

We now bound the number of edges of B in two ways. First, consider a vertex 𝑖 ∈ 𝐿. The degree of 𝑖 is the number of cache misses occurred between times 𝑖 ′ + 1 and 𝑖 -1. Note that 𝐿 only contains indices corresponding to 𝐸 1 . Hence, at least 𝑑 distinct data items were accessed in this period. At the end of time 𝑖 ′ , at most 𝑘 of these items could potentially be in the cache. Thus, there are at least 𝑑 -𝑘 cache misses in this period, i.e. the degree of 𝑖 is at least 𝑑 -𝑘, and the number of edges is at least |𝐿| • (𝑑 -𝑘). Now consider a vertex 𝑗 ∈ 𝑀 * . We prove that the degree of 𝑗 is at most 𝑘. To get a contradiction, suppose that 𝑗 has edges to 𝑖 1 , 𝑖 2 , . . . , 𝑖 𝑘 , 𝑖 𝑘+1 ∈ 𝐿. Given that the range of 𝑓 has 𝑘 different values, by the pigeonhole principle there exist 𝑎, 𝑏 ∈ {𝑖 1 , . . . , 𝑖 𝑘+1 } such that 𝑓 * (𝜎 𝑎 ) = 𝑓 * (𝜎 𝑏 ) = 𝑓 0 . We know that 𝑎 ′ < 𝑗 < 𝑎 and 𝑏 ′ < 𝑗 < 𝑏. Without loss of generality, assume 𝑎 > 𝑏. Since 𝜎 𝑎 and 𝜎 𝑏 are both mapped to 𝑓 0 , 𝜎 𝑎 was brought to cache line 𝑓 0 at time 𝑎 ′ but was then evicted on or before time 𝑏. Hence, we have a cache miss at time 𝑎. For any 𝜖 > 0, by applying the approach above using the sparsified access hypergraph G𝑑 𝜖 of order 𝑑 𝜖 := ⌈𝑘 + 𝑘 𝜖 ⌉, we obtain a (1 + 𝜖)-approximation of the optimal number of cache misses in a direct-mapped cache, i.e. Misses 𝑘 ( f , Σ) ≤ (1 + 𝜖) • Misses 𝑘 (𝑓 * , Σ).

Extension to 𝑡-way Mapping. Extending the approach above to 𝑡-way mapping is quite straightforward and all steps go through naturally. Thus, we only present the differences. See Appendix A for a detailed treatment of the 𝑡-way mapping case.

Optimal 𝑡-way Coloring. In a canonical hypergraph 𝐺 = (𝑉 , 𝐸), we define Cost 𝑡 (𝑓 , 𝐺) of a coloring function 𝑓 as the number of edges 𝑒 = ⟨𝑣 1 , 𝑣 2 , . . . , 𝑣 𝑚 , 𝑣 1 ⟩ that have at least 𝑡 distinct internal vertices with the same color as 𝑣 1 . We call these edges missed edges. The optimal 𝑡-way coloring problem asks for a coloring f with minimal cost. Lemma 1 and Corollary 1 apply to the 𝑡-way case with no changes and Theorem 1 sees only a minor change: Theorem 2. We have

Misses 𝑡 𝑘 (𝑓 * , Σ) ≤ Misses 𝑡 𝑘 ( f , Σ) ≤ 𝑑 𝑑 -𝑡 • 𝑘 • Misses 𝑡 𝑘 (𝑓 * , Σ).
Proof. Every step is the same as in the proof of Theorem 1, except that the total cache size is now 𝑡 • 𝑘.

Hence, the degree of each vertex in 𝐿 is at least 𝑑 -𝑡 • 𝑘 and the degree of each vertex in 𝑀 * is at most 𝑡 • 𝑘. □ Corollary 3. For any positive constant 𝜖 > 0, by applying the approach above using the sparsified access hypergraph G𝑑 𝜖 of order 𝑑 𝜖 := ⌈𝑡 • 𝑘 + 𝑡 •𝑘 𝜖 ⌉, we obtain a (1 + 𝜖)-approximation of the optimal number of cache misses in a 𝑡-way cache, i.e. Misses 𝑡 𝑘 ( f , Σ)

≤ (1 + 𝜖) • Misses 𝑡 𝑘 (𝑓 * , Σ).
Remark. The proofs of the 𝑡-way results above, which are provided in detail in Appendix A, are applicable even when the data items can have varying non-unit integer sizes. Hence, our approach is not limited to unit-sized objects.

Corollaries 2 and 3 show that we can get arbitrarily tight (1 + 𝜖)-approximations of the optimal number of cache misses provided that we can solve the optimal (𝑡-way) coloring problem on the sparsified access hypergraph of the right order and obtain the coloring/placement map f . This is summarized in Algorithm 1.

In Section 3.3, we provide a linear-time FPT algorithm for solving the optimal coloring and 𝑡-way coloring problems parameterized by treewidth. Hence, we can obtain a (1 + 𝜖)-approximation of the number of cache misses whenever the sparsified access hypergraph G𝑑 𝜖 is sparse and has bounded treewidth. It is also noteworthy that Theorems 1 and 2 and hence the (1 + 𝜖) factor are not tight. In practice, our approach may find much tighter approximations.

A Decomposition-based Algorithm for Optimal Coloring

In this section, we consider the problem of (𝑡-way) optimal coloring, as defined in Section 3.2 and provide a linear-time FPT algorithm wrt treewidth for solving it, i.e. our algorithm can solve the problem in linear time if the input graph is sparse and has bounded treewidth.

Input. The input consists of two integers 𝑡 and 𝑘, a canonical hypergraph 𝐺 = (𝑉 , 𝐸) with 𝑛 vertices and 𝑁 edges, each with at most 𝑑 endpoints, and a nice tree decomposition 𝑇 = (𝐵, 𝐸 𝑇 ) of 𝐺 with 𝑂 (𝑛) bags and constant width 𝑤.

Output. The output is an optimal coloring function f : 𝑉 → {1, 2, . . . , 𝑘 } with minimal total cost.

Note that we are mostly focused on direct mapping, i.e. 𝑡 = 1. However, our algorithm can handle any value of 𝑡. Moreover, we can assume that a tree decomposition of linear size is given as part of the input, Algorithm 1 A (1 + 𝜖)-approximation for CDP since, as mentioned in Section 2.2, there are linear-time FPT algorithms for computing an optimal tree decomposition and making it nice. Subtrees and Subgraphs. We say that a vertex 𝑣 appears in a bag 𝑏, if 𝑣 ∈ 𝑉 𝑏 . Similarly, an edge 𝑒 appears in 𝑏 if all of its endpoints appear in 𝑏, i.e. 𝑒 ⊆ 𝑉 𝑏 . We denote the set of all edges appearing in 𝑏 by 𝐸 𝑏 .

For a bag 𝑏 ∈ 𝐵, we define its corresponding subtree 𝑇 ↓ 𝑏 = (𝐵 ↓ 𝑏 , 𝐸

𝑇 ↓ 𝑏
) as the part of 𝑇 that is rooted at 𝑏, i.e. including 𝑏 and all of its descendants. The subgraph 𝐺 ↓ 𝑏 corresponding to 𝑏 consists of all vertices and edges that appear in at least one bag in 𝑇 ↓ 𝑏 , i.e.

𝐺 ↓ 𝑏 = 𝑏 ′ ∈𝐵 ↓ 𝑏 𝑉 𝑏 ′, 𝑏 ′ ∈𝐵 ↓ 𝑏 𝐸 𝑏 ′ .
Example 5. Consider the graph and decomposition of Figure 1. Figure 4 shows the subtree and subgraph corresponding to the bag 𝑏 3 .

Partial Coloring. Let 𝑏 ∈ 𝐵 be a bag. A partial coloring on 𝑏 is simply a function 𝑓 𝑏 : 𝑉 𝑏 → {1, 2, . . . , 𝑘 } that assigns a color to each vertex in 𝑏. We denote the set of all 𝑘 |𝑉 𝑏 | possible partial colorings on 𝑏 by C 𝑏 .

Our algorithm is a bottom-up dynamic programming on the nice tree decomposition 𝑇 . There are two basic observations: (i) since every bag 𝑏 is small and has size at most 𝑤 + 1, we can do a brute-force check of all partial colorings over 𝑏, and (ii) we can define subproblems on 𝐺 ↓ 𝑏 and its tree decomposition 𝑇 ↓ 𝑏 and use the solutions in these subproblems to solve the initial instances. Dynamic Programming Variables. Based on the two observations above, for every bag 𝑏 ∈ 𝐵 and partial coloring 𝑓 𝑏 ∈ C 𝑏 , the algorithm defines a dynamic programming variable dp[𝑏, 𝑓 𝑏 ] and initializes it to +∞.

Our goal is to compute values for the dp[•, •] in a bottom-up order such that the following invariant holds after we compute dp[𝑏, 𝑓 𝑏 ]:

dp[𝑏, 𝑓 𝑏 ] = Minimal possible cost of a coloring of 𝐺 ↓ 𝑏 ( †) in which 𝑉 𝑏 is colored according to 𝑓 𝑏
In other words, we solve subproblems on 𝐺 ↓ 𝑏 corresponding to each possible partial coloring of 𝑏.

Computing dp Values. Our algorithm processes the bags of 𝑇 in a bottom-up order and performs the following actions based on the type of the bag:

(1) Leaf Bags: Consider a leaf bag ℓ ∈ 𝐵. Given that 𝑇 is nice, we have 𝑉 ℓ = ∅. Hence, C ℓ contains only a single trivial coloring 𝑓 ℓ . Since there are no edges in 𝐺 ↓ ℓ , the total cost would always be 0. Hence, the algorithm sets dp[ℓ, 𝑓 ℓ ] = 0.

(2) Bags with a Single Child: Suppose that 𝑏 ∈ 𝐵 is a bag with a single child 𝑐 ∈ 𝐵. Given that 𝑇 is nice, (3) Bags with Two Children: Consider a bag 𝑏 with two children 𝑐 1 and 𝑐 2 . Since 𝑇 is nice, we have

𝑉 𝑏 = 𝑉 𝑐 1 = 𝑉 𝑐 2 and 𝐺 ↓ 𝑏 = 𝐺 ↓ 𝑐 1 ∪ 𝐺 ↓ 𝑐 2 .
So, when computing dp[𝑏, 𝑓 𝑏 ], we can use the same partial coloring function 𝑓 𝑏 for both 𝑐 1 and 𝑐 2 and then the number of missed edges in 𝐺 ↓ 𝑏 is equal to the number of missed edges in 𝐺 ↓ 𝑐 1 plus the number of missed edges in 𝐺 ↓ 𝑐 2 minus the number of missed edges that were counted in both. If an edge 𝑒 is in both 𝐺 ↓ 𝑐 1 and 𝐺 ↓ 𝑐 2 , then all of its endpoints must appear in both graphs. Using the last property of tree decompositions (see Section 2.2), we conclude that all of its endpoints have appeared in 𝑏 and hence 𝑒 ∈ 𝐸 𝑏 = 𝐸 𝑐 1 = 𝐸 𝑐 2 . Thus, the algorithm sets: Computing the Final Answer. Since 𝑇 is nice, we have 𝑉 𝑟 = ∅. So, there is only one possible partial coloring ⊥∈ C 𝑟 for the root bag 𝑟 . Moreover, we have 𝐺 ↓ 𝑟 = 𝐺 . So, the algorithm outputs dp[𝑟, ⊥] as the minimal number of missed edges. Algorithm 2 shows all steps of our method for obtaining the cost of the optimal coloring. Algorithm 2 Parameterized algorithm for optimal coloring 1: procedure OptimalColoring(𝑉 , 𝐸, 𝑡, 𝑘,𝑇 = (𝐵, 𝐸 𝑇 ))

dp[𝑏, 𝑓 𝑏 ] = dp[𝑐 1 , 𝑓 𝑏 ] + dp[𝑐

2:

for 𝑏 ∈ 𝐵 in bottom-up order do 3:

for 𝑓 𝑏 : 𝑉 𝑏 → {1, 2, . . . , 𝑘 } do 𝑐 ← 𝑏.children [START_REF] Alambardar | Optimal Mining: Maximizing Bitcoin Miners' Revenues[END_REF] 8:

if 𝑉 𝑐 ⊆ 𝑉 𝑏 then for 𝑖 = 1 to 𝑘 do 19:

𝑓 𝑐 ← 𝑓 𝑏 [𝑣 → 𝑖] 20: dp[𝑏, 𝑓 𝑏 ] ← min(dp[𝑏, 𝑓 𝑏 ], dp[𝑐, 𝑓 𝑐 ]) 21: else if |𝑏.children| = 2 then 22: 𝑐 1 , 𝑐 2 ← 𝑏.children 23: dp[𝑏, 𝑓 𝑏 ] ← dp[𝑐 1 , 𝑓 𝑏 ] + dp[𝑐 2 , 𝑓 𝑏 ] 24:
for 𝑒 ∈ 𝐸 𝑏 do Finding the Optimal Coloring. The algorithm above obtains the minimal number of missed edges / minimal cost. As is common in dynamic programming, one can obtain the optimal coloring itself by simply keeping track of the partial colorings that led to the optimal dp[•, •] value at every step of the algorithm. Theorem 3. Given positive integer constants 𝑡 and 𝑘, a canonical hypergraph 𝐺 with 𝑛 vertices whose edges have at most 𝑑 endpoints, and a nice tree decomposition of 𝐺 with 𝑂 (𝑛) bags and width 𝑤, the algorithm above solves the 𝑡-way optimal coloring problem in total runtime 𝑂 (𝑛 • 𝑘 𝑤+1 • (𝑘 + 𝑑 • 𝑤 𝑑 )).

Proof. The correctness of the algorithm was argued in its presentation above. We focus on the runtime bound. There are 𝑂 (𝑛) bags and the algorithm defines at most 𝑘 𝑤+1 different dp[•, •] variables at each bag 𝑏, since there are at most 𝑘 𝑤+1 partial colorings in C 𝑏 . Case (1) spends 𝑂 (1) time per variable and Case (2.ii) takes the minimum of 𝑘 values in 𝑂 (𝑘). In cases (2.i) and ( 3), all edges in the current bag should be checked to see if they are missed. There are at most (𝑤 + 1) 𝑑 such edges and checking each of them takes 𝑂 (𝑑) 4 . □ Remark. The bound above is a theoretical worst-case bound and not tight. Our algorithm is indeed much faster in practice. Moreover, we can improve the runtime to 𝑂 (𝑁 • 𝑘 𝑤+2 ) using a slightly different notion of nice tree decompositions. See Appendix B for details of theoretical improvements and Section 5 for experimental results. Corollary 4. When 𝑘, 𝑤 and 𝑑 are bounded, our algorithm solves the optimal coloring problem in linear time 𝑂 (𝑛).

We are now ready to present our main theorem: Theorem 4. For any 𝜖 > 0, there exists an order 𝑑 𝜖 , such that by applying our tree decompostion-based algorithm to the sparsified access hypergraph G𝑑 𝜖 , we obtain a linear-time (1 +𝜖)-approximation of the optimal number of cache misses, as well as a placement map f such that

Misses 𝑡 𝑘 ( f , Σ) ≤ (1 + 𝜖) • Misses 𝑡 𝑘 (𝑓 * , Σ).
For direct mapping, we have 𝑑 𝜖 = ⌈𝑘 + 𝑘 𝜖 ⌉ and for 𝑡-way mapping,

𝑑 𝜖 = ⌈𝑡 • 𝑘 + 𝑡 •𝑘 𝜖 ⌉.
Proof. Direct result of Corollaries 2, 3 and 4. □

HARDNESS OF CDP IN BOUNDED TREEWIDTH

As proven in [START_REF] Petrank | The hardness of cache conscious data placement[END_REF], it is impossible to approximate CDP within any non-trivial factor unless P=NP. In this section, we show that for every positive integer constant 𝑑, finding an exact solution to the CDP problem remains NP-hard even if the access hypergraph 𝐺 𝑑 of order 𝑑 has constant treewidth. These two complementary hardness results show that both parameterization and approximation are necessary for our efficient solution in Section 3 and the problem remains NP-hard if only one of them is applied.

Theorem 5 (Hardness of CDP with Direct Mapping). For every positive integer constant 𝑑, the CDP problem with direct mapping is NP-hard even when limited to instances where the treewidth of 𝐺 𝑑 is bounded by a constant. Example 6. Before providing a formal proof, let us illustrate the main ideas by an example. Our goal is to find a reduction from general CDP, which is NP-hard, to the special case of CDP in which the treewidth is bounded. Consider the access sequence of Example 3:

Σ = ⟨𝑜 1 , 𝑜 2 , 𝑜 1 , 𝑜 4 , 𝑜 5 , 𝑜 3 , 𝑜 3 , 𝑜 1 , 𝑜 2 ⟩.
Suppose that we have a cache of size 𝑘 = 2 and set 𝑑 = 2 in the theorem above. In other words, we want to reduce our CDP instance 𝐼 = (𝑛, 𝑂, 𝑁 ′ , Σ, 1, 𝑘) = (5, {𝑜 1 , . . . , 𝑜 5 }, 9, Σ, 1, 2) to another CDP instance 𝐼 ′ = (𝑛 ′ , 𝑂 ′ , 𝑁 ′ , Σ ′ , 1, 𝑘 ′ ) such that the access graph of 𝐼 ′ has small treewidth. We first introduce two new data

𝜏 1 𝜏 2 𝑜 1 𝑜 2 𝑜 3 𝑜 4 𝑜 5 𝜏 1 𝜏 2
Fig. 8. Base access graph of the sequence Σ.

{𝜏 1 , 𝜏 2 , 𝑜 1 } {𝜏 1 , 𝜏 2 , 𝑜 2 } {𝜏 1 , 𝜏 2 , 𝑜 3 } {𝜏 1 , 𝜏 2 , 𝑜 4 } {𝜏 1 , 𝜏 2 , 𝑜 5 } {𝜏 1 , 𝜏 2 }
Fig. 9. A tree decomposition of width 2 for the graph of Figure 8.

elements (objects) 𝜏 1 and 𝜏 2 and set 𝑂 ′ = {𝑜 1 , . . . , 𝑜 5 , 𝜏 1 , 𝜏 2 }. Intuitively, we want to take Σ and add ⟨𝜏 1 , 𝜏 2 ⟩ between any two consecutive accesses, so that the treewidth of the access sequence becomes small. This leads to

Σ = ⟨𝜏 1 , 𝜏 2 , 𝑜 1 , 𝜏 1 , 𝜏 2 , 𝑜 2 , 𝜏 1 , 𝜏 2 , 𝑜 1 , 𝜏 1 , 𝜏 2 , 𝑜 4 , 𝜏 1 , 𝜏 2 , 𝑜 5 𝜏 1 , 𝜏 2 , 𝑜 3 , 𝜏 1 , 𝜏 2 , 𝑜 3 , 𝜏 1 , 𝜏 2 , 𝑜 1 , 𝜏 1 , 𝜏 2 , 𝑜 2 , 𝜏 1 , 𝜏 2 ⟩
Note that every access to any original data item 𝑜 𝑖 is now preceded and succeeded by the new elements 𝜏 2 and 𝜏 1 . Ignoring edge directions and repetitions, this leads to an access graph that is almost bipartite, except for the edge between the new elements. See Figure 8. We can easily find a tree decomposition of constant width 2 for this access graph, as shown in Figure 9. We put a bag containing only the new elements as the root and add a child of the form {𝜏 1 , 𝜏 2 , 𝑜 𝑖 } for each 𝑜 𝑖 . It is easy to verify that this is a valid tree decomposition.

To have a reduction, we must be able to obtain the optimal number of cache misses in 𝐼 from the optimal number of cache misses in 𝐼 ′ , but an optimal data placement for Σ might have no resemblance to its counterpart for Σ. So, we first increase our cache size by setting 𝑘 ′ = 4, and then add a gadget that ensures each 𝜏 𝑖 gets its own dedicated cache line. This ensures that exactly 2 = 𝑘 cache lines remain for the 𝑜 𝑖 's and hence we can simulate the original instance. To achieve this property, we simply append many repetitions of ⟨𝜏 1 , 𝜏 2 ⟩ to the end of Σ, and define:

Σ ′ = Σ • ⟨𝜏 1 , 𝜏 2 ⟩ | Σ+1| .
In other words, Σ ′ is obtained by appending | Σ + 1| copies of ⟨𝜏 1 , 𝜏 2 ⟩ to the end of Σ. Note that in 𝐼 ′ , the new items 𝜏 1 and 𝜏 2 should be assigned to different cache lines. Otherwise, we will get 2 • ( Σ + 1) cache misses in the second part of Σ ′ since every access to the new items will be a miss. In contrast, if they are assigned to the same cache line, we can get at most |Σ ′ | cache misses in the first part and none in the second.

Now consider an optimal data placement for 𝐼 ′ and suppose that it assigns 𝜏 1 and some original object 𝑜 𝑖 to the same cache line. This means every access to 𝑜 𝑖 or 𝜏 1 in Σ is a miss. We can modify our data placement and assign 𝑜 𝑖 to any other cache line that is not assigned to 𝜏 1 or 𝜏 2 , and this will not increase the number of cache misses. In the worst case, every cache miss on 𝑜 𝑖 is preserved and every cache miss on 𝜏 1 is replaced by a miss on another element that shares a cache line with 𝑜 𝑖 . Hence, there is an optimal data placement 𝑓 ′ for 𝐼 ′ in which 𝜏 1 and 𝜏 2 have their own dedicated cache lines. This means that the other elements must be put into 𝑘 ′ -2 = 𝑘 lines and hence 𝐼 is simulated by 𝐼 ′ . So, we can just count the number of cache misses on 𝑜 𝑖 's in 𝐼 ′ and this gives us the optimal number of misses in 𝐼 .

Proof of Theorem 5. We provide a polynomial-time reduction from the general case of CDP to lowtreewidth CDP. Since the former is NP-hard [START_REF] Petrank | The hardness of cache conscious data placement[END_REF], then so is the latter. Let 𝐼 = (𝑛, 𝑂, 𝑁 , Σ, 1, 𝑘) be a CDP instance with direct mapping. We create a new CDP instance 𝐼 ′ = (𝑛 ′ , 𝑂 ′ , 𝑁 ′ , Σ ′ , 1, 𝑘 ′ ) where:

• 𝑛 ′ = 𝑛 + 𝑑 and 𝑂 ′ = 𝑂 ∪ {𝜏 1 , 𝜏 2 , . . . , 𝜏 𝑑 }, i.e. we add 𝑑 new objects.

• 𝑁 ′ = 𝑑 2 • 𝑁 + 𝑑 2 + 2 • 𝑑 • 𝑁 + 2
• 𝑑 + 𝑁 and the access sequence Σ ′ is of the following form:

𝑋 𝜎 1 𝑋 𝜎 2 𝑋 . . . 𝑋 𝜎 𝑁 𝑋 𝑋 𝑑 •𝑁 +𝑑+𝑁 +1
where 𝑋 = ⟨𝜏 1 , 𝜏 2 , . . . , 𝜏 𝑑 ⟩. Intuitively, we add 𝑋 at the beginning and end of Σ, as well as in between every two accesses. Finally, we add 𝑑 • 𝑁 + 𝑑 + 𝑁 + 1 more copies of 𝑋 to the end. • 𝑘 ′ = 𝑘 + 𝑑, i.e. we add 𝑑 new cache lines.

Let 𝑓 ′ be an optimal placement function for 𝐼 ′ . Note that for every 𝑖 ≠ 𝑗, we have 𝑓 ′ (𝜏 𝑖 ) ≠ 𝑓 ′ (𝜏 𝑗 ). This is because assigning 𝜏 𝑖 and 𝜏 𝑗 to the same cache line will cause at least 𝑑 • 𝑁 + 𝑑 + 𝑁 + 1 cache misses in the final part of Σ ′ , i.e. in 𝑋 𝑑 •𝑁 +𝑑+𝑁 +1 , whereas any placement that assigns different cache lines to each of the 𝜏 𝑙 's leads to no cache misses in this part. The length of the rest of the sequence is 𝑑 • 𝑁 + 𝑑 + 𝑁 which is a natural upper-bound on the number of possible cache misses. Next, we argue that there is an optimal 𝑓 ′ that does not assign any 𝜏 𝑖 and 𝑜 𝑗 to the same cache line. Suppose that 𝑓 (𝜏 𝑖 ) = 𝑓 (𝑜 𝑗 ). Then every access to 𝑜 𝑗 at any time 𝑎 is a cache miss, since 𝑓 (𝑜 𝑗 ) contains 𝜏 𝑖 . Similarly, the access to 𝜏 𝑖 at time 𝑎 + 𝑖 is also a cache miss. We now change 𝑓 (𝑜 𝑗 ) arbitrarily to some other value 𝑞 that is not shared with any 𝜏 𝑙 . It is easy to verify that this cannot increase the number of cache misses. In the worst case, the misses on 𝑜 𝑗 remain and the misses on 𝜏 𝑖 are replaced by misses on the first other access that is mapped to 𝑞. By repeating this process, we will obtain an optimal 𝑓 ′ that uses 𝑑 of the cache lines for {𝜏 1 , . . . , 𝜏 𝑑 } and the other 𝑘 lines for 𝑂. Hence, 𝑓 * = 𝑓 ′ |𝑂 is an optimal solution for 𝐼 . This completes the reduction. Figure 10 Theorem 6 (Hardness of CDP with 𝑡-way Mapping). For all positive integer constants 𝑑 and 𝑡, the CDP problem with 𝑡-way mapping is NP-hard even when limited to instances where the treewidth of 𝐺 𝑑 is bounded by a constant.

Proof. Section 4.3 of [START_REF] Petrank | The hardness of cache conscious data placement[END_REF] provides a construction that, by introducing new data items and polynomially increasing the instance size, simulates a direct-mapping cache by a 𝑡-way mapping cache. The construction in [START_REF] Petrank | The hardness of cache conscious data placement[END_REF] uses a constant number of extra data elements and does not blow up the treewidth of 𝐺 𝑑 . We can then apply Theorem 5. □

EXPERIMENTAL RESULTS

In this section we report on an implementation and experimental evaluation of our algorithm for CDP.

Implementation. We implemented our approach, i.e. the algorithm of Section 3.3 for direct-mapped caches with the optimizations of Appendix B, in C++ and used the LibTW library [START_REF] Thomas Van Dijk | Computing treewidth with LibTW[END_REF] for computing optimal tree decompositions.

Machine. All results were obtained on an Ubuntu 20.04 machine using a single thread of an Intel Xeon E3-1220 v2 Processor (3.1 GHz, 8M Cache) with 32 GB of RAM.

Benchmarks. We used the benchmarks of [START_REF] Chatterjee | Efficient parameterized algorithms for data packing[END_REF] for obtaining experimental results. These benchmarks contain access sequences Σ that are generated from a wide variety of classical algorithms including in linear algebra, sorting, divide-and-conquer, dynamic programming and string matching. In [START_REF] Chatterjee | Efficient parameterized algorithms for data packing[END_REF], they were introduced as benchmarks for the problem of data packing, which is another formalism of minimizing cache misses. Given that both data packing and CDP have the same input format, i.e. an access sequence of a program, we can simply repurpose the benchmarks of [START_REF] Chatterjee | Efficient parameterized algorithms for data packing[END_REF] for our use-case. Each benchmark corresponds to a classical algorithm, e.g. Gram-Schmidt or Heap Sort, and can generate access sequences of various (arbitrarily long) lengths. See [START_REF] Chatterjee | Efficient parameterized algorithms for data packing[END_REF] and its artifact for a complete list of benchmarks and other details.

Test Cases. Recall that a direct-mapping instance is a tuple 𝐼 = (𝑛, 𝑂, 𝑁 , Σ, 1, 𝑘). Our algorithm also needs an extra parameter 𝑑, i.e. the degree of the access hypergraph. We call the tuple (𝑛, 𝑂, 𝑁 , Σ, 𝑘, 𝑑) a test case.

In our experiments, we set a time limit of 5 minutes per test case for our algorithm and, for each benchmark, each cache size 3 ≤ 𝑘 ≤ 6, and each hypergraph degree 𝑘 < 𝑑 < 15, generated all the test cases that our algorithm could handle in this time limit. This led to a total of 12,085 test cases, corresponding to 1,633 distinct instances. Our longest access sequence in our instances has 12,917 accesses. Note that the cache sizes considered here are much smaller than those in the real world. Our algorithm is hence not suitable for practical cache management but can instead be used for limit studies and profiling as mentioned in Section 1. Similarly, note that we assume the entire sequence Σ of accesses is given as part of the input and are solving the single-threaded offline case of the problem.

Sparsity of Instances. The fact that access graphs and access hypergraphs are sparse is quite well-known.

In [START_REF] Chatterjee | Efficient parameterized algorithms for data packing[END_REF], it was shown that the access hypergraphs of most classical algorithms have bounded treewidth.

However, in contrast to previous methods, our algorithm does not depend on the access hypergraph 𝐺 𝑑 itself, but only on a sparsified subgraph G𝑑 . See Section 3.2. This means that we work with a much sparser graph. In our experiments, the average ratio of the number of edges in G𝑑 to the number of edges in 𝐺 𝑑 was 47.22%. So, our sparsification has significant impact, leading to graphs that have less than half as many edges as the widely-used access hypergraphs. Moreover, they have a treewidth of at most 14. Figure 11 provides a histogram of the treewidths of G𝑑 in our test cases. Baselines. We compare our algorithm against several well-known heuristics in the literature.

• CKJA: This is the algorithm presented in [START_REF] Calder | Cache-Conscious Data Placement[END_REF], when cache-conscious data placement was first defined.

It is a classic and has since been extensively studied. • BB: This algorithm was presented in [START_REF] Beg | A graph theoretic approach to cache-conscious placement of data for direct mapped caches[END_REF] and provides a graph-theoretic approach that aims to totally prevent the so-called "conflict misses" if possible.

• SCE: This approach aims to minimize cache misses using a coloring-based heuristic. It was presented in [START_REF] Sherwood | Reducing cache misses using hardware and software page placement[END_REF].

Experimental Results. Table 1 provides a summary of the number of instances where our approach outperformed the baseline heuristics. Overall, our algorithm beats CKJA in 85% of instances, BB in 84% and SCE in 88%. Figure 12 provides a detailed comparison between our algorithm and the baselines above.

In this figure, each red dot corresponds to one instance. The dot's 𝑥 coordinate is the number of cache misses obtained by our algorithm and its 𝑦 coordinate is the number of cache misses of the other method.

The 𝑥 = 𝑦 line is shown in blue. Hence, a red dot above the line corresponds to an instance in which our algorithm performed better than the other approach, and a red dot below the blue line signifies that the other approach performed better.

Lower-bounds. A major theoretical advantage of our approach is that, for the first time, it provides constant multiplicative approximation ratio guarantees. Specifically, we can use the guaranteed ratio in Theorem 1 to obtain a lower-bound ℓ on the optimal number of cache misses, i.e. we are guaranteed to have at least ℓ cache misses no matter which placement function is used. These lower-bounds are shown in Figure 13. As before, there is a green dot corresponding to each instance. The green dot's 𝑥 coordinate is the number of cache misses obtained by our algorithm, whereas its 𝑦 coordinate is the guaranteed lower-bound ℓ. As expected, all green dots are below the 𝑥 = 𝑦 line.

Discussion. Our experimental results show that our novel approach manages a better utilization of the cache compared to previous heuristics, leading to improved cache performance in the vast majority of the benchmarks. Moreover, the performance gap increases as we go to more demanding benchmarks, indicated by the widening distribution of data points on the right-end side of the charts in Figure 12. Our approach is the first to provide theoretical guarantees of approximation within a constant ratio. Although our running time is generally larger than the heuristics, it is many orders of magnitude faster than a purely exhaustive search, which is the only other known approach so far that offers any non-trivial guarantees of optimality. Performing exhaustive search on our benchmark instances will take more than 10 500 years per instance. This matches the intuition provided by the notorious hardness-of-approximation result in [START_REF] Petrank | The hardness of cache conscious data placement[END_REF]. Our parameterized approach overcomes this hardness of approximation and solves instances that have thousands or even tens of thousands of accesses. This being said, given that our runtime depends exponentially on the cache size, we can only handle small caches and our approach does not scale to real-world cache sizes.

Finally, our lower bounds can be used in limit studies of heuristics, in order to characterize their performance not against another approach, but compared to the best theoretically-possible performance.

CONCLUSION

We studied Cache-conscious Data Placement (CDP), which is a standard and classical problem in memory management. As previous works have provided either formal and strong theoretical hardness results, or heuristics with no guarantees of optimality, this work is the first to present formal positive results. Particularly, we have shown that real-world instances of CDP admit efficient approximations within a constant ratio (1 + 𝜖) based on sparsification and parameterization by treewidth. Notably, our results differ from standard algorithmic approaches in which treewidth suffices to make the problem tractable. As our hardness results show, the problem remains NP-hard even with bounded treewidth, and only approximations are possible.This reveals a stronger hardness for the problem compared to previous results.

Interesting directions of future work include studying the existence of other parameters that allow for an efficient algorithm to solve CDP exactly, designing heuristics on top of our treewidth-based algorithm to improve its performance, and on the more practical side, incorporating our algorithm in data-placement of mainstream compilers.

Proof. The proof is an extension of that of Theorem 1 with the caveat that the total cache size is now 𝑡 • 𝑘, since each of the 𝑘 cache lines can hold up to 𝑡 elements. The first inequality is trivially obtained by the definition of 𝑓 * . We define 𝑀 * to be the set of indices of access that cause a cache miss when using the optimal placement 𝑓 * . Similarly, let M be the indices of misses using f . Let us form the same bipartite graph B as in Theorem 1 in which 𝑀 * serves as the vertices on side and 𝐿 as the other side. Suppose 𝑖 ∈ 𝐿, 𝑗 ∈ 𝑀 * and let 𝑖 ′ be the index of the previous access to 𝜎 𝑖 . We connect vertex 𝑖 in 𝐿 to vertex 𝑗 in 𝑀 if and only if 𝑖 ′ < 𝑗 < 𝑖. This is the same as in Figure 3.

We now double-count the edges of B. Let 𝑖 ∈ 𝐿. The degree of 𝑖 is the number of cache misses occurred between times 𝑖 ′ + 1 and 𝑖 -1. Given that 𝐿 only contains indices in 𝐸 1 , at least 𝑑 distinct data items were accessed in this period. By the end of time 𝑖 ′ , at most 𝑡 • 𝑘 of these items can possibly be in the cache since the overall cache capacity is 𝑡 • 𝑘. Therefore, at least 𝑑 -𝑡 • 𝑘 cache misses occur in this period and the degree of 𝑖 is at least 𝑑 -𝑡 • 𝑘. As such, the number of edges is at least |𝐿| • (𝑑 -𝑡 • 𝑘).

For the other side, let 𝑗 ∈ 𝑀 * . The degree of 𝑗 is at most 𝑡 • 𝑘. We prove this by contradiction. Assume 𝑗 has edges to 𝑖 1 , 𝑖 2 , . . . , 𝑖 𝑡 •𝑘 , 𝑖 𝑡 •𝑘+1 ∈ 𝐿. By the pigeonhole principle there exist 𝑎 1 , 𝑎 2 , . . . , 𝑎 𝑡 +1 ∈ {𝑖 1 , . . . , 𝑖 𝑘+1 } such that 𝑓 * (𝜎 𝑎 1 ) = 𝑓 * (𝜎 𝑎 2 ) = . . . = 𝑓 * (𝜎 𝑎 𝑡 +1 ) = 𝑓 0 . We know that for every index 𝑞, we have 𝑎 ′ 𝑞 < 𝑗 < 𝑎 𝑞 . Without loss of generality, assume 𝑎 ′ 1 < 𝑎 ′ 2 < . . . < 𝑎 ′ 𝑡 +1 . Since 𝜎 𝑎 1 , . . . , 𝜎 𝑎 𝑡 +1 are all mapped to 𝑓 0 , by tracing the elements that enter this cache line, we can see that 𝜎 𝑎 1 enters the cache at time 𝑎 ′ 1 but is then evicted before time 𝑎 1 as each cache line can hold at most 𝑡 items at a time. Hence, we have a cache miss at time 𝑎 1 .

This contradicts the definition of 𝐿. Therefore, the total number of edges is at most |𝑀 * | • 𝑡 • 𝑘. For any positive constant 𝜖 > 0, by applying the approach above using the sparsified access hypergraph G𝑑 𝜖 of order 𝑑 𝜖 := ⌈𝑡 • 𝑘 + 𝑡 •𝑘 𝜖 ⌉, we obtain a (1 + 𝜖)-approximation of the optimal number of cache misses in a 𝑡-way cache, i.e. Misses 𝑡 𝑘 ( f , Σ) ≤ (1 + 𝜖) • Misses 𝑡 𝑘 (𝑓 * , Σ).

Extension to Objects with Varying Sizes. Consider an extension of the CDP problem in which every data item 𝑜 𝑖 has an integer size 1 ≤ 𝑠 𝑖 ≤ 𝑡 . We require the size to be at most 𝑡 since the items should fit in a cache line. To handle this case, we can redefine the concept of missed edges. We say an edge 𝑒 = ⟨𝑣 1 , 𝑣 2 , . . . , 𝑣 𝑚 , 𝑣 1 ⟩ is missed if and only if by running the access sequence Σ 𝑒 = ⟨𝑣 1 , 𝑣 2 , . . . , 𝑣 𝑚 , 𝑣 1 ⟩ with the same coloring, we get a cache miss at the final position of the sequence. With this definition, it is easy to verify that Lemma 2 and Corollary 5 hold by a simple definition-chasing. Every step of Theorem 7 also holds with the exact same arguments as before. This is because any 𝑡 distinct data items have a total size of at least 𝑡. Our algorithm of Section 3.3 can also be straightforwardly extended to handle varying object sizes. Note that this algorithm simply relies on local checks within each bag to decide if specific edges are missed or not. See the use-cases of is_missed in Algorithm 2. Hence, we can plug in any definition of missed edges that is solely based on the partial coloring of the vertices appearing in the edge. This has no effect on the runtime, either.

B AN ALGORITHM FOR OPTIMAL COLORING USING EDGE-NICE TREE DECOMPOSITIONS

In this section, we present an alternative algorithm for the problem of (𝑡-way) optimal coloring. Just as in Section 3.3, we rely on nice tree decompositions to perform a bottom-up dynamic programming. The difference is that we use a finer notion of niceness, which leads to a better overall runtime.

Edge-nice Tree Decompositions [START_REF] Chatterjee | Efficient parameterized algorithms for data packing[END_REF][START_REF] Cygan | Parameterized algorithms[END_REF]. An edge-nice tree decomposition of an undirected graph/unordered hypergraph 𝐺 = (𝑉 , 𝐸) is a tuple 𝑇 = (𝐵, 𝐸 𝑇 , 𝑟, 𝐺 ↓ ) such that:

• (𝐵, 𝐸 𝑇 , 𝑟 ) is a tree decomposition of 𝐺 .

• 𝐺 ↓ is a function that maps each bag 𝑏 ∈ 𝐵 to a subgraph 𝐺 ↓ (𝑏) of 𝐺.

• The root bag and every leaf bag ℓ are empty, i.e. 𝑉 𝑟 = 𝑉 ℓ = ∅.

• The subgraph associated to each leaf bag ℓ is empty, i.e. 𝐺 ↓ (ℓ) = (∅, ∅).

• Each non-leaf bag 𝑏 is in one of the following forms:

-Introduce Vertex Bag (IV): The bag 𝑏 has exactly one child 𝑏 ′ . Moreover, 𝑉 𝑏 = 𝑉 𝑏 ′ ∪ {𝑢} for some vertex 𝑢 ∉ 𝑉 𝑏 ′ and 𝐺 𝑏 = 𝐺 𝑏 ′ ∪ {𝑢}. In other words, the bag 𝑏 has one new vertex 𝑢 that was not in its child bag 𝑏 ′ . We say that 𝑏 introduces 𝑢. The subgraph 𝐺 ↓ (𝑏) is obtained from 𝐺 ↓ (𝑏 ′ ) by adding the vertex 𝑢. Note that if 𝑢 is not already in 𝐺 ↓ (𝑏 ′ ), then it will be added in 𝐺 ↓ (𝑏) as an isolated vertex. -Forget Vertex Bag (FV): The bag 𝑏 has exactly one child 𝑏 ′ and 𝑉 𝑏 = 𝑉 𝑏 ′ \ {𝑢} for some 𝑢 ∈ 𝑉 𝑏 ′ . Moreover, 𝐺 ↓ (𝑏) = 𝐺 ↓ (𝑏 ′ ). We say that 𝑏 forgets 𝑢.

-Introduce (hyper)Edge Bag (IE): The bag 𝑏 has exactly one child 𝑏 ′ and 𝑉 𝑏 = 𝑉 𝑏 ′ . However, 𝐺 ↓ (𝑏) = 𝐺 ↓ (𝑏 ′ ) ∪ {𝑒} for some edge 𝑒 ∈ 𝐸 whose all endpoints are in 𝑉 𝑏 , i.e. 𝑒 ⊆ 𝑉 𝑏 . We say that 𝑏 introduces 𝑒.

-Join Bag (J): The bag 𝑏 has two children 𝑏 1 and 𝑏 2 . Additionally, 𝑉 𝑏 = 𝑉 𝑏 1 = 𝑉 𝑏 2 and 𝐺 ↓ (𝑏) = 𝐺 ↓ (𝑏 1 ) ∪ 𝐺 ↓ (𝑏 2 ).

• Each (hyper)edge is introduced exactly once.

Fig. 1 .

 1 Fig. 1. A graph 𝐺 = (𝑉 , 𝐸) (left) and a tree decomposition 𝑇 of width 2 for 𝐺 (right).

Fig. 3 .

 3 Fig. 3. Construction of the bipartite graph B.There is an edge from 𝑖 in 𝐿 to 𝑗 in 𝑀 * iff in the access sequence Σ, 𝜎 𝑗 is between 𝜎 𝑖 and the previous access to the same element, i.e. 𝜎 𝑖 ′ .

  This contradicts the definition of 𝐿. Therefore, the total number of edges is at most |𝑀 * | • 𝑘. Putting the two bounds together, we get |𝐿| ≤ |𝑀 * |• 𝑘 𝑑-𝑘 . Combining this with (2), we have | M | ≤ |𝑀 * |• 𝑑 𝑑-𝑘 . □ Corollary 2.

Fig. 4 . 3 ( 3 (

 433 Fig. 4. The subtree 𝑇 ↓ 𝑏 3 (right) and the subgraph 𝐺 ↓ 𝑏 3 (left) of the bag 𝑏 3 of Figure 1.

Fig. 5 .

 5 Fig. 5. 𝑏 has one vertex more than 𝑐. A coloring of 𝑏 also colors 𝑐. New edges in 𝐺 ↓ 𝑏 , i.e. part (a), are shown in red.

(Fig. 6 .

 6 Fig.6. 𝑐 has one vertex 𝑣 more than its parent 𝑏. The coloring of 𝑓 𝑏 sets colors for all vertices of 𝑐 except 𝑣. This vertex can have any color.

4 : 6 :

 46 if 𝑏.children = ∅ then 5: dp[𝑏, 𝑓 𝑏 ] ← 0 else if |𝑏.children| = 1 then 7:

25 : 27 :

 2527 if is_missed(𝑒, 𝑓 𝑏 ) then 26: dp[𝑏, 𝑓 𝑏 ] ← dp[𝑏, 𝑓 𝑏 ] -1 𝑟 ← 𝑇 .root28: return dp[𝑟, ⊥]

Fig. 11 .

 11 Fig. 11. Treewidths of our test cases. The 𝑥 axis is the treewidth of the sparsified access hypergraph G𝑑 and the 𝑦 access is the number of cases.

Fig. 12 .

 12 Fig. 12. Performance of our algorithm vs BB (top), SCE (middle), and CKJA (bottom).

Fig. 13 .

 13 Fig. 13. Number of cache misses obtained by our algorithm vs the theoretical lower bounds of Theorem 1.

3 )

 3 By definition, we have |𝑀 * | = Misses 𝑘 (𝑓 * , Σ) and | M | = Misses 𝑘 ( f , Σ). As in Theorem 1, let 𝐿 be the set of indices in Σ that correspond to edges in 𝐸 1 but do not lead to a cache miss in 𝑓 * . With the same argument as in Theorem 1, we have |𝑀 * | ≥ Cost( f , G𝑑 ) + |𝐸 1 | -|𝐿|. (We put (3) and Corollary 5 together to obtain | M | ≤ |𝑀 * | + |𝐿|. (4) Hence, in order to bound | M | in terms of |𝑀 * |, we need to find an upper-bound on |𝐿|.

  Putting the two bounds together, we get |𝐿| ≤ |𝑀 * | • 𝑡 •𝑘 𝑑-𝑡 •𝑘 . Combining this with (4), we have | M | ≤ |𝑀 * | • 𝑑 𝑑-𝑡 •𝑘 . □ Corollary 6.

  . Consider a placement map 𝑓 : 𝑂 → {1, 2, . . . , 𝑘 }. By definition, 𝑓 assigns a cache line to every object 𝑜 𝑖 ∈ 𝑂. However, given that 𝑂 is also the set of vertices in our access hypergraphs, one can equivalently think of 𝑓 as a coloring of vertices in these graphs with 𝑘 colors 3 . Direct Mapping. Let us first assume that we have a direct mapping instance, i.e. 𝑡 = 1 and each cache line can hold only one object.Sparsification. Consider the access hypergraph 𝐺 𝑑 of order 𝑑. Recall that 𝐺 𝑑 has an edge 𝑒 𝑖 corresponding to each access 𝜎 𝑖 in Σ. We divide the edges of 𝐺 𝑑 in two groups: 𝐸 1 is the set of edges 𝑒 𝑖 that contain the vertex 𝜎 𝑖 only once and 𝐸 2 is the set of edges 𝑒 𝑖 that contain 𝜎 𝑖 twice. Let G𝑑 = (𝑂, 𝐸 2 ) be the subgraph of 𝐺 𝑑 containing only the edges of the second kind. We call G𝑑 the sparsified access hypergraph of order 𝑑. Informally, G𝑑 keeps the edge corresponding to an access 𝜎 𝑖 iff the number of other distinct data items seen since the last access to 𝜎 𝑖 is less than 𝑑. The intuition is to focus on data items that are accessed regularly and whose placement in the memory really matters in the number of cache misses. These are elements that can likely cause capacity/conflict misses. In contrast, we would rather ignore elements that are accessed only once or rarely and cause a compulsory first-time cache miss anyway. In other words, if many distinct data items have been accessed since the last time we saw 𝜎 𝑖 , then it is very likely that 𝜎 𝑖 is already evicted

  {𝑜 3 , 𝑜 4 , 𝑜 6 } 𝑏 3 {𝑜 4 , 𝑜 5 , 𝑜 6 } 𝑏 4 {𝑜 4 , 𝑜 6 , 𝑜 7 } 𝑏 5

	2:	𝑑 ← ⌈𝑡 • 𝑘 + 𝑡 •𝑘 𝜖 ⌉
	3:	𝐸 2 ← ∅
	4:	for 𝑖 = 1 to 𝑁 do
	5:	𝑒 𝑖 ← ⟨𝜎 𝑖 ⟩
	6:	for 𝑗 = 𝑖 -1 downto 1 do
	7:	𝑒 𝑖 ← ⟨𝜎 𝑗 ⟩ + 𝑒 𝑖
	8:	if 𝜎 𝑗 = 𝜎 𝑖 then
	9:	𝐸 2 ← 𝐸 2 ∪ {𝑒 𝑖 }
	10:	break
	11:	if |set(𝑒 𝑖 )| > 𝑑 then
	12:	break
	13:	𝑇 = (𝐵, 𝐸 𝑇 ) ← NiceTreeDecomposition(𝑂, 𝐸 2 )
	14:	return OptimalColoring(𝑂, 𝐸 2 , 𝑡, 𝑘,𝑇 )
		𝑜 3	𝑜 4
		𝑜 5	𝑜 6
		𝑜 7

1: procedure CDP(𝑛, 𝑂, 𝑁 , Σ, 𝑡, 𝑘, 𝜖)

  Fig.7. 𝑏 has two children 𝑐 1 and 𝑐 2 . A coloring of 𝑏 will also color all vertices in 𝑉 𝑐 1 and 𝑉 𝑐 2 . Some edges are shared between 𝐺

	b
	c 1	c 2

2 , 𝑓 𝑏 ] number of missed edges in 𝐸 𝑏 As before, the algorithm can check whether an edge 𝑒 ∈ 𝐸 𝑏 is missed because the partial coloring 𝑓 𝑏 provides the color information for all endpoints of 𝑒. ↓ 𝑐 1 and 𝐺 ↓ 𝑐 2 . All such edges appear in 𝑏.

  𝑓 𝑏 ] ← dp[𝑐, 𝑓 𝑐 ] 𝑒 ∧ is_missed(𝑒, 𝑓 𝑏 ) then 𝑓 𝑏 ] ← dp[𝑏, 𝑓 𝑏 ] + 1 15: else if 𝑉 𝑏 ⊆ 𝑉 𝑐 then

	9:	𝑣 ← 𝑉 𝑏 \ 𝑉 𝑐
	10:	𝑓 𝑐 ← 𝑓 𝑏 |𝑉 𝑐
	11: dp[𝑏, 12: for 𝑒 ∈ 𝐸 𝑏 do
	13: if 𝑣 ∈ 14: dp[𝑏, 16: 𝑣 ← 𝑉 𝑐 \ 𝑉 𝑏
	17:	dp[𝑏, 𝑓 𝑏 ] ← +∞
	18:

Table 1 .

 1 Comparison of our algorithm with the baselines. The total number of benchmarks instances is 1633. Each cell contains the number of instances in which our algorithm outperformed the base line (left) and the number of instances in which the baseline had fewer misses (right).

		CKJA	BB	SCE
	Our Algorithm	P P P P P P P P 1395 238	P P P P P P 1373 260 P P P 1441 P P	P P P P P 192

The FIFO and ORP cases are removed since the space is limited and they do not provide new insights. We will publish them as a tech report.

The definition of access hypergraphs provided here is a bit different from[START_REF] Chatterjee | Efficient parameterized algorithms for data packing[END_REF] since we allow our hyperedges to include the same vertex more than once. However, this difference does not affect the treewidth.

Adjacent vertices need not necessarily have different colors.

Without loss of generality, we can assume every edge in G𝑑 has exactly 𝑑 + 1 endpoints. Each edge has exactly 𝑑 distinct vertices and removing repetitive internal vertices from the edge has no effect in our algorithm.

ACKNOWLEDGMENTS

We are extremely grateful to the anonymous reviewers for their suggestions, which significantly improved the quality of this work. The research was partially supported by the HKUST-Kaisa Joint Research Institute Project Grant HKJRI3A-055 and HKUST Startup Grant R9272.

A DETAILS OF THE SPARSIFICATION FOR 𝑡-WAY MAPPING

In this section, we provide a detailed treatment of our method over 𝑡-way mapping instances. Throughout this section, we fix a CDP instance 𝐼 = (𝑛, 𝑂, 𝑁 , Σ, 𝑡, 𝑘) with 𝑡 ≥ 2. We define colorings, sparsification and canonical hypergraphs in the exact same manner as in the case of direct mapping (Section 3.2). Specifically, we focus on the sparsified access hypergraph G𝑑 of order 𝑑, which is canonical by definition.

Missed Edges. Consider a canonical hypergraph 𝐺 = (𝑉 , 𝐸) and a coloring function 𝑓 : 𝑉 → {1, 2, . . . , 𝑘 }.

We say an edge 𝑒 = ⟨𝑣 1 , 𝑣 2 , . . . , 𝑣 𝑚 , 𝑣

Intuitively, such an edge corresponds to a situation where 𝑣 1 and at least 𝑡 of the internal vertices are mapped to the same cache line.

Optimal 𝑡-way Coloring. We define Cost 𝑡 (𝑓 , 𝐺) of a coloring function 𝑓 as the number of missed edges.

The optimal 𝑡-way coloring problem asks for a coloring f with minimal cost.

The following lemma establishes a correspondence between cache misses in indices of 𝐸 2 and missed edges in G𝑑 . Recall that 𝐸 2 is the set of edges 𝑒 𝑖 that contain the data item 𝜎 𝑖 twice. Lemma 2. Let 𝑓 be a coloring of vertices in G𝑑 = (𝑂, 𝐸 2 ) or equivalently a placement map for 𝐼 = (𝑛, 𝑂, 𝑁 , Σ, 𝑡, 𝑘). An edge 𝑒 𝑖 ∈ 𝐸 2 is missed in the coloring 𝑓 iff a cache miss occurs at its corresponding access 𝜎 𝑖 with placement map 𝑓 .

Proof. Recall that 𝑒 𝑖 is of the form ⟨𝜎 𝑗 , 𝜎 𝑗+1 , . . . , 𝜎 𝑖 ⟩ and since G𝑑 is canonical we have 𝜎 𝑖 = 𝜎 𝑗 . If 𝑒 𝑖 is a missed edge, then the data item 𝜎 𝑖 was brought to cache line 𝑓 (𝜎 𝑖 ) at time 𝑗, but by time 𝑖, it was already evicted. Given that our replacement policy is LRU, this means at least 𝑡 other elements have entered this cache line, otherwise 𝜎 𝑖 would not have been evicted. By definition, those 𝑡 elements have the same color as 𝜎 𝑖 and hence 𝑒 𝑖 is a missed edge. Conversely, if 𝑒 𝑖 is a missed edge, then there are at least 𝑡 distinct data items accessed between times 𝑗 and 𝑖 that shared the same color 𝑓 (𝜎 𝑖 ). Hence, 𝜎 𝑗 = 𝜎 𝑖 is evicted before time 𝑖 and the access at time 𝑖 is a cache miss.

Proof. Recall that 𝑓 * is the optimal placement map that minimizes the number of cache misses and f is the optimal coloring that minimizes the number of missed edges in G𝑑 . Consider f as a placement map.

Based on the lemma above, it causes exactly Cost( f , G𝑑 ) cache misses in accesses corresponding to 𝐸 2 . It can also cause at most |𝐸 1 | cache misses in accesses corresponding to 𝐸 1 .

Based on the corollary above, we can find a bound on the optimal number of cache misses based on the cost of f . Theorem 7. We have

Intuitively, an edge-nice tree decomposition is finer than a nice tree decomposition. In the latter, we also have IV, FV and J bags and the vertices are added or removed one-by-one, but each newly introduced vertex can automatically add many new edges to the subgraph 𝐺 ↓ 𝑏 of the current bag 𝑏. In contrast, in an edge-nice tree decomposition, the edges are also added one-by-one. Moreover, since each edge is introduced only once, we can be sure that in a join bag 𝑏 with children 𝑏 1 and 𝑏 2 , the left subgraph 𝐺 ↓ (𝑏 1 ) and the right subgraph 𝐺 ↓ (𝑏 2 ) are edge-disjoint. Any tree decomposition can be turned into an edge-nice decomposition of the same width in linear time [START_REF] Cygan | Parameterized algorithms[END_REF]. In practice, we do not store the subgraphs 𝐺 ↓ (𝑏) in memory. We just keep track of the vertices/edges that are introduced or forgotten at every bag.

We now present our dynamic programming algorithm for optimal coloring using an edge-nice tree decomposition. The algorithm is similar to that of Section 3.3 and computes the following variables in a bottom-up manner: Dynamic Programming Variables. For every bag 𝑏 ∈ 𝐵 and partial coloring 𝑓 𝑏 ∈ C 𝑏 , the algorithm defines a dynamic programming variable dp[𝑏, 𝑓 𝑏 ] and initializes it to +∞. Our goal is to compute values for the dp[•, •] in a bottom-up order such that the following invariant holds after we compute dp[𝑏, 𝑓 𝑏 ]:

in which 𝑉 𝑏 is colored according to 𝑓 𝑏 Computing dp Values. The algorithm processes the bags in a bottom-up order and performs the following computations at each bag according to its type:

(1) Leaf Bags. In a leaf bag ℓ ∈ 𝐵, we have 𝑉 ℓ = ∅ and 𝐺 ↓ ℓ = (∅, ∅). Hence, there is only one possible trivial coloring 𝑓 ℓ . The algorithm sets dp[ℓ, 𝑓 ℓ ] = 0 since there are no edges to be missed.

(2) IV Bags. Suppose 𝑏 is an IV bag introducing the vertex 𝑢. Let 𝑏 ′ be the only child of 𝑏. Any partial coloring 𝑓 𝑏 : 𝑉 𝑏 → {1, . . . , 𝑘 } also colors 𝑉 𝑏 ′ . Moreover, 𝐺 ↓ (𝑏) has the exact same set of edges as 𝐺 ↓ (𝑏 ′ ). Thus, the algorithm sets dp[𝑏,

(3) FV Bags. If 𝑏 is an FV bag forgetting 𝑢 and its only child is 𝑏 ′ , then we have 𝐺 ↓ (𝑏) = 𝐺 ↓ (𝑏 ′ ). However, a partial coloring 𝑓 𝑏 ∈ C 𝑏 does not assign a color to 𝑢. So, the algorithm should check all possibilities for the color of 𝑢. Hence, it sets dp[𝑏,

) IE Bags. Suppose that 𝑏 introduces the (hyper)edge 𝑒. Let 𝑏 ′ be the child of 𝑏. Then, the only difference between 𝐺 ↓ (𝑏) and 𝐺 ↓ (𝑏 ′ ) is that the former contains the extra edge 𝑒. Moreover, 𝑉 𝑏 = 𝑉 𝑏 ′ . For every partial coloring 𝑓 𝑏 ∈ C 𝑏 , the algorithm checks whether 𝑒 is a missed edge in 𝑓 𝑏 . This (5) J Bags. Let 𝑏 be a join bag with children 𝑏 1 and 𝑏 2 . Since each (hyper)edge is introduced exactly once, we know that 𝐺 ↓ (𝑏 1 ) and 𝐺 ↓ (𝑏 2 ) are (hyper)edge-disjoint. Moreover, since 𝑉 𝑏 = 𝑉 𝑏 1 = 𝑉 𝑏 2 , every partial coloring 𝑓 𝑏 ∈ C 𝑏 is inherited by 𝑏 1 and 𝑏 2 . As such, the algorithm sets dp[𝑏,

The algorithm computes the final answer and the optimal coloring exactly as in Section 3.3. The argument for its correctness is also similar.

Computing the Final Answer. Since 𝑇 is edge-nice, we have 𝑉 𝑟 = ∅. So, there is only one possible partial coloring 𝑓 𝑟 ∈ C 𝑟 for the root bag 𝑟 . Moreover, we have 𝐺 ↓ (𝑟 ) = 𝐺 . So, the algorithm outputs dp[𝑟, 𝑓 𝑟 ] as the minimal number of missed edges.

Finding the Optimal Coloring. Our algorithm obtains the minimal number of missed edges. As in many other dynamic programming methods, we can obtain the optimal coloring itself by keeping track of the partial colorings that led to the optimal dp[•, •] value at every step.

Based on this algorithm, we obtain the following variant of Theorem 3: Theorem 8. Given positive integer constants 𝑡 and 𝑘, a canonical hypergraph 𝐺, with 𝑛 vertices and 𝑁 edges, each with at most 𝑑 endpoints, and an edge-nice tree decomposition of 𝐺 with 𝑂 (𝑛 + 𝑁 ) bags and width 𝑤, the algorithm above solves the (𝑡-way) optimal coloring problem in total runtime 𝑂 ((𝑛 + 𝑁 ) • 𝑘 𝑤+2 ).

Proof. The edge-nice tree decomposition has 𝑂 (𝑛 + 𝑁 ) bags. At each bag, we define at most 𝑘 𝑤+1 dp variables, one for each partial coloring. Computing each of these variables takes 𝑂 (1) time in cases 1, 2, 4 and 5 above, and 𝑂 (𝑘) time in case 3.