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

在过去的十年中，主要的通用处理器制造商已经转向超线程和多核架构来提高硬件性能，因为许多传统的提高CPU性能的方法都遇到了“砖墙”。 超线程是关于在一个CPU中并行运行两个或多个线程。多核是指在一个芯片上运行两个或多个实际的CPU。目前正在进行的这场多核革命现在已经从台式机、笔记本电脑和工作站等通用计算设备转移到其他更专业的计算设备，如智能手机、平板电脑、游戏设备、路由器甚至智能手表。不幸的是，大多数当前的软件应用程序将不会从现代计算设备提供的这种巨大的并行处理能力中受益，除非它们以使得程序能够将其任务分布在多个核上的方式被重写。 未来的软件应用程序必须是多线程的，以实现任何性能增益。数据结构是任何软件程序的基本构建块。它用于管理对应用程序数据的访问，旨在有效地支持特定操作。在多线程程序中，多个线程可能需要共享数据并并发操作数据。 这就产生了设计和构建并发数据结构的问题，其中多个线程可以同时访问数据和操作数据结构，并且其性能随核的数量而扩展。这种高性能的并发数据结构是编写多线程程序的关键，这些程序可以随着不断增加的内核数量而很好地扩展。在这个项目中，研究人员将开发新的技术来管理并发操作之间的竞争，减少竞争窗口，降低内存占用，减少缓存流量和/或减少遍历开销。这些技术将用于开发适用于多核系统的重要数据结构的并发版本，这些数据结构可以随核数的增加而扩展。拟议的研究有可能使计算机科学的许多领域受益，包括操作系统，数据库，编程语言，游戏引擎以及并行和科学应用。PI定期教授操作系统和多核系统的研究生课程，以及不时以研究为导向的研讨会课程。PI将把这次调查过程中开发的许多结果纳入研究生课程。

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 singleCPU. 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.