Theory and implementation of algorithms & data structures for memory hierarchies

算法原理与实现

• 批准号: 298332-2007
• 负责人: Zeh, Norbert
• 金额: $ 2.11万
• 依托单位: Dalhousie University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2007
• 资助国家: 加拿大
• 起止时间: 2007-01-01 至 2008-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=363412
• 关键词: 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:(1)  Graph problems.  This is motivated by applications that have to process massive graphs efficiently, such as web mining and web modelling, geographic information systems, and information retrieval.(2)  Data structures and algorithms for fundamental geometric search problems, most notably range search problems.  The motivation is the need to answer such search problems efficiently in database applications and geographic information systems.

我的研究重点是内存层次结构的算法和数据结构的理论和实现。​当前的技术发展导致处理器速度和内存 (RAM) 传输速率之间的差距迅速扩大。如果磁盘访问时间较长，这种差距会更加显着。因此，除非有办法弥合处理器和内存速度之间的差距，否则当今的处理器毫无用处。最先进的计算机中解决此问题的方法是使用多个级别的层次结构。仅当运行的程序具有足够的本地内存访问模式以确保大多数内存访问可以从高速缓存而不是从主内存或磁盘提供时，此方法才有用。对许多计算问题具有挑战性。​​​​这是我的研究重点。​​​​我的研究计划有一个理论和一个更应用的方面。​​​​理论工作旨在开发设计算法和计算的通用技术具有高访问局部性的数据结构。​​​应用的工作将应用这些技术并通过实施和实验评估它们在特定问题设置中的有效性：（1）图问题这是由必须有效处理大量图的应用程序（例如网络挖掘）推动的。以及网络建模、地理信息系统和信息检索。(2) 基本几何搜索问题的数据结构和算法，尤其是范围搜索问题。其动机是需要在数据库应用程序和地理信息系统中有效地解决此类搜索问题。