An attribute grammar based framework for machine-dependent computational optimization of media processing algorithms

Media processing algorithms are typically computationally intensive, and in complexity constrained environments, finding the most computationally efficient algorithm is critical. In this paper, we present an attribute grammar based framework which captures the computational complexity of an algorithm in a machine-dependent manner. Using this formalism, a media processing algorithm can be optimally and automatically tuned to a particular machine by a problem specific optimizer. Moreover, the tradeoff between performance and execution time on a specific machine can be controlled and thus exploited to optimize overall performance. To illustrate the viability of our approach, we applied it to the variable-length code (VLC) decoding problem and show that the optimal VLC decoding algorithm can be found using the framework. Tradeoff between coding efficiency and decoding speed of Huffman code can be exploited by employing length-limited code.