ITR/SY(CISE): Cache-Oblivious Data Structures

提案编号：0112849主要作者：Arge，Lars机构名称：杜克大学名称：ITR/SY（CISE）：缓存不经意的数据结构随着现代计算机中的内存系统变得越来越复杂，设计对内存结构敏感的算法变得越来越重要。现代内存系统的一个基本特征是它们由几个层次的高速缓存、主存和磁盘组成。虽然传统的理论存储器模型已经假设具有统一访问时间的“平坦”存储器，但是在当前机器中，不同级别的存储器的访问时间可以变化几个数量级。例如，一级缓存通常比主存快100倍，而主存比磁盘快100万倍。为了分摊远离处理器的存储器级的大量访问时间，存储器系统通常以大块在存储器级之间传输数据。因此，在内存访问模式中获得高的数据局部性变得越来越重要。本项目将重点关注在不规则和动态问题中试图保持数据局部性时遇到的挑战性问题，根据定义，数据流不断变化和不可预测，难以事先组织数据局部性。特别是，高速缓存无关的动态数据结构将被开发这样的数据结构可以反过来被用来开发高速缓存有效的算法。直到最近才开发出第一个（也是唯一一个）这样的动态缓存无关数据结构。这个结构是一个搜索树的缓存遗忘版本。这个项目的宏伟目标是为其他基本问题开发高速缓存无关结构。在这个过程中，将开发设计高速缓存无关数据结构的一般技术。将考虑在各种应用领域中应用的数据结构，但将特别关注几何结构。这种结构通常在空间数据库和地理信息系统等方面具有重要的应用。该项目是高风险的，因为几乎没有什么是已知的动态缓存无关的数据结构，但它有可能彻底改变该地区的缓存和I/O有效的计算，并作出巨大的实际影响。最终，这项研究可能会导致一个标准的缓存无关数据结构库。这种独立于平台的数据结构将使程序员能够轻松地开发各种各样的应用程序，这些应用程序在所有现代内存层次结构上都能获得高性能。

PROPOSAL NO.: 0112849PRINCIPAL INVESTIGATOR: Arge, LarsINSTITUTION NAME: Duke UniversityTITLE: ITR/SY(CISE): Cache-Oblivious Data StructuresAs the memory system in modern computers grows more complex, it is becoming increasingly important to design algorithms that are sensitive to the structure of the memory. One of the essential features of modern memory systems is that they are made up of a hierarchy of several levels of cache, main memory, and disk. While traditional theoretical memory models have assumed a "flat" memory with uniform access time, the access times of different levels of memory can vary by several orders of magnitude in current machines. For example, level-one cache is often around 100 times faster than main memory, while main memory is around1,000,000 times faster than disks. In order to amortize the large access time of memory levels far away from the processor, memory systems often transfer data between memory levels in large blocks. Thus it is becoming increasingly important to obtain high data locality in memory access patterns.This project will focus on the challenging problems encountered when trying to maintain data locality in irregular and dynamic problems, where by definition the data flow is continually changing and unpredictable, making it difficult to organize data locality a priori. In particular, cache-oblivious dynamic data structures will be developed-such data structures can in turn be used to develop cache-efficient algorithms. Only very recently was the first (and only) such dynamic cache-oblivious data structure developed. This structure is a cache-obliviousversion of a search tree. The ambitious goal of this project is to develop cache-oblivious structures for other fundamental problems. In the process general techniques for designing cache-oblivious data structures will be developed. Data structures with applications in a variety of application areas will be considered, but there will be a particular focus on geometric structures. Such structures often have important applications in e.g. spatial databases and geographic information systems (GIS). The project is high-risk because almost nothing is known about dynamic cache-oblivious data structures, but it has the potential to revolutionize the area ofcache- and I/O-efficient computation and to make a tremendous practical impact. Ultimately this research could lead to a standard library of cache-oblivious data structures. Such platform-independent data structures would enable programmers to easily develop a wide variety of applications that obtain high performance on all modern memory hierarchies.