Efficient parameterized algorithms for data packing
Efficient parameterized algorithms for data packing
复制标题
用于数据打包的高效参数化算法
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Andreas Pavlogiannis
中科院分区：
文献类型：
--
作者：
K. Chatterjee;A. Goharshady;Nastaran Okati;Andreas Pavlogiannis
现代缓存的速度和主要记忆之间存在巨大的差距，因此，缓存却错过了考虑程序的主要效率的考虑，以解决此问题。将其包装到同一缓存块中，从而最大程度地减少了对主要内存的访问访问数据元素的序列是，任务是将元素划分为“缓存块对于大于4的缓存大小而言，很难近似。因此，所有现有的数据包装技术都是基于启发式方法，并且缺乏理论保证。数据包装，加上新的和更强的负面结果。我们研究了通过访问超图的树宽参数，这是图理论中的标准概念，用于测量图与树的亲密关系。有一个数字q*，具体取决于缓存参数，以便（a）订单Q*具有恒定的树宽，则有一个线性时间算法用于数据包装（b）数据包装问题仍然是NP - 即使访问Q*-1的访问超图具有恒定的树宽，我们会根据单个参数建立细粒度的二分法width;最终，我们的算法的原型实现了，我们的结果表明，在实践中，我们的算法是许多常用的算法的访问，我们采用几种基于启发式启发式的算法的方法，表明我们的算法会导致较少的缓存可能性。
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 that 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.