| As integrated-circuit (IC) technology continues to shift towards the deep-submicron (DSM) regime---stimulated by the increasing drive towards higher operating frequency, greater system complexity, and less power requirement---a host of new challenges for present-day computer-aided design (CAD) presents itself. Interconnect performance has become as important as transistor performance, as a major factor limiting electrical-switching speed. IC interconnects, themselves, require significant chip area, they contribute to overall propagation delay, and they consume significant amounts of power. A key objective in moderns high-end digital-interconnect design is reducing propagation delay due to parasitic capacitance and resistance. The primary aim of this Thesis, consequently, is the creation of an efficient, fully parallel algorithm for the electrical analysis of RC interconnects.;Chip designers must use sophisticated CAD software to model massively coupled digital-IC interconnects. Fundamentally, improving process technology requires the use of increasingly powerful CAD software. In addition, conventional deterministic numerical methods for the electrical analysis of interconnects lack what, we believe, is the necessary computational efficiency for future gigascale digital integration.;This Thesis concerns the creation of an arbitrary-order algorithm for extracting RC-interconnect impulse-response (IR) moments. Our motivation stems from a previously developed Sum-over-Paths (SoP) algorithm, for fixed, low-order moment extraction. Here, however, we, for the first time, employ symbolic analysis to define an arbitrary-order stochastic algorithm. Note, too, our new algorithm preserves full parallelism---a critical requirement in complex IC-interconnect applications. Our algorithm allows us to effectively construct the circuit transfer function to arbitrary order of Laplace transform variable s.;We have successfully coded and preliminary tested our algorithm on 3-, 5-, and 10-stage example RC networks. We used a 2.16-GHz Intel Core-Duo ProcessorRTM with the GCC v. 2.4.1 compiler. In addition, a large, 20-stage RC-line benchmark problem was studied to further explore the performance of our stochastic algorithm. For output taken at the final stage, we achieved an absolute error of approximately 0.015%, after 1G statistical samples. All moments m 0 through m20 were obtained in less than 20 minutes per moment order.;Based on our Thesis results, we suggest that multi-line coupling, including inductance, as an important next step for future research.;This work was supported by the Interconnect Focus Center, one of the Semiconductor Research Corporation/DARPA Focus Centers. This work, as well, was supported by the New York State Office of Science, Technology, and Academic Research (NYSTAR). |
