Grant: Discovery Grants Program - Individual
University of Waterloo
$39,000.00
Techniques for Coping with Increasingly Non-uniform Memory Architectures
EF 2024-25
Résumé
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.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Ontario, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data
Tel que publié
Application id
RGPIN-2019-04227
Name nom
Brown, Trevor
Department département
Department of Computer Science
Organization id
33
Institution établissement
University of Waterloo
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2024
Competition year année de concours
2019
Award amount
39000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR LA DÉCOUVERTE
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
801
Area of application group en
Information and communication services
Area of application group fr
Services d'information et de télécommunications
Area of application en
Computer software
Area of application fr
Logiciel
Research subject code
2704
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Distributed and parallel processing
Research subject fr
Traitement réparti et simultané
Field of research list names en
Not available
Field of research list names fr
Non disponible
Socioeconomic objective list names en
Not available
Socioeconomic objective list names fr
Non disponible
Application title
Techniques for Coping with Increasingly Non-uniform Memory Architectures
Keywords
non-uniform memory architectures; multicore; concurrency; data structures; non-volatile memory; synchronization; distributed systems; remote direct memory access; lock-freedom; performance evaluation
Application summary
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.