In VLSI circuits, signal delays play an important role in design, timing verification and signal integrity checks. These delays are attributed to the presence of parasitic resistance, capacitance and inductance. With increasing clock speed and reducing feature sizes, these delays will be dominated by parasitic inductance. In the next generation VLSI circuits, with more than millions of components and interconnect segments, fast and accurate inductance estimation becomes a crucial step. A generalized approach for inductance extraction requires the solution of a large, dense, complex linear system that models mutual inductive effects among circuit elements. Iterative methods are used to solve the system without explicit computation of the system matrix itself. Fast hierarchical techniques are used to compute approximate matrix-vector products with the dense system matrix in a matrix-free way. Due to unavailability of system matrix, constructing a preconditioner to accelerate the convergence of the iterative method becomes a challenging task. This work presents a class of parallel algorithms for fast and accurate inductance extraction of VLSI circuits. We use the solenoidal basis approach that converts the linear system into a reduced system. The reduced system of equations is solved by a preconditioned iterative solver that uses fast hierarchical methods to compute products with the dense coefficient matrix. A Green’s function based preconditioner is proposed that achieves near-optimal convergence rates in several cases. By formulating the preconditioner as a dense matrix similar to the coefficient matrix, we are able to use fast hierarchical methods for the preconditioning step as well. Experiments on a number of benchmark problems highlight the efficient preconditioning scheme and its advantages over FastHenry. To further reduce the solution time of the software, we have developed a parallel implementation. The parallel software package is capable of analyzing interconnects con- figurations involving several conductors within reasonable time. A two-tier parallelization scheme enables mixed mode parallelization, which uses both OpenMP and MPI directives. The parallel performance of the software is demonstrated through experiments on the IBM p690 and AMD Linux clusters. These experiments highlight the portability and efficiency of the software on multiprocessors with shared, distributed, and distributed-shared memory architectures.

Thesis (MScEng)--Stellenbosch University, 2011. / ENGLISH ABSTRACT: Rapid Single Flux Quantum (RSFQ) cells are key in the design of complex and applicable RSFQ electronic circuits. These cells are low-level circuit elements that are used repeatedly to build larger, applicable RSFQ circuitry. Making these cells simple to layout and manufacture, but reliable for extensive use demands a careful development process for RSFQ cells. Cell functionality is verified through simulations, thereafter the cell is laid out in special software packages. Inductance of on-chip superconductor structures is extracted through careful modelling with numerical field solver software. A cell library has been developed by incorporating existing or published cells after further analysis and optimization, as well as developing new cells. Cells that have been adapted into the library include the Josephson transmission line (JTL), Splitter, Merger, D-Flip Flop (DFF), T-Flip Flop (TFF), NOT, AND, OR and XOR, DC-SFQ and SFQ-DC and PTL Driver and Receivers. New cells include NOR, NAND and XNOR. The cells were designed for the IPHT’s RSFQ1D 1kA/cmª and Hypres’ 4.5kA/cmª processes. The cells in the library have good bias current operating margins obtained through simulations (> ±26%). All cells have all the parameters listed in the thesis including extracted inductance values. In order to have a complete and verified RSFQ cell library, cells have been sent for fabrication at IPHT and Hypres facilities. These cells can now be tested on-chip, in the laboratory, to establish functionality and practical bias current margins. All test signal patterns and bias currents required for testing are defined to allow co-workers or collaborators to test the cells. / AFRIKAANSE OPSOMMING: "Rapid Single Flux Quantum" (RSFQ) selle is van sleutelbelang in die ontwerp van komplekse en toepaslike RSFQ elektroniese stroombane. Hierdie selle is laevlak stroombaanelemente wat herhaaldelik gebruik word om groter RSFQ bane mee te bou. Versigtige ontwikkeling is nodig om hierdie selle eenvoudig vir uitleg en vervaardiging te hou terwyl dit ook betroubaar is vir wye gebruik. Selfunksionaliteit word geverifieer deur middel van simulasies, waarna selle vir vervaardiging uitgelê word in spesiale sagtewarepakette. Induktansie van supergeleierstrukture op vervaardigde skyfies word deur versigtige modellering met behulp van numeriese veldoplossingsagteware onttrek. In hierdie tesis is ’n selbiblioteek ontwerp deur bestaande (gepubliseerde) selle verder te analiseer en optimeer, en deur nuwe selle te ontwerp om die biblioteek volledig te maak. Selle wat aangepas is vir hierdie biblioteek sluit die Josephson-Transmissielyn (JTL), Verdeler, Samevoeger, DWipkring (DFF), T-Wipkring (TFF), NIE, EN, OF en XOF, asook die DC-SFQ en SFQ-DC selle en Passiewe Transmissielyn (PTL) drywers en ontvangers in. Nuwe selle sluit die NOF, NEN en XNOF hekke in. Die selle is ontwerp en uitgelˆe vir beide IPHT se RSFQ1D 1kA/cmª en Hypres se4.5kA/cmª prosesse. Die selle in die biblioteek toon goeie voorspanningstroom-werksmarges, soos verkry deur simulasie (> ±26%). Parameters en berekende induktansies vir alle selle word in die tesis gelys vir naslaandoeleindes. Vir die daarstel van ’n volledige en geverifieerde RSFQ selbiblioteek is selontwerpe vir vervaardiging na IPHT en Hypres gestuur. Aangesien vervaardiging slegs een maal per jaar by IPHT gedoen word, is die skyfies egter nog nie beskikbaar nie. Na vervaardiging kan die skyfies egter getoets word om selfunksionaliteit in die laboratorium te meet. Ten einde hierdie toetsing vir enige medewerker te vergemaklik, word alle toetsparameters soos voorspanningstroom en intreeseinpatrone in die tesis gedefinieer.