Data Structures and Algorithms for Maintaining Data Locality

随着现代存储器体系结构的复杂性不断增加，设计具有高数据局部性的算法变得越来越重要。标准方法通过存储器层次结构的各个方面来参数化算法，例如每个存储器级别的大小和块大小。不幸的是，这种参数化通常会导致针对特定体系结构进行调整的复杂算法。 一个有前途的新的研究方向是开发内存层次敏感的算法，避免任何内存特定的参数化。这种平台无关的算法被称为“缓存无关”。“如果一个高速缓存无关算法在两级层次结构上工作最优，那么它在多级存储器层次结构的所有级别上都工作最优;高速缓存无关算法自动调整到任意内存架构。这项研究涉及在不规则和动态设置中维护数据局部性，其中的数据流是不断变化和不可预测的。调查员将设计缓存无关的解决方案，为各种基础算法和数据-结构问题。 新的算法模型方面的内存层次结构将被提出和整合。调查员将强调解决方案是简单和优雅的实现。 正在StonyBrook开发的两个核查工具将为项目的经验部分提供试验平台。

As modern memory architectures grow in complexity, it is becomingincreasingly important to design algorithms with high data locality.Standard approaches parameterize algorithms by aspects of the memoryhierarchy, such as the size and block size of each memory level.Unfortunately, this parameterization often leads to complex algorithmsthat are tuned to particular architectures. A promising new line ofresearch is to develop memory-hierarchy-sensitive algorithms that avoidany memory-specific parameterization. Such platform-independent algorithmsare said to be "cache-oblivious." If a cache-oblivious algorithm worksoptimally on a two-level hierarchy, then it works optimally on all levelsof a multilevel memory hierarchy; cache-oblivious algorithms automaticallytune to arbitrary memory architectures.This research involves maintaining data locality in irregular and dynamicsettings, where the data flow is continually changing and unpredictable.The investigator will design cache-oblivious solutions for a variety offundamental algorithms and data-structures problems. New algorithmicmodels of aspects of the memory hierarchy will be proposed and integrated.The investigator will emphasize solutions that are simple and elegantenough to implement. Two verification tools under development at StonyBrook will provide testbeds for the project's empirical component.