Communication Locality in Computation: Software, Chip Multiprocessors and Brains

Dr Daniel Greenfield, one of my Ph.D. students, obtained the BCS Distinguished Dissertation in Computer Science in 2011. He received the award on 1st November 2011 at the Royal Society.

Abstract

This thesis argues that it is the communication costs of algorithms, rather than their computation costs, that will dominate future computing concerns. That, as we move to thousands of cores on a chip, the physical spatial locality of computation and data becomes critical to performance and cost. However, there is very little in the way of theory, models, or even characterisation of such locality for Chip-Multiprocessors (CMP). This thesis adapts and extends the existing theory and models of wire locality in VLSI circuits to the physical and temporal locality of software running on CMPs. It aims to provide a new foundation for characterising, modelling, predicting and exploiting the communication properties of software, which as we show, exhibits Rentian fractal scaling. In doing so, it lays a new communication-centric foundation for CMP software and hardware, and provides fundamental insights into their continued technological scaling.

Electronic Copy

Here is a PDF copy of the thesis.