Technical reports
Scaling Mount Concurrency: scalability and progress in concurrent algorithms
Chris J. Purcell
August 2007, 155 pages
This technical report is based on a dissertation submitted July 2007 by the author for the degree of Doctor of Philosophy to the University of Cambridge, Trinity College.
DOI: 10.48456/tr-697
Abstract
As processor speeds plateau, chip manufacturers are turning to multi-processor and multi-core designs to increase performance. As the number of simultaneous threads grows, Amdahl’s Law means the performance of programs becomes limited by the cost that does not scale: communication, via the memory subsystem. Algorithm design is critical in minimizing these costs.
In this dissertation, I first show that existing instruction set architectures must be extended to allow general scalable algorithms to be built. Since it is impractical to entirely abandon existing hardware, I then present a reasonably scalable implementation of a map built on the widely-available compare-and-swap primitive, which outperforms existing algorithms for a range of usages.
Thirdly, I introduce a new primitive operation, and show that it provides efficient and scalable solutions to several problems before proving that it satisfies strong theoretical properties. Finally, I outline possible hardware implementations of the primitive with different properties and costs, and present results from a hardware evaluation, demonstrating that the new primitive can provide good practical performance.
Full text
PDF (1.0 MB)
BibTeX record
@TechReport{UCAM-CL-TR-697, author = {Purcell, Chris J.}, title = {{Scaling Mount Concurrency: scalability and progress in concurrent algorithms}}, year = 2007, month = aug, url = {https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-697.pdf}, institution = {University of Cambridge, Computer Laboratory}, doi = {10.48456/tr-697}, number = {UCAM-CL-TR-697} }