| In VLSI process technology with process geometries greater than one micron, gate and transistor delays dominated interconnect delays. In ultra deep submicron (UDSM) design (i.e., 0.25 μm and below), parasitic capacitance and resistance effects begin to dominate. The increased coupling capacitance between adjacent interconnect wires increases delay times and may cause failures due to noise injection. In UDSM design, capacitances can no longer be extracted in a two-dimensional (2-D) or 2.5-D context. For multi-layer interconnect optimization to avoid signal integrity problems, very fast and accurate 3-D capacitance extraction is essential. Numerical methods are usually employed for accurate 3-D capacitance extraction. However, they are known to be extremely memory and time consuming.; Parallel processing provides one solution to reduce the running time and address the memory shortage problems in capacitance extraction. In this dissertation, we study the parallel formulations of typical capacitance extraction methods, on distributed memory multiprocessors. This includes the best known fast multipole accelerated FASTCAP, and another widely used Boundary Element Method (BEM). We examine the partitioning and load balancing approaches of each method. We report detailed comparison results on networks of scientific workstations, connected through standard communication links such as Ethernet and ATM, in addition to an IBM SP2.; The capacitance extraction during iterative performance-driven layout design must be very fast and accurate in order to meet timing closure in as less number of iterations as possible. Traditional batch model capacitance extraction can not handle the task due to the inability to response successive small design changes in such an iterative design methodology. In this dissertation, we address this problem by introducing the concept of incremental 3-D capacitance extraction and developing efficient incremental algorithms. We demonstrate its application in an iterative timing-driven multilayer detailed routing. In such a routing approach with aggressive performance goals, the incremental extraction can provide the most accurate 3-D parasitic capacitance information for timing optimization, without compromising CPU time. More important, with accurate delay estimation based on 3-D extraction, an iterative design methodology will be able to reach timing closure much faster in reduced design iterations. |
