Integrating program transformations in the memory-based synthesis of image and video algorithms
David J. Kolson, Alexandru Eugen Nicolau, Nikil D. Dutt · 1994
In this paper we discuss the interaction and integration of two important program transformations in high-level synthesis---Tree Height Reduction and Redundant Memory-access Elimination. Intuitively, these program transformations do not interfere with one another as they optimize different operations in the program graph and different resources in the synthesized system. However, we demonstrate that integration of the two tasks is necessary to better utilize available resources. Our approach involves the use of a "meta-transformation" to guide transformation application as possibilities arise. Results observed on several image and video benchmarks demonstrate that transformation integration increases performance through better resource utilization. 1 Introduction Tree height reduction (THR) [1, 12] is a well-known technique for reducing the critical path length and increasing the parallelism of expressions and/or recurrences through the introduction of redundant computation. THR has ...