Communication Locality in Computation

Software, Chip Multiprocessors and Brains

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.