Techniques for Coping with Increasingly Non-uniform Memory Architectures

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

• 批准号: RGPIN-2019-04227
• 负责人: Brown, Trevor
• 金额: $ 2.84万
• 依托单位: University of Waterloo
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2021
• 资助国家: 加拿大
• 起止时间: 2021-01-01 至 2022-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=737494
• 关键词: 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来改善数据结构，因此在电源故障的情况下，它们将永远不会丢失数据。我的学生将同时进行理论和以系统为导向的研究：开发清洁且可证明的正确的抽象，将他们的想法与数百个处理器上实施，进行严格的性能实验，将开发的数据结构整合到开放源代码软件中，并累积一路上可以在行业或学术界为他们提供良好服务的技能。