Data Structures and Algorithms for Maintaining Data Locality

点击翻译按钮获取中文摘要

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.