Sparsity is fundamental to the design of efficient algorithms across a vast range of applications – but sparsity makes performance optimisation harder – and the issue is primarily locality. This talk reflects on our experience with many applications, notably in DSLs for solving PDEs, but also in robotics and vision– specifically looking at how to automate data locality optimisation. We will look at what techniques we have, what we know about characteristics of tractable problems, and tough ones. We need to compute efficiently with a compact representation of where our data is and where it is used – and we want to amortise this cost. When we succeed we deliver real value to users, by supporting composition and abstraction.

Biography: Paul Kelly leads the Software Performance Optimisation group at Imperial College London. His research focus is domain-specific program optimisation, leading to close engagement with colleagues in computational science, robotics and computer vision. This talk covers joint work with many such collaborators,