Return to search

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

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.

Identiferoai:union.ndltd.org:tamu.edu/oai:repository.tamu.edu:1969.1/85790
Date10 October 2008
CreatorsCobb, Jeffrey Lee
ContributorsKhatri, Sunil P.
PublisherTexas A&M University
Source SetsTexas A and M University
Languageen_US
Detected LanguageEnglish
TypeBook, Thesis, Electronic Thesis, text
Formatelectronic, born digital

Page generated in 0.0019 seconds