Techniques for Coping with Increasingly Non-uniform Memory Architectures

应对日益不均匀的内存架构的技术

• 批准号: RGPIN-2019-04227
• 负责人: Brown, Trevor
• 金额: $ 2.84万
• 依托单位: University of Waterloo
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2020
• 资助国家: 加拿大
• 起止时间: 2020-01-01 至 2021-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=714133
• 关键词: Techniques; Coping; Increasingly; Non; uniform

Nearly all modern computers contain multiple processors, which can execute multiple threads of computation in parallel. Large systems with dozens or hundreds of processors are used extensively by companies that provide Internet, e-commerce and cloud services at massive scales. So, there is a need for techniques that make it easier to program such systems and efficiently harness their computational power, as well as graduates who can program them. Reasoning about multi threaded computation is notoriously difficult, so to make it easier to write software for such systems, researchers have designed many convenient building blocks for programmers called data structures. Most published data structures were designed for systems with uniform memory architectures (UMAs), where all threads of computation pay approximately the same costs to access memory. However, in recent years, systems are rapidly trending towards non-uniform memory architectures (NUMAs), where some memory is local to a thread, and other memory is remote (and costly to access). Most classical data structures were designed for UMAs, and they can perform extremely poorly on NUMAs. NUMAs have non-trivial connections to load balancing, data partitioning and distributed systems, and represent one of the most important problems on the path to efficient, scalable computing. The goal of this research program is to develop efficient data structures for all computing scales, from small UMA systems, to large NUMA systems, to massive distributed systems. Towards this goal, my students and I will pursue two main objectives. First, we will develop novel algorithmic techniques, data structures and system software for coping with increasingly NUMA systems. Second, we will explore new and upcoming hardware capabilities such as remote direct memory access (RDMA), which allows a thread on one computer to directly access the memory of another computer, and non-volatile random-access memory (NVRAM), an upcoming memory technology that combines the speed of traditional memory with the capacity and persistence of hard disks. My students and I will find new ways to harness these technologies to improve classical data structures and algorithms. For example, we will use RDMA to redesign data structures so they can be used in massive distributed systems, and we will use NVRAM to improve data structures so they will never lose data in the event of a power failure. My students will conduct both theoretical and systems-oriented studies: developing clean and provably correct abstractions, implementing their ideas on large scale systems with hundreds of processors, conducting rigorous performance experiments, integrating the data structures they develop into open-source software, and accumulating skills along the way that will serve them well in industry or academia.

几乎所有现代计算机都包含多个处理器，它们可以并行执行多个计算线程。大规模提供互联网、电子商务和云服务的公司广泛使用具有数十个或数百个处理器的大型系统。因此，需要一种能够更轻松地对此类系统进行编程并有效利用其计算能力的技术，以及能够对其进行编程的毕业生。众所周知，推理多线程计算非常困难，因此为了更容易为此类系统编写软件，研究人员为程序员设计了许多方便的构建块，称为数据结构。大多数已发布的数据结构都是为具有统一内存架构（UMA）的系统而设计的，其中所有计算线程访问内存的成本大致相同。然而，近年来，系统迅速趋向于非统一内存架构（NUMA），其中一些内存对于线程来说是本地的，而其他内存是远程的（并且访问成本高昂）。大多数经典数据结构都是为 UMA 设计的，它们在 NUMA 上的性能极差。 NUMA 与负载平衡、数据分区和分布式系统有着重要的联系，并且是高效、可扩展计算道路上最重要的问题之一。 该研究计划的目标是为所有计算规模开发高效的数据结构，从小型 UMA 系统到大型 NUMA 系统，再到大规模分布式系统。为了实现这一目标，我和我的学生将追求两个主要目标。首先，我们将开发新颖的算法技术、数据结构和系统软件，以应对日益增长的 NUMA 系统。其次，我们将探索新的和即将推出的硬件功能，例如远程直接内存访问 (RDMA)，它允许一台计算机上的线程直接访问另一台计算机的内存，以及非易失性随机存取存储器 (NVRAM)，这是一种即将推出的技术。将传统内存的速度与硬盘的容量和持久性相结合的内存技术。我和我的学生将找到新的方法来利用这些技术来改进经典数据结构和算法。例如，我们将使用RDMA来重新设计数据结构，以便它们可以在大规模分布式系统中使用，我们将使用NVRAM来改进数据结构，以便它们在断电时永远不会丢失数据。 我的学生将进行理论和面向系统的研究：开发干净且可证明正确的抽象，在具有数百个处理器的大型系统上实现他们的想法，进行严格的性能实验，将他们开发的数据结构集成到开源软件中，并积累一路走来的技能将有助于他们在工业界或学术界发挥作用。