CSR: Small: Data Structure Designs and Implementations for Modern Multicore Architectures and Applications

Lehigh University, Bethlehem PA

Investigators

Abstract

Data Structures are the conventional way to store data managed by applications and system software. Developing data structures that function correctly even in the presence of multiple simultaneous operations has been one of the most important topics in the last decade. This project moves research on data structures ahead by targeting the way these data structures interact with the underlying hardware infrastructure. The project proposes innovative software designs and features that allow data structure implementations to improve performance when deployed on modern servers equipped with hundreds of processors, and to meet new application necessities. This project investigates data structure designs and implementations that exploit the hardware organization of modern multicore architectures, where memory is partitioned in multiple zones and each zone is subject to an access latency that is influenced by the source and destination zone (also known as Non-Uniform Memory Access, or NUMA, architectures), to improve application performance. The core intuition is to divide the data structure into independent layers, avoid synchronization across them, and distributed them among NUMA zones. The proposal identifies four research tasks, ranging from hardware optimizations to scalable bulk operations over the data within the data structures. The outcomes of this project include delivering to programmers, industry, and academia a new open-source data structure library that scales its performance in modern multicore architectures and meets emerging application needs. The results of this research will provide a basis for a new module focused on data structures in a course that includes concurrency in its curriculum, and will influence the materials that will be included in a reference textbook on principles and best practices of concurrent programming. Findings of this project will enable new engagement with local communities and public schools to inspire next generation of practitioners. Any data produced in the context of this project will be made available to the public and rigorously maintained throughout the duration of the project and beyond. Developed source code will initially be maintained in a private repository (Bitbucket), with periodic public deliverables. After the software becomes stable, it will transition to a public repository (Github) so that a larger open-source community can use and maintain it. Technical reports will be registered into arXiv.org. Published results will be made available at: http://www.cse.lehigh.edu/~palmieri/. The Github account for public code release is the following: "https://github.com/robertopalmieri/dev". This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.