Cobb, Jeffrey Lee (2007-12). A robust window-based multi-node minimization technique using Boolean relations. Master's Thesis. Thesis uri icon

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.
  • 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.

publication date

  • December 2007