Department of Computer Science and Technology

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}
}