SHF: Small: Multicore Data-Structures: Relaxed, Flat, and Randomized

点击翻译按钮获取中文摘要

Most multicore data structures being designed and used in parallel software today are concurrent versions of the sequential data structures of years past. They continue to work reasonably well because the level of parallelism offered by mainstream multicore machines is still low. As machines grow in size, however, the limitations of these traditional structures will become clear: they have inherent sequential bottlenecks, require tight synchronization, and are not easily distributed. This project will develop new classes of parallel data structures that combine relaxed specifications with highly decentralized randomized implementations, overcoming the drawbacks of existing structures and providing a better fit with tomorrow's massively parallel many-core machine designs. This research will combine theoretical algorithmic work with empirical evaluation on real machines and applications, and will result in a library of concurrent data structures and a collection of design approaches and specification methodologies. Commercial software developers are in desperate need of data structures that scale while still remaining easy to understand and modify. Making this project's developed structures widely available will greatly help in making tomorrow's applications, whether they run on a cell phone or on a server in the cloud, make full use of the parallelism offered by multicore technology.