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.