| The success of logic synthesis systems depends upon the ability to estimate area and delay during the logic optimization process. As technology goes under sub-quarter micron feature size, wire delays dominate gate delays. Many iterations between logic synthesis and layout synthesis (placement and routing) are required to meet design timing specifications, and still convergence is hard to achieve. Pseudo-Symmetric Binary Decision Diagrams (PSBDDs), a layout-driven, logic-synthesis approach, have been proposed as a possible solution to this problem. This regular two-dimensional logic structure can be directly mapped to physical layout, practically, without any placement or routing. Therefore, the quality loss in case of highly optimized netlists that fit badly onto the target architecture can be avoided by using PSBDDs. Additionally, all paths in a PSBDD have the same delay and, therefore, PSBDDs have already been successfully applied to wave pipelining. Similarly to BDDs, PSBDDs suffer from a variable ordering problem, the size and level of PSBDD can grow exponentially if the variable order is not appropriate.; In this dissertation, we present a complete design methodology to synthesize PSBDDs. At first, we introduce a novel global approach to the variable ordering problem in PSBDDs. It is based on analyzing symmetric relationships between functions' variables. In addition to widely used classical symmetries, extended symmetries are heavily used in the ordering heuristics and are shown to be very useful. Next, to further reduce the size and the number of levels in PSBDDs, we introduce a hierarchical disjoint-support decomposition method that is based on multiple symmetries and serves as a preprocessor to the PSBDD generation algorithm. The PSBDD can be used as layout generators for ASICs, and for mapping to fine-grain, multiplexer-based FPGAs. FPGA architecture based on PSBDDs is another example of a possible application of this work.; Experimental results on a set of MCNC benchmarks show that, comparing to the previously published results, we have substantially reduced the number of levels (delay) in PSBDDs. In addition, for many non-symmetric benchmark functions, we have found solutions with the minimum number of levels equal to the number of primary input variables. |
