| With VLSI fabrication entering the deep sub-micron (DSM) era, devices are scaled down to smaller sizes, clocks are running at higher frequencies, and more functions are integrated into one chip. As a result, coupling effect between neighboring wires is increasing, and signal switching on one wire produces noise on the other wire. This phenomenon is called crosstalk . Another result of increasing frequency and density is the increasing power dissipation.; In this dissertation, we studied several major CAD problems for crosstalk and power reduction, namely crosstalk-driven routing, low power gate decomposition, low power floorplanning, and multi-objective buffered maze routing.; In crosstalk-driven routing, we first consider river routing where only one layer is available. We establish a relationship between crosstalk reduction and space allocation. Based on this relationship, a polynomial time network-flow based algorithm is designed to construct an optimal solution. We then consider crosstalk control in maze routing which is a general routing technique. We give the complexity result and design an algorithm which is based on Lagrangian relaxation. We also consider crosstalk reduction in global routing. To enable crosstalk estimation, simple layer and track assignments are included in the routing. A multi-stage global router is designed to construct a crosstalk-feasible solution in such a model.; For power reduction, we first consider low power gate decomposition where a multiple input gate is decomposed into a tree of two-input gates. In the case of AND/OR gate, we first prove many properties for an optimal decomposition. Based on these properties, we design an exact algorithm which is the fastest in the literature and a heuristic algorithm which outperforms known heuristics. In the case of XOR gate, we give polynomial algorithms to construct optimal decompositions. We then consider the problem of cell selection in a slicing floorplan to minimize power dissipation under area constraint. We characterize the complexity of the problem and give pseudo-polynomial time algorithms for it. We also consider the problem of simultaneous routing and buffer insertion which forbids buffer insertions over macro blocks. We design algorithms for this problem where the objectives include power, delay, and congestion. |
