New Mathematics for Computer Performance: Array Algebra and Cost Functions

MoA (mathematics of arrays) is a theory of parallel operations on arrays that can describe all known algorithms in linear algebra, signal processing, and HPC because they are based on primitive recursion and array shapes. Mapping parallel algorithms to computer architectures remains more of an art than a science, and specific mathematical techniques are needed to provide a basis for performance evaluation at a level abstract enough to constitute an experimental science. In this paper we present a methodology for parallel code generation from MoA expressions. Then, we relate the MoA operators to the linear space of memory elements in computer architecture. Finally, we define a theory of execution costs that is based on classical operations research and is formally related to MoA-based parallel code generation. This constitutes a formalized and mechanizable approach to performance prediction, portability and optimization.