Routing plays an important role in determining the total circuit area and circuit performance and hence must be addressed as early as possible during the design process. In this paper, an effective routing-driven approach for technology-dependent logic synthesis, which relies on alphabetic tree construction, is presented. Alphabetic trees are trees generated under the restriction that the initial order on the leaf nodes is maintained while not introducing any internal edge crossing. First, a mechanism for generating all alphabetic trees on a given number of leaf nodes is presented. Next, the number of such trees is calculated under different height and degree restriction and used to derive upper bounds on the complexity of alphabetic tree optimization problem. A classification of tree cost functions, for which alphabetic trees can be generated in polynomial time, is also proposed. Specifically, alphabetic tree optimization algorithms are applied to generate optimal alphabetic fan-out trees. For fan-out optimization, we obtained 14% improvement in chip area at the cost of 1% loss in performance.

This paper presents a delay-optimal clustering algorithm for minimizing the power dissipation in a very large scale integration (VLSI) circuit. Traditional approaches for delay-optimal clustering are based on Lawler's clustering algorithm which makes no attempt to explore alternative clustering solutions that have the same delay but lower power implementations. Our algorithm implicitly enumerates alternate clusterings and selects a clustering solution which has the same delay, but the lowest power dissipation. For tree circuits, the proposed algorithm produces delay- and power-optimal clustering, whereas for nontree circuits it produces delay-optimal clustering with significantly reduced power dissipation. The proposed mechanism can be used to generate power minimized clusters for various applications such as preprocessing designs for partitioning, clustering logic during synthesis, etc. The mechanism can also be deployed hierarchically to generate circuit partitioning solutions directly.

We propose a novel technique for post-layout delay optimization. This technique identifies the Boolean space corresponding to late arriving transitions at the outputs of delay-critical subcircuits within the given circuit. The transitions are eliminated from the outputs by implementing the corresponding logic separately and merging them with the original circuit through some control logic. Experimental results suggest that this technique can speed up circuits even when the circuits have already been optimized for delay to the fullest extent.

This paper describes techniques for reducing the routing cost during logic extraction. Two routing cost functions derived from the global structure of a boolean network are analyzed and the effectiveness of each cost function is compared against the conventional literal savings cost function. Experimental results obtained with these routing cost functions are presented and discussed in detail.

In this paper, a delay optimal clustering/partitioning algorithm for minimizing the power dissipation of a circuit is proposed. Traditional approaches for delay optimal partitioning are based on Lawler's clustering algorithm that makes no attempt to explore alternative partitioning solutions that have the same delay but better power implementations. Our algorithm provides a formal mechanism which implicitly enumerates alternate partitionings and selects a partitioning that has the same delay but less power dissipation. For tree circuits, the proposed algorithm produces delay and power optimal partitioning whereas for non-tree circuits it produces delay optimal partitioning with significantly improved power dissipation.

We present a cost function which can be used to minimize the routing contribution of a circuit during logic synthesis. Instead of estimating the absolute routing cost of a net, this function captures the relative routing costs of nets based on the number of terminals on the nets. Unlike the routing cost functions proposed earlier, the proposed cost function does not require layout-parameters or any tuning of the variables to achieve acceptable estimation of the routing cost. The usefulness of the proposed routing cost is verified by minimizing it during the process of logic extraction in logic synthesis, leading to an average of 10% improvement in the routing area and 8% improvement in the chip area at no performance loss.

In this paper, we propose an efficient fanout optimization algorithm which improves circuit performance while honoring an order restriction on the fanouts. This order is derived from a companion placement of mapped circuit. By honoring the placement order we generate fanout trees that are free of internal edge crossings, resulting in improved routing and chip area. Our O(n/sup 3/) procedure which is based on an algorithm for constructing optimal alphabetic codes, is optimal for binary trees with monotone tree cost function. For nonbinary trees, we propose a set of rules which reduce size of the solution space while maintaining the optimality. We obtained an average of 14% improvement in chip area without a significant performance degradation as compared to the SIS fanout optimization tool.