An algebraic approach to computer program design and memory management

Beginning with an algebra of multi-dimensional arrays and following a set of reduction rules embodying a calculus of array indices, we translate (in a mechanizable way) from the high-level mathematics of any array-based problem and a machine specification to a mathematically-optimized implementation. Raynolds and Mullin introduced the name \it{Conformal Computing}\,${}^\star$\rm \ to describe this process that will be discussed in the context of data transforms such as the Fast Fourier, Wavelet Transforms and QR decomposition. We discuss the discovery that the access patterns of the Wavelet Transform form a sufficiently regular subset of those for our cache-optimized FFT so that we can be assured of achieving similar efficiency improvements to the Wavelet Transform as those that were found for the FFT. We present recent results in which careful attention to reproducible computational experiments in a dedicated/non-shared environment is demonstrated to be essential in order to optimally \it{measure} \rm the response of the \it{system} \rm (in this case the computer itself is the object of study) so as to be able to optimally tune the algorithm to the numerous cost functions associated with all of the elements of the memory/disk/network hierarchy. ${}^\star$ The name Conformal Computing is protected: \copyright ~2003, The Research Foundation, State University of New York.