CSR: Small: Design and Optimization of Scalable Concurrent Data Structures for Multi-Core Systems

University Of Texas At Dallas, Richardson TX

Investigators

Abstract

In the last decade, major general-purpose processor manufacturers have turned to hyper-threading and multi-core architectures to improve hardware performance since many of the traditional approaches for boosting CPU performance have hit a "Brick Wall". Hyper-threading is about running two or more threads in parallel inside a single CPU. Multi-core is about running two or more actual CPUs on one chip. This multi-core revolution that is currently underway has now moved from general-purpose computing devices such as desktops, laptops and workstations to other more specialized computing devices such as smartphones, tablets, gaming devices, routers and even smartwatches. Unfortunately, most current software applications will not benefit from this enormous parallel processing power offered by a modern computing device unless they are rewritten in a way that enables a program to distribute its tasks across several cores. The future software applications will have to be multi-threaded to achieve any performance gains. A data structure is a fundamental building block of any software program. It is used to manage access to application data and is designed to support specific operations efficiently. In a multi-threaded program, several threads may need to share data and manipulate it concurrently. This gives rise to the problem of designing and building concurrent data structures in which several threads can access the data and manipulate the data structure at the same time, and whose performance scales well with the number of cores. Such high performance concurrent data structures are key to writing multi-threaded programs that scale well with the ever increasing number of cores. In this project, the researcher will develop new techniques for managing contention among concurrent operations that reduce contention window, lower memory footprint, reduce cache traffic and/or decrease traversal overhead. These techniques will be used to develop concurrent version of important data structures suitable for multi-core systems that scale well with the number of cores. The proposed research has the potential of benefiting many areas in computer science and beyond including operating systems, databases, programming languages, game engines and parallel and scientific applications. The PI teaches graduate courses on operating systems and multi-core systems on a regular basis as well as research-oriented seminar courses from time to time. The PI will incorporate many of the results developed during this investigation into graduate courses.