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.