Potential-driven statistical ordering of transformations

Successive, well organized application of transformations has been widely recognized as an exceptionally effective, but complex and difficult CAD task. We introduce a new potential-driven statistical approach for ordering transformations. Two new synthesis ideas are the backbone of the approach. The first idea is to quantify the characteristics of all transformations and the relationship be-tween them based on their potential to reorganize a computation such that the complexity of the corresponding implementation is reduced. The second one is based on the observation that transfor-mations may disable each other not only because they prevent the application of the other transformation, but also because both trans-formations target the same potential of the computation. These two observations drastically reduce the search space to find efficient and effective scripts for ordering transformations. A key algorithmic novelty is that both conceptual and optimization insights as well as all optimization algorithms are automatically derived by organized experimentation and statistical methods. On a large set of diverse real-life examples improvements in throughput, area, and power by large factors have been obtained. Both qualitative and quantitative statistical analysis indicate effectiveness, high robustness, and con-sistency of the new approach for ordering transformations