Theory and implementation of algorithms & data structures for memory hierarchies

我的研究重点是内存层次结构的算法和数据结构的理论和实现。当前的技术发展导致处理器速度和内存（RAM）传输速率之间的差距迅速扩大。如果考虑到磁盘访问时间，这个差距甚至更大。因此，今天的处理器是无用的，除非有一种方法弥合处理器和内存速度之间的差距。在最先进的计算机中，解决这个问题的方法是使用多层快速但相对较小的缓存存储器。只有当运行的程序具有足够的本地内存访问模式，以确保大多数内存访问可以从缓存而不是从主内存或磁盘提供时，这种方法才有用。对于许多计算问题来说，实现这种局部性是具有挑战性的。这是我研究的重点。我的研究项目既有理论方面的，也有应用方面的。理论工作的目的是开发设计具有高访问局部性的算法和数据结构的通用技术。应用工作将应用这些技术，并通过实施和实验来评估它们在特定问题设置中的有用性。我关注的具体问题有：

My research focuses on the theory and implementation of algorithms and data structures for memory hierarchies. Current technological developments lead to a rapidly widening gap between processor speeds and memory (RAM) transfer rates. This gap is even more significant if disk access times are taken into account. Hence, today's processors are useless unless there is a way to bridge the gap between processor and memory speeds. The approach to this problem taken in state-of-the-art computers is the use of a hierarchy of several levels of fast, but relatively small, cache memory. This approach is useful only if the programs that are run have sufficiently local memory access patterns that ensure that most memory accesses can be served from cache rather than from main memory or disk. Achieving this locality is challenging for many computational problems. This is the focus of my research. My research programme has a theoretical and a more applied facet. The theoretical work aims at developing general techniques for designing algorithms and data structures with high access locality. The applied work will apply these techniques and evaluate their usefulness in particular problem settings through implementation and experimentation. The particular problems I focus on are: