Theory and implementation of algorithms & data structures for memory hierarchies

算法原理与实现

• 批准号: 298332-2007
• 负责人: Zeh, Norbert
• 金额: $ 2.11万
• 依托单位: Dalhousie University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2008
• 资助国家: 加拿大
• 起止时间: 2008-01-01 至 2009-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=396056
• 关键词: Theory; implementation; algorithms; data; structures

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:

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