Techniques for Coping with Increasingly Non-uniform Memory Architectures

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

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.