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.

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