Techniques for Coping with Increasingly Non-uniform Memory Architectures

点击翻译按钮获取中文摘要

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.