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.
| Identifer | oai:union.ndltd.org:tamu.edu/oai:repository.tamu.edu:1969.1/ETD-TAMU-2023 |
| Date | 15 May 2009 |
| Creators | Cobb, Jeffrey Lee |
| Contributors | Khatri, Sunil P. |
| Source Sets | Texas A and M University |
| Language | en_US |
| Detected Language | English |
| Type | Book, Thesis, Electronic Thesis, text |
| Format | electronic, application/pdf, born digital |
Page generated in 0.0025 seconds