Optimization techniques for arithmetic expressions
Ryan Kastner, Anup Hosangadi · 2006
The increasing complexity of systems has spawned new directions in Design Automation research. System designers need the most sophisticated tools that can design applications of ever increasing complexity and meet the stringent requirements of performance and power consumption. Most of the popular embedded system applications perform some kind of continuous numeric processing which are computationally intensive. Examples of such computing can be found in multimedia applications such as 3-D computer graphics, audio and video processing and wireless communication applications. Traditionally system designers have often used hand written library routines for implementing these functions in software and custom Intellectual Property (IP) cores for hardware. Such an approach often does not give the best results since the results depend on the target architectures and the implementation constraints that are not taken into account in these libraries. Unfortunately, the currently available software compilers and high level synthesis frameworks have been designed for general purpose applications and do not do a good optimization of arithmetic expressions. As a result, there is an urgent need to come up with good tools that can take advantage of the flexibility of arithmetic expressions and provide the best solutions for their implementations. These methods then need to be integrated into the conventional optimization frameworks for software and/or hardware. This thesis highlights the opportunities available for the optimization of arithmetic expressions, and presents algebraic techniques for their optimization. The heart of these techniques is based on a novel canonical representation and methodology for eliminating redundant operations in arithmetic expressions. These techniques were applied for optimizing arithmetic functions in a number of popular applications, where significant performance, power and area savings were observed over the conventional techniques. This thesis also highlights the various factors that affect the delay and power consumption of these arithmetic expressions, and discusses some solutions that give the best result. Furthermore, the challenges of verifying the precision and range of these computations and their relationship with the various optimizations are studied.