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

建议编号：0112849 PRINCIPAL调查员：ARGE，LarsInstitution名称：Duke University TITLE：ITR/SY(CESE)：高速缓存无关数据结构随着现代计算机中的存储系统变得越来越复杂，设计对存储器结构敏感的算法变得越来越重要。现代存储系统的基本特征之一是它们由多个级别的高速缓存、主存和磁盘的层次结构组成。虽然传统的理论内存模型假设访问时间相同的“扁平”内存，但在当前机器中，不同级别内存的访问时间可能会有几个数量级的差异。例如，一级缓存通常比主内存快约100倍，而主内存比磁盘快约1,000,000倍。为了将远离处理器的存储级的大访问时间摊销，存储系统经常以大块的形式在存储级之间传输数据。因此，在内存访问模式中获得高的数据局部性变得越来越重要。本项目将关注在不规则和动态问题中保持数据局部性时遇到的挑战性问题，根据定义，数据流不断变化和不可预测，使得先验地组织数据局部性变得困难。具体地说，将开发高速缓存无关的动态数据结构--这样的数据结构又可用于开发高速缓存高效的算法。直到最近，才开发出第一个(也是唯一一个)这样的动态缓存无关数据结构。此结构是搜索树的缓存忽略版本。该项目雄心勃勃的目标是为其他基本问题开发与缓存无关的结构。在这个过程中，将开发设计高速缓存无关数据结构的一般技术。将考虑在各种应用领域中应用的数据结构，但将特别关注几何结构。这种结构通常在例如空间数据库和地理信息系统(GIS)中有重要的应用。该项目风险很高，因为对动态缓存无关数据结构几乎一无所知，但它有可能彻底改变缓存和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.