A robust window-based multi-node minimization technique using Boolean relations

Abstract

Multi-node optimization using Boolean relations is a powerful approach for network minimization. The approach has been studied in theory, and so far its superiority over single node optimization techniques has only been conjectured for practical designs. This is due to the highly memory intensive computations involved in the calculation of Boolean relations representing the multi-node optimization exibility. In this thesis, an algorithm to perform Boolean relation-based multi-node optimization using a robust, fast and memory efcient algorithm is presented. In particular, two nodes are simultaneously optimized at a time. Results are reported on large designs, demonstrating the initial power of this multi-node optimization algorithm. The robustness of the approach arises from the use of a window-based technique for computing these Boolean relations. Secondly, aggressive early quantication is performed during the computation, keeping memory utilization low. Finally, smart heuristics are employed for selecting the node pair to be optimized simultaneously. These features allow the approach to scale well and provide good results for large designs. Experiments are performed on a set of large benchmarks and the algorithm's performance is compared to a SAT-based network optimization technique using complete don't cares. On average, the approach presented in this thesis achieves a 12% reduction in literal count across all the large designs compared to the complete don't cares, while maintaining small runtimes and low memory usage.