A Framework for Computation-Memory Algorithmic Optimization for Signal Processing

Abstract—The heterogeneity of today’s computing environment means computation-intensive signal processing algorithms must be optimized for performance in a machine dependent fashion. In this paper, we present a dynamic memory model and associ-ated optimization framework that finds a machine-dependent, near-optimal implementation of an algorithm by exploiting the computation-memory tradeoff. By optimal, we mean an imple-mentation that has the fastest running time given the specification of the machine memory hierarchy. We discuss two instantiations of the framework: fast IP address lookup, and fast nonuniform scalar quantizer and unstructured vector quantizer encoding. Experiments show that both instantiations outperform techniques that ignore this computation-memory tradeoff. Index Terms—Computation theory, memory management, packet switching, signal processing, vector quantization. I