Open Collections

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Implementation of algorithms to determine the capacitance sensitivity of interconnect parasitics in the.. Huang, Nick Kuan-Hsiang 2009-12-31

You don't seem to have a PDF reader installed, try download the pdf

Item Metadata

Download

Media
[if-you-see-this-DO-NOT-CLICK]
ubc_2009_fall_Huang_Nick.pdf [ 3.06MB ]
Metadata
JSON: 1.0067690.json
JSON-LD: 1.0067690+ld.json
RDF/XML (Pretty): 1.0067690.xml
RDF/JSON: 1.0067690+rdf.json
Turtle: 1.0067690+rdf-turtle.txt
N-Triples: 1.0067690+rdf-ntriples.txt
Original Record: 1.0067690 +original-record.json
Full Text
1.0067690.txt
Citation
1.0067690.ris

Full Text

Implementationof Algorithms to DeterminetheCapacitanceSensitivity of InterconnectParasiticsinthe MagicVLSI Layout ToolbyNick Kuan-HsiangHuangB.A.Sc.,The University of BritishColumbia, 2007A THESISSUBMITTEDIN PARTIAL FULFILLMENTOFTHE REQUIREMENTSFOR THE DEGREEOFMASTEROF APPLIEDSCIENCEinThe Collegeof GraduateStudies(ElectricalEngineering)THE UNIVERSITYOF BRITISHCOLUMBIA(Okanagan)September 2009c©Nick Kuan-HsiangHuang,2009AbstractVLSIinterconnectcapacitanceis becomingmoresignificant and also increasinglysubject toprocess variationin the deep submicronregime. A new set of capacitancemodels is imple-mented in the Magic VLSI layout tool to improve the capacitanceaccuracybased on 2.5Dcapacitancemodels. This involves a new technologyfile, equations,and search algorithms.Inaddition,a simpletechniquetoextractfromlayoutthesensitivityofinterconnectparasiticcapacitanceto linewidthprocess variationis proposedbasedon the newcapacitancemodelsand implemented in Magic. The derivative of each extracted capacitancewith respect tolinewidthvariation in every level is obtained. Coincident edges in layout result in distinct“shrinking”and “bloating”derivatives. The derivatives thereforeform a gradient that maybe multipliedby a vectorof the variationson each level to give the totalexpecteddeviationfrom nominal capacitance. The gradient allows the process sensitivity of each capacitanceto be determinedby simply inspecting the netlist. In the end, the impactof process varia-tion is simulated in a crosstalkapplicationto emphasizethe necessity of process variationawareness.iiTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiiList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ixList of Acronyms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiiAcknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiv1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1 Motivation................................. 11.2 Research Goals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.3 ThesisOrganization . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 Background and Relevant Work . . . . . . . . . . . . . . . . . . . . . . . 52.1 InterconnectDesignTheory . . . . . . . . . . . . . . . . . . . . . . 62.1.1 Deep-Submicron Interconnect. . . . . . . . . . . . . . . . . 62.1.2 ParasiticResistance. . . . . . . . . . . . . . . . . . . . . . . 72.1.3 ParasiticCapacitance. . . . . . . . . . . . . . . . . . . . . . 8iiiTable of Contents2.1.4 Inductance . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112.2 CapacitanceExtraction ......................... 132.2.1 AnalyticalFormulae. . . . . . . . . . . . . . . . . . . . . . . 132.2.2 Field Solver ............................ 152.2.2.1 RandomWalk Method ............... 152.2.2.2 Volume-BasedMethod ............... 172.2.2.3 Surface-BasedMethod ............... 182.2.2.4 Field Solver Summary . . . . . . . . . . . . . . . . 212.2.3 Library Look-UpBasedMethod ............... 212.3 Commercial Parasitic Extraction . . . . . . . . . . . . . . . . . . . 222.3.1 Synopsys- Star-RCXT . . . . . . . . . . . . . . . . . . . . . 232.3.2 CadenceQRC Extraction ................... 232.3.3 Mentor Graphics- Calibre LFD ............... 252.3.4 Magma- QuickCap ....................... 252.3.5 Space 3D . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272.3.6 Industry Parasitic ExtractionSummary ........... 272.4 MagicTechnologyFiles for Look Up-BasedMethod . . . . . . . . 282.4.1 Stack File .............................282.4.2 Techgen ..............................293 ExistingCapacitanceExtractionModel of Magic . . . . . . . . . . . . 303.1 MagicDatabase..............................313.1.1 Geometry .............................313.1.1.1 Point . . . . . . . . . . . . . . . . . . . . . . . . . . 313.1.1.2 Rectangle ....................... 313.1.2 CornerStitched Tile . . . . . . . . . . . . . . . . . . . . . . 323.1.3 Plane ...............................343.1.3.1 Coverage . . . . . . . . . . . . . . . . . . . . . . . . 363.1.3.2 Strips. . . . . . . . . . . . . . . . . . . . . . . . . . 36ivTable of Contents3.1.3.3 Stitches ........................ 373.2 MagicTechnologyFile. . . . . . . . . . . . . . . . . . . . . . . . . . 383.2.1 Planes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 393.2.2 Contact . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 403.2.3 DRC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 413.2.3.1 Widthrules ...................... 413.2.3.2 Spacingrules ..................... 413.2.4 Extract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 423.2.4.1 Resistance. . . . . . . . . . . . . . . . . . . . . . . 453.3 MagicCapacitanceExtraction ..................... 453.3.1 Overlap CapacitanceExtraction . . . . . . . . . . . . . . . 463.3.2 Sidewall CapacitanceExtraction . . . . . . . . . . . . . . . 473.3.3 Sidewall Overlap CapacitanceExtraction .......... 493.3.4 Substrate CapacitanceExtraction .............. 503.4 MagicExtractionOutput ........................ 513.4.1 ExtractionFile .......................... 523.4.2 SimulationFile.......................... 533.5 Summary .................................534 Integrationof New Capacitive Model into Magic . . . . . . . . . . . . 554.1 CUP models................................554.1.1 Area Capacitance ........................ 564.1.2 LateralCapacitance. . . . . . . . . . . . . . . . . . . . . . . 584.1.3 Fringe Capacitance ....................... 614.1.4 Model Fit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 654.2 Changesto MagicFile Formats . . . . . . . . . . . . . . . . . . . . 664.2.1 TechnologyFile Changes . . . . . . . . . . . . . . . . . . . . 664.2.2 New ExtractionOutput .................... 664.3 LinewidthVariation ........................... 67vTable of Contents4.4 AlgorithmsImplementation . . . . . . . . . . . . . . . . . . . . . . 694.4.1 Real Edges . . . . . . . . . . . . . . . . . . . . . . . . . . . . 704.4.2 Coincident Edges ........................ 704.4.3 Pixel-basedSearch Algorithms . . . . . . . . . . . . . . . . 724.5 Summary .................................755 Simulationand Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . 765.1 CapacitanceComparison ........................ 775.1.1 Space 3D - OptEM ....................... 785.1.2 CapacitanceComparison Results ............... 795.2 LinewidthProcess Variation Evaluation . . . . . . . . . . . . . . . 815.2.1 Crosstalk .............................815.2.1.1 Interconnect...................... 825.2.2 Crosstalk SimulationResults . . . . . . . . . . . . . . . . . 885.3 Runtime Analysis ............................ 905.4 Summary .................................936 Conclusionand Future Work . . . . . . . . . . . . . . . . . . . . . . . . 946.1 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 946.2 Interpretationof Results . . . . . . . . . . . . . . . . . . . . . . . . 946.3 Limitations ................................956.4 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 966.4.1 Process Variations. . . . . . . . . . . . . . . . . . . . . . . . 966.4.2 CapacitanceModels . . . . . . . . . . . . . . . . . . . . . . . 966.4.3 Accuracy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 976.4.4 Runtime. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98viTable of ContentsAppendices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105A Stack file . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106A.1 Create a Stack File............................106A.2 Stack Diagram ..............................107B MagicTile Search Algorithm . . . . . . . . . . . . . . . . . . . . . . . . 108C Area CapacitanceEdge Implementation . . . . . . . . . . . . . . . . . . 110D MagicTechnologyFile on Extraction . . . . . . . . . . . . . . . . . . . 112E MagicOutputFiles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118E.1 Ext File . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118E.2 Spice File . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119E.3 Final Spice File ..............................119F Model Fit to Field Solver . . . . . . . . . . . . . . . . . . . . . . . . . . 120G MagicCodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132G.1 Real and Coincident Edge Algorithms . . . . . . . . . . . . . . . . 132G.2 Pixel-BasedSearch Algorithms ....................140viiList of Tables2.1 Informationof Figure2.4 .............................102.2 Commercialextractionmethods .........................273.1 Planessection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 403.2 Contact section . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 403.3 DRC section . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 413.4 Extractsection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 433.5 Node output . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 523.6 Couplingcapacitanceoutput . . . . . . . . . . . . . . . . . . . . . . . . . . . 534.1 New technologyparameters ...........................674.2 Capacitancederivative array ...........................685.1 Capacitancecomparison .............................795.2 Extractedvs estimatedcapacitances . . . . . . . . . . . . . . . . . . . . . . 855.3 Runtime record . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92viiiList of Figures2.1 Resistance cross-sectionalarea reduction from 90 nm to 65 nm technologynodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82.2 Capacitanceconfigurationin a typical DSM technologywith 1.5 aspect ratio 82.3 Capacitancein old assumptionand DSM .................... 92.4 Interconnectvs gate delay . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112.5 Conductorwith a rectangularcross-section . . . . . . . . . . . . . . . . . . . 142.6 Samplerandomwalk method . . . . . . . . . . . . . . . . . . . . . . . . . . 162.7 Samplefinite element method (idealizationof a beam) . . . . . . . . . . . . 172.8 Overall flow of interconnectlibrarymodel ...................222.9 Star-RCXT’ssensitivity-basedextractionsolution ............... 242.10 CadenceQRC extraction’sadvanced capabilities ................252.11 QuickCap NX’s process variationsolution . . . . . . . . . . . . . . . . . . . 263.1 Point structure ..................................313.2 Rectanglestructure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323.3 Corner-stitching (Manhattanshape) . . . . . . . . . . . . . . . . . . . . . . . 323.4 Basic tile structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343.5 Coverage tile . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 363.6 Strips tile . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 373.7 Stitch tile . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 383.8 Tile search algorithmpseudocode . . . . . . . . . . . . . . . . . . . . . . . . 393.9 Sidewall technologyline description . . . . . . . . . . . . . . . . . . . . . . . 44ixList of Figures3.10 Overlap capacitance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 463.11 Sidewall capacitance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 473.12 Sidewall capacitancedetection . . . . . . . . . . . . . . . . . . . . . . . . . . 493.13 Sidewall overlap capacitance . . . . . . . . . . . . . . . . . . . . . . . . . . . 503.14 Substratecapacitance...............................514.1 Capacitanceconfiguration . . . . . . . . . . . . . . . . . . . . . . . . . . . . 574.2 Area capacitance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 574.3 Lateralcapacitance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 584.4 Lateralcapacitanceschematic ..........................604.5 Fringe capacitance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 624.6 Lateralcapacitancebetween two layers .....................634.7 Fringe capacitanceschematic...........................644.8 Linewidthvariation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 694.9 A samplelayout illustratingreal edges .....................704.10 A samplelayout illustratingcoincident edges ..................714.11 extRealEdge()functionpseudocode .......................734.12 Pixel-basedsearch algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 745.1 CAD flow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 775.2 Space 3D layout . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 785.3 Capacitancecomparisonbetween Space 3D, CUP, and Magic ......... 805.4 Crosstalkconfiguration ..............................825.5 Magic interconnectlayouts with nets A, C on metal 1, B on metal 2, and Don metal 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 835.6 Extractedvs estimatedarea and lateralcapacitances . . . . . . . . . . . . . 865.7 Extractedvs estimatedsubstratecapacitanceswith fringing . . . . . . . . . 875.8 Extractedvs estimatedfringe capacitances . . . . . . . . . . . . . . . . . . . 885.9 Extractedvs estimatedarea + fringe capacitances ............... 89xList of Figures5.10 Victimsignalswith and withoutprocess variation . . . . . . . . . . . . . . . 905.11 CPLDlayout ...................................915.12 Runtime analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92A.1 Metal configurationfrom the stack file . . . . . . . . . . . . . . . . . . . . . 107B.1 Magic tile search algorithm. . . . . . . . . . . . . . . . . . . . . . . . . . . . 108C.1 Area capacitanceedge computation .......................111F.1 Lateralcapacitanceon metal 1 per λ ......................121F.2 Lateralcapacitanceon metal 2 per λ ......................122F.3 Lateralcapacitanceon metal 3 per λ ......................123F.4 Fringe capacitancemetal 1 to metal 2 with substrateper λ ..........124F.5 Fringe capacitancemetal 1 to metal 3 with substrateper λ ..........125F.6 Fringe capacitancemetal 2 to metal 1 with metal 3 above per λ .......126F.7 Fringe capacitancemetal 2 to metal 1 with space above per λ ........127F.8 Fringe capacitancemetal 2 to metal 3 with substrateper λ ..........128F.9 Fringe capacitancemetal 2 to metal 3 with metal 1 below per λ .......129F.10 Fringe capacitancemetal 3 to metal 1 with space above per λ. ........130F.11 Fringe capacitancemetal 3 to metal 2 with space above per λ ........131xiList of Acronyms3D Three-DimensionalAMS Analog/Mixed-SignalASIC Application-specific IntegrationCircuitBEM Boundary-Element MethodCAD Computer-aided DesignCMP ChemicalMechanicalPolishingCPLD ComplexProgrammableLogic DeviceCPU Central ProcessingUnitDRC Design-Rule CheckDSM Deep SubmicronEDA ElectronicDesign AutomationFD Finite-DifferenceFE Finite-ElementFFT Fast FourierTansformFMM Fast Multipole MethodFHM Fast Hierarchical MethodHILEX HIerarchical Layout EXtractionIC IntegratedCircuitLER line edge roughnessLFD Litho-FriendlyDesignLM Levenberg-MarquardtLSI Large-Scale IntegrationxiiList of AcronymsMOS Metal-Oxide-SemiconductorMSI Medium-Scale Integrationnm nano-meterOPC OpticalProximity CorrectionQMM Quasi-MultipleMediumRF Radio-FrequencyRWM RandomWalk MethodSI Signal IntegritySoC System-on-ChipSSI Small-Scale IntegrationSVD SingularValue DecompositionUDSM Ultra-Deep SubmicronVLSI Very-Large-Scale IntegrationxiiiAcknowledgementsI would first like to thank my academicsupervisor, Dr. Andrew Labun, for the guidance,technicaladvice,support, dedication,andpatience. Thisworkwouldnothave beenpossiblewithouthis help.I would then like to express my thanks to Dr. Roberto Musedere from the University ofWindsorfor his willingnessto serve as my externalexaminerand Dr. Peter HallschmidandDr. JonathanHolzmanfor servingon the committee. I reallyappreciatetheirvaluabletimeand constructive comments on my thesis.I would also like to thank my friends and colleagues in School of Engineeringfor makingmy graduate life enjoyable at UBC Okanagan and providing a friendly work environmentin the office. In particular, thank you to Xian Jin, Chiun-ShenLiao, Xuegui Song, NingWang, Junfeng Zhao, James Sun, Yeyuan Xiao, Mingbo Niu, and a short-timecolleague,Carl Wong.Special thanksare owed to my family, especially my parents, for their unwavering love andcontinual support throughoutmy years of education.xivChapter1Introduction1.1 MotivationNowadays, as integratedcircuit(IC) manufacturingtechnologyimproves into the deep sub-micron(DSM)regime,interconnecthas been identifiedas one of the mostcriticalchallengesfor IC designers[1]. In the past, chip performancewas determinedby the transistorperfor-mance. However, as the technologycontinues to scaledown, interconnectbehavior becomesindispensableintheDSMdomainandwilldominatetheoverallchipperformance,reliability,and cost eventually. Accuracyin predictingthe performanceof a design becomes the firststep in this interconnect-dominatedtechnology[2–4].The 2007 International Technology Roadmap for Semiconductoraddresses “three di-mensional(3D)control of interconnectfeatures”amongthe five “interconnectdifficult chal-lenges”both for technologygenerationgreateror equaland less than 22 nano-meters(nm),1Chapter1. Introductionand it is the only challengein near term (2007-2013)and distinctfuture(2014-2022).Con-tributionsto dimensionalvariation include “line edge roughness (LER), trench depth andprofile, via shape, etch bias, thinning due to cleaning, and chemical mechanical polishing(CMP)effects” [5, 6].Astheshrinkingof geometricdimensionandchangeof physicalpropertiesaffectthesen-sitivity and increasethe variability of resistanceand capacitance,the accuracyof estimatesof interconnectparasiticsdueto resistancesandcapacitancesvariability canhave significantimpactson the performanceand reliability in very-large-scaleintegration(VLSI)circuitsofsemiconductortechnologydevelopment [7–9].1.2 Research GoalsThere are several key challenging problems associated with the scaling technology. Onesuch challenge is the increasing effects of process variation. The typical variations in theinterconnectgeometriestakeaccountoflinewidth,thickness,height,andinter-layerdielectricthickness,and thesevariationsmay lead to significant disagreement between the conceptualdesignandrealfabricatedchip[10]. Thesediscrepanciesarecollectivelyreferredtoasprocessvariations [11]. The management of variation is playing an important role in shrinkingfundamental dimensions. The continuing increase in operating frequency is also anotherchallengein chip power density and within-dietemperaturefluctuations[12, 13].Bothdevicesandinterconnectshave becomeincreasinglysusceptibletovariationsduringmanufacturingprocesseswith the scaledtechnology. In the past, designerswere principallyconcernedwith device variations,which can be capturedby worst/best case corner points2Chapter1. Introductiontechniques[14, 15]. In today’s VLSIproducts,however, processvariationsare not restrictedto device variations. Interconnectvariations become more pronouncedand dominateoverdevice variations in future technologies [16]. As a result, designers need more accurateparasiticcapacitanceand resistancevalues to minimizedesign marginsand cost. Accuracyof capacitancesensitivity extractionis increasinglyessential to account for process effectsand is a challengingissue [7, 12, 17, 18].Magicisanopensourcelayouteditor. Itnotonlyprovidesuserfriendlyoperations,butitis also flexiblefor usersto modify its internalstructures. As a result,the idea to implementcapacitanceprocess variation into Magic was brought up. Magic contains approximately9,000 lines of C languagesin extractionpart [19], which causedthe initialunderstandingofMagic’sinternal structureto be more difficult than expected. As Magic has been widelyinuse for lots of universitiesin educationpurpose since it was first published,it is certainlyagood idea to implement more capabilitiesto make Magic a more sophisticatedlayout toolwithoutmuch cost, and it would be a benefit for educationpurposes in the future.In this thesis, the focus is on the improvement of capacitanceextractionin Magic andthe capacitancesensitivity on the linewidthprocess variationin interconnect. The demon-stration of this method for the first time is done by extracting capacitancesensitivity tolinewidthvariationfrom layout.The goals for this thesis are two-fold: First, CUP capacitancemodels, a capacitanceextraction, are presented and implemented in the Magic VLSI layout tool. Second thederivative of capacitance models are computed for process variation effects on linewidth.The approach to implement CUP models is to understandMagic’s internal structuresand3Chapter1. Introductionapply better formulae to calculate capacitances. To compute the derivatives, it is firstnecessaryto find the real edge of a conductor,which leads to an invented type of edge, the“coincident edge” explainedin Chapter 4. New metal search algorithmsare created alongwith a new extractionoutputformat.The contributionsof this thesis are summarizedas follows:1. Implementation of CUP models to improve Magic’scapacitanceextractionaccuracy.2. Implementationof capacitancederivatives to account for process variationsensitivity.3. Comparisonand evaluationof proposed algorithms.1.3 ThesisOrganizationThis thesis is composed of six chapters. Chapter Two starts with the background of in-terconnectdesign problemsin the DSM regime, and then discussesrelevant work done oncapacitanceextractionandprocessvariationinindustrialtools. InChapterThree,a detaileddescriptionof how Magic extracts capacitancesis presented that includes a descriptionofMagic’s internal structureand behavior. Chapter Four then discussesthe implementationof CUP models for capacitanceand interconnectcapacitancesensitivity into Magic. Realand coincident edgesand pixel-basedsearch algorithmsare introducedand described. Eval-uationis performedin ChapterFive, includingsimulationswith spice tool and comparisonswith a commercialcapacitanceextractiontool. In the end, ChapterSix concludeswith thesummary, suggestions,and areas for future work.4Chapter2Background and Relevant WorkIn thischapter,backgroundinformationandrelevant workfor thisthesisarepresented. Thefirst part of this chapter emphasizesinterconnectdesign theory. Before investigating fur-ther,abriefhistoricalperspectiveisintroduced. TheevolutionofICsbeganwithSmall-ScaleIntegration (SSI) containing only a few transistors, Medium-ScaleIntegration (MSI) con-taininghundredsof transistors,Large-ScaleIntegration(LSI) containingtens of thousandsof transistors. In the final stage, VLSI was introduced containing hundreds of thousandsto several billions transistors nowadays in a single chip. VLSI technology is divided intoseveral regimesfrom micron,submicron,deep submicron(DSM),and ultra-deepsubmicron(UDSM). This section focuses on the extractionof interconnectparasitics for high aspectratio interconnect,typical of the DSM or UDSMregime.5Chapter2. Background and Relevant Work2.1 InterconnectDesignTheoryIt is well known that interconnectdesign is becominga more and more significant concernin DSM process technologies, and the influence of shrinking interconnect line width andheight size fluctuationsbecomesmoresevere in the fabricationprocessesbeyond 45 nm [20].Therefore,a detaileddiscussionof interconnectbackgroundand design is presented in thissection.2.1.1 Deep-Submicron InterconnectIn DSM technology, interconnecthas numerousissues that would affect the performanceofcircuits. IC designersare facing more challenges,such as couplingparasitics,IR drop, andelectromigration. However, one of the most widespreadchallenges for interconnectdesignis interconnect delay in a critical path [21]. Reference [22] showed an example of delaycomponents for the 65 nm technology, in which the transistordelay component is 43%, theintra-cell resistance(coming from contact, via, diffusion, poly, and metal resistances)andthecapacitance(comingfromcontact-to-gate,poly, metal,andviacapacitances)contributes22%of thetotaldelay, andtheinter-cell(betweencells)metalandviaresistanceandcapaci-tanceaccount for35%of thetotaldelay. It is observed thatRC components area significantfractionand contributeapproximate57% of overall circuitdelay.In addition,optimalbuffer insertionmethods were used to reducedelay from quadraticto linear. However, thismethod becomesdifficultas thenumber of buffersincreasesat a fastrate in DSM technologies[23]. As size dimensionsbecomesmaller,the primarycontributorto interconnect delay is wire parasitic. The parasitics of resistance (R) and capacitance6Chapter2. Background and Relevant Work(C) are the physics properties of the wire, and the amount of resistanceand capacitanceisdependent on the physical dimensionsof the interconnectand materialsused. In next fewsections,parasiticresistanceand capacitanceare introduced.2.1.2 ParasiticResistanceThe resistance is determinedfrom the cross-sectionalarea of the interconnect. With theresistanceequationgiven byR = ρlw×t(2.1)a larger cross-sectionalarea (width (w) by thickness (t)) means a lower resistance. Theconductorresistivity ρ is in Ω· m. As the technologyshrinks down to DSM, wires tend tobe much thinner than before (see Figure 2.1). This fact leads to an increase in parasiticresistance for a minimum width wire. For instance, interconnect cross-sectionalarea isreduced by 50% from the 90 nm to the 65 nm technology node, but it results in 100%increasein resistancefor a line of the same length.Improvements have been made by replacing the materials in the interconnect system(from Al and SiO2to Cu and so-called low-κ dielectric materials) to reduce interconnectresistances. Table 2.1 lists the resistivity for Al and Cu. This approach, however, causesserious delay as integrating new low-κ materials is not a straightforward process [24, 25].Moreover, this is onlya one-timeimprovement; the resistancecontinues to increasedramat-icallyin furthersmallergeometries.In themeantime,thesimplestsolutionis to increasethewire width to reduce resistance. Unfortunately, this is not always possible because an in-creasein wiringdensity is neededto keep up withthe increasein logicdensity as transistors7Chapter2. Background and Relevant Work Area = 16k nm2 Area = 8k nm2 Linewidth reduction Trench depth reduction Cros-sectional area reduction 28% 29% 50% 90nm 65nm 181nm 130nm (Numbers are from ITRS) Figure 2.1: Resistancecross-sectionalarea reductionfrom 90 nm to 65 nm technologynodes [5].are scaled.2.1.3 ParasiticCapacitance Cfrg Cfrg Cfrg Cfrg Cltr Carea Carea Cltr M2 M1 M3 Figure2.2: Capacitanceconfigurationin a typicalDSMtechnologywith1.5aspectratio.8Chapter2. Background and Relevant WorkCouplingbetweenneighboringconductorsgives riseto parasiticcapacitance,andto firstorder the amount of capacitanceis proportionalto the ratio of the conductive areas facingeach otherbutinverselyproportionalto theseparationof two conductors.Given thechargeson both conductors’plates are +Q and −Q with a V voltage between them, the equationfor the capacitanceis shown with integrals:C =QV; Q =integraldisplayV0dV ·C(V) (2.2)A typical structureof a DSM interconnectwith the most dominant parasitic capacitanceslabeledisshowninFigure2.2. Metal2 conductorshave lateralcapacitancewiththeadjacentconductorsandalsohave areaandfringecapacitanceswithmetal1 and3 conductorson theabove and below. Areacapacitanceis causedby two different conductorsoverlapped, and itwas the dominant element in earlier technologies. However, lateral and fringe capacitanceshave grown dramaticallyto be the major contribution to the coupling capacitancedue tothe narrower wires and spacingin DSM technology. Old Assumption DSM t w l Figure 2.3: Capacitancein old assumptionand DSM.9Chapter2. Background and Relevant WorkTo improve performance,advanced methods, such as low-κ dielectricinsulatorsand airgaps, are strongly required to reduce κ to around 1.9 [26], but it is no longer useful infurther scaling of technology down to 90 nm and below (see Figure 2.4 and Table 2.1). Acomparison between interconnects and device delays by using two different materials, Aland Cu with SiO2and low-κ from the National Technology Roadmapfor SemiconductorsSEMATECH [27] is made. By observing the interconnectdelay for Al with SiO2and Cuwith low-κ, it is clear that the total delay for a gate with Cu and low-κ is definitelylowerthan Al and SiO2, and it solves the delay problemfor the 250 nm and 180 nm technologygenerations.However, the delay startedto increaseexponentiallywith furtherscalingdownof the technology. Challenges develop as the delay time starts to increase parabolicallybeyond 130 nm.Table 2.1: Informationof Figure2.4 (adaptedfrom [27]).Aluminum (Al) 3.0 µΩ/cmCopper (Cu) 1.7 µΩ/cmSiO2κ= 4.0Low-κ κ= 2.0Al & Cu 0.8 µ ThickAl & Cu Line 43 µ LongThe easiestsolutionfor circuitdesignersto obtaina lower capacitanceis to increasethespacingbetween wires,but at the costof moreareain the design. Thebenefitsof increasingthewirespacingarelimitedby diminishingreturnsandcanonlybe usedat thecostof losinginterconnectdensity.10Chapter2. Background and Relevant Work 0 5 10 15 20 25 30 35 40 45100130180250350500650Delay (ps)Generation (nm )Interconnect delay dominates gate delay in DSM VLSIGate DelayInterconnect (Al+SiO2)Sum of Delays (Al+SiO2)Interconnect (Cu+low K)Sum of Delays (Cu+low K)Figure 2.4: Interconnectvs gate delay (adaptedfrom [27]).2.1.4 InductanceInductanceis anothercriticalparasiticeffect. A severe inductive effect includesovershoots,undershoots and oscillation in signal waveform, and aggravates crosstalk and power gridnoises [28, 29]. These signal integrity faults can potentially manifestthemselves as glitchesor worse, as false transitionsat the end of wires. Inductanceis the ratio of the magneticflux Φ generatedby the electric current i and passing througha closed loop with N turns,and the equationis shown:L =NΦi(2.3)11Chapter2. Background and Relevant WorkIn the past, inductancewas not a criticalconcernbecauseRC effects dominatedat low fre-quencies. However, the increasinginductanceeffect arisesnot only fromthe resultof higherswitching frequency, but also from other factors: resistanceand capacitancereductionsbyCu andlow-κ dielectricrespectively, denserandsmallergeometries,andgrowingcomplexityof interconnectdesign [30–32]. The promotionalliteraturefor one of the leading industrialtools, SynopsysStar RCXT, claims that modeling global interconnectsof RC circuitsis nolonger adequate,and the inductanceeffect must be includedto avoid underestimatingthesignal integrity problem[33].In this thesis, inductancewas neglectedfor a few reasons. The first reason is that it isverydifficultto predictandcaptureon-chipinductanceeffectbecauseit dependsstronglyonthe overall constructionof the integratedcircuit[34]. The uncertainty of the current returnpath, prior to parasiticextractionand circuit model simulation,has challengedinductancemodelingand analysisin the DSM era [35, 36]. Unlike capacitance,which is basedstronglyon neighboring features, inductive effects have a much larger spatial range. The secondreasonis that inductancedoes not causesevere signalor propagationdelay of interconnectsproblems. It is shown that the worst-case inductance would cause an 8% reduction inthe delay [28]. The third, and most significant, reason is that Magic does not includean inductance extraction system. Such a modification would have required more humanresources, which is beyond the scope of the work intended for this thesis. The scope ofthis Master’sthesis was mainly about implementing the sensitivity analysisin capacitanceextraction.12Chapter2. Background and Relevant Work2.2 CapacitanceExtractionIn the DSM regime,interconnectbehavior dominatesthe overall chip performance. There-fore, accurate estimates of interconnect due to resistance-capacitanceare significant forpredictingperformanceand reliability in VLSI circuits[4, 7]. There are many different ap-proaches to capacitanceextraction. In this section, a number of previous approaches arepresented, and one of them is chosen for investigation and implementation in the Magiclayout tool.2.2.1 AnalyticalFormulaeCapacitancevalues are estimatedby analyticalformulae in many cases because there is acompelling need for simple and fast approximationformulae, and these formulae are espe-cially useful for hand calculations.The basic capacitancecalculationis the parallelplate formula given byC = epsilon1Ad(2.4)where A is the area of two parallel planar conductorsseparatedby distanced and epsilon1 is thedielectricconstant. AstheICtechnologyadvances,theinterconnectwidthsbecomenarrowerthan their verticalthickness, which meansfringe capacitanceis comparableto overlap areacapacitance,and the need to model the capacitancemore accuratelybecomesimportant asshown in Figure2.2.13Chapter2. Background and Relevant WorkTwo accurateformulaewere proposedusingapproximateconformalmappingtechniquesin [37], and both formulae are more accurate, within 1% error, for a metal line of widthgreaterthan the dielectricthickness.Later a simpleanalyticalformula was presented to includea direct physical interpreta-tion in [38]. The replacement of rectangularwire cross-sectionwith an “oval” one is made,and the final cross-sectionis composed of a rectangle and two half-cylindersas shown inFigure2.5. The formula is shown:C = epsilon1w−t/2h+2pilnparenleftBig1+2ht+radicalBig2htparenleftbig2ht+2parenrightbigparenrightBig(2.5)It is shownthatthisformulais simplerandmoreaccuratethantheproposedapproximation w t h w-t/2 t/4 t/4 Ground plane r = t/2 Figure 2.5: Conductorwith a rectangularcross-section(adaptedfrom [38]).in [37].A purely empirical formula based on evaluating numerical solutions was proposed in[39], and it was later improved by extending the empirical expressionand simultaneously14Chapter2. Background and Relevant Workreducingthe range of validity in [40]. The formula is shown:C = epsilon1bracketleftBiggwh+0.77+1.06parenleftBigwhparenrightBig0.25+1.06parenleftbiggthparenrightbigg0.5bracketrightBigg(2.6)wherethefirsttermdescribestheparallelplatecapacitorandtheotherthreetermsrepresentside effects.Reference [41] includes a complete comparison of these analytical formulae, and it isshown that Meijs and Fokkema [40] is the best choice in every respect, both most accurateand fastestin runtime.2.2.2 Field SolverElectric field solvers produce accurate results for multi-conductorsystems in capacitanceextraction. In [4], several reasonsto use field solver for parasiticextractionwere discussed:field solvers deliver accurate distributed self- and coupling capcaitances, and it handlesgeneral, non-Manhattangeometries and scales to DSM domain. Three major field solverapproaches are discussedbelow.2.2.2.1 RandomWalk MethodThe random walk method (RWM), also known as a stochastic algorithm, used for high-speed capacitanceextraction in multi-level VLSI interconnects,was introduced by LeCozand Iverson [42, 43]. The basic idea is to present boundary-integral solutions to computeelectric potential and electric field at a cube center. The capacitance CABbetween two15Chapter2. Background and Relevant WorkelectricalconductorsA and B can be shown by Monte Carlo integration:CAB=contintegraldisplaycontintegraldisplayd2r1ε(r1)E(r1)VB(2.7)Each randomwalk consistsof a series of steps onto cube boundaries. Figure 2.6 shows therandom walk starting on an integration surface around conductor A and terminating ona conductorB, and the estimated capacitancebetween both electrodes is associated withEq. 2.7. Reference [44] addresses that the random-walk method performs with excellentcomputationalefficiency because it requires no numerical mesh. Random walk methodshave been successfullyimplemented in some commercialtools, such as Magma QuickCap[45] and SynopsysRaphaelNXT [46]. A B . r1 . . . r4 r2 r3 r5 Figure 2.6: Samplerandomwalk method (adaptedfrom [44]).16Chapter2. Background and Relevant Work2.2.2.2 Volume-BasedMethodIn volume-basedanalysismethods, Laplace’sequationis solved outsidethe conductors(seeEq. 2.8).∇· epsilon1∇Φ= 0 (2.8)Onecommonwaytosolve 3DLaplace’sequationnumericallyistouseFinite-Difference(FD)[47, 48] or Finite-Element (FE)[49–51] Methods, in which FD’smainideais to approximatethe derivatives in the equations. The basic idea in FE method is to find an approximatesolutionto simplifyinga complicatedproblem. For instance,suppose a structure(beam) isgiven, withFEmethod. It is thendividedinto severalelements in a suitablesolutionin eachelement (see Figure 2.7). Volume-basedmethods are computationallyexpensive with very 1 L 2 3 4 Element 1 Element 2 Element 3 1 2 2 3 3 4 l=L/3 l=L/3 l=L/3 W1 W2 W3 W4 W1(1) W2(1) W1(2) W2(2) W1(3) W2(3) Figure 2.7: Samplefinite element method (idealizationof a beam).large sparse matrices and require numerical techniques to improve the run time efficiencyand memorystorage. FD and FE methods have been used in some commercialtools, suchas AnsoftMaxwell [52] and SynopsysRaphael[53].17Chapter2. Background and Relevant Work2.2.2.3 Surface-BasedMethodThe surface-basedmethod, also known as IntegralEquationFormulationMethod, is a well-known method in VLSI capacitanceextraction, and many proposed algorithmsare basedon it. The following describes a set of different techniquesfor parasiticextractionover thepast two decades,and they are all basedand extendedon the integralequationformulationmethod.BEM. Boundary-Element Methods (BEM) are commonlyused to perform elec-trostatic analysis [54], and a technique is shown in [55]. Many of the following techniquesare based on BEM.The purpose of BEM is to find the short-circuit capacitance matrix in a domain VcontainingM conductors(see Eq. 2.9).Q = CsΦ (2.9)where Q is conductorcharge QT=[Q1,Q2,···QM] and conductorpotentialsΦT= [Φ1,Φ2,···ΦM]φ(p)=integraldisplayVG(p,q) ρ(q) dq, (2.10)where ρ(q) is the charge distributionand G(p,q) is the Greens function for V. BEM sub-divides the conductors’ surfaces and approximates inverse matrix to eventually computecapacitancematrixCs. One of the commercialtools, Space3D, uses this method in capaci-tance extraction[56].18Chapter2. Background and Relevant WorkFMM. In 1991, a 3-D capacitance extraction program based on the multipoleexpansionswas published: FastCap [57]. The algorithms,based on fast multipole method(FMM), acceleratesthe boundary-element solution with conjugateresidual method for re-ducingorderof computationsand complexity. It is noticedthat for problemswithas few as12 conductorsthe multiple acceleratedboundaryelement method can be nearly 500 timesfaster than Gaussian elimination based algorithms, and five to ten times faster than theiterative method alone,dependingon the requiredaccuracy[57]. FastCaphas becomeverypractical, popular, widely used in industry and academia, and has initiated an extensiveamount of research in the area of the development of fast integral equation solution tech-niques[58, 59].FFT. Several years later, a new algorithm,“precorrected-fastFourier transform(FFT)”, was presented for accelerating the potential calculation and solving electromag-netic boundaryintegral equationsarising in the extractionof couplingcapacitancesin 3-Dgeometries[54]. The comparisonshows thatfor a widevariety of geometriesin IC packages,the new algorithmis superior to the fast multipole algorithmused in FastCap in terms ofexecutiontime and memoryuse by more than an order of magnitude[54].SVD. Another integral equation 3-D solver is IES3(“ice cube”), which usessingularvalue decomposition (SVD) algorithm,an extremelyeffective tool for compressionof rank-deficient matrices. The result shows that IES3is dramatically faster than themultipole-basedapproaches [60].Hierarchical. Shiandet al. presentedafasthierarchicalalgorithmforcomputing3-D capacitanceextraction, and it is significantly faster with less memory used than the19Chapter2. Background and Relevant Workprevious famous algorithm used in FastCap. It is noticed that the this hierarchy-basedalgorithmis 60 times faster than FastCap and uses 1/80 of the memory used by FastCapwithaccuracyof2.5%. Also,thisalgorithmis 5 to150timesfasterthancommercialsoftwareQuickCap with the same accuracy[61, 62].FMM+Hierarchical. Beattieand PileggicombinedFMMwith the hierarchicalrefinement methodsto proposesolutionsthatusebothwindowingandshift-truncateboundsto get an error value for the extracted capacitancesto improve the speed further, calledadaptive window sizing methodology. This methodology is of use in identifying crosstalkproblemzones for interconnectoptimizationand noise reduction[63].Nebula. Nebula was presented for accurate large-scalecapacitancecalculationswith a charge distributionthat decouplescharge variation from conductorgeometry. Thisseparationsignificantly reduces the discretizationsize, the time and memory requirementscompared to the previous approaches, and Nebula, based on FMM, is efficient enough tocomputefull capacitancematrixof typical interconnectproblems[64].QMM. The quasi-multiple medium (QMM) method greatly reduces the centralprocessingunit (CPU)time and memoryusage of large-scaledirect BEM computationsbytransferringthe coefficient matrix into a highly sparse block matrix and iterative equationsolver [58]. Later, an enhanced QMM-BEMsolver for 3-D multiple-dielectriccapacitanceextraction was proposed to achieve much higher speed and adaptability. With two en-hancements, an automaticdeterminationof QMMcuttingpair number and preconditioningtechnique, the results showed over 10X speed-up and memory saving over the multipoleapproach [65].20Chapter2. Background and Relevant WorkFHM. Fast hierarchical method (FHM)is an efficient accelerationalgorithmfor3-D capacitanceextraction. A preconditioningtechnique is proposed by virtue of inherentpropertiesof hierarchicaldata structures,and experiments show a remarkable improvementon coverage of the iterative procedure[66].2.2.2.4 Field Solver SummaryThe random-walk method is practicallybeneficial for suitability to rectilineargeometries,statistical-errorcancellation,selective integrationover Gaussian surfaces,and direct capac-itancematrixevaluation[43]. The surface-basedmethod is robustand has advantages overvolumebasedmethod, includinga betterconditioning,smallerdimensionality, and the abil-ity to treat arbitraryregions[60].In general, the random walk method is the best for calculating self-capacitancefor acomplicatednet; the surface based method is most suitable for calculatingsmall couplingcapacitances,and the volume-basedmethod is good at dealingwith multipledielectrics.2.2.3 Library Look-UpBasedMethodLibrarylook-up based method is a practicalapproach to estimatecapacitanceefficiently inlayout. The analytical or the table-look-up models are automaticallygenerated based onnumericalsimulations,and this method is often used to extractparasiticsdirectlyfrom thegiven mask layout in a chip and fabricationprocesses. A couple of techniques have beenproposed in [67–69], and [67] has been chosen to be implemented in the project becauseMagic is a VLSI layout tool, parasitics values are obtained in the extraction. Figure 2.821Chapter2. Background and Relevant Workshows the block diagram of the library model procedure as implemented in this project.The detailswill be discussedin a later sectionof this chapter. Physical Interconnect Parameters 2D Numerical Simulation  Capacitance Data 2D Model Library substrate Metal 1 Metal 2 Metal 3 space Capacitance Models  Optimization Figure 2.8: Overall flow of interconnectlibrarymodel (adaptedfrom [67]).2.3 Commercial Parasitic ExtractionThis section describes several industry parasitic extractiontools from some of the largestelectronicdesignautomation(EDA)companies,such as Synopsys,CadenceDesignSystems,Mentor Graphics,Zuken, and Magma Design Automation,to demonstratethat this thesisresearch is important.22Chapter2. Background and Relevant Work2.3.1 Synopsys- Star-RCXTSynopsysStar-RCXT is a standardfor parasiticextractionin EDA industry. It provides aparasitic extractionsolution for application-specific integrated circuit (ASIC), System-on-Chip(SoC),customdigital,analog/mixed-signal(AMS),radio-frequency(RF)andmemorydesign. Synopsysclaims that “the offered capabilitiesinclude variation-aware parasiticex-traction,chemical-mechanicalpolishing(CMP)basedandlitho-awareextraction,inductanceextraction,and analogmixed signal designflow” [33].In addition,Star-RCXTcouldbe integratedinto industrystandarddesignflows, layoutverificationand simulationtools easily, and its incorporated flow with RaphaelNXT, a 3Dfield solver capacitanceextractor providing silicon-accurateand coupling capacitancesforcircuitdesign,makes it an accurateextraction[33].Star-RCXT uses a statisticaltechnique to model interconnectprocess variation effectsaccuratelyat advanced process nodes. This solutioneliminatesthe need to run traditionalmulti-cornerextractionsand provides multiple netlists and a single netlist with sensitivity(seeFigure2.9) to enhancetheproductivity andperformance.Thevariationof each processparameter, including conductor, dielectric thickness, is available and used based on theprocess variations[33]. The focus is on the linewidthparametervariationin this thesis.2.3.2 CadenceQRC ExtractionAs advanced process technologiesbecome more critical,parasiticextractionbecomesa keyfactor not only during the validation phase but also during design implementation. Ca-dence claims that “QRC Extraction is a 3D full-chip parasitic extractor in industry, and23Chapter2. Background and Relevant Work   Star-RCXT VX Sensitivity-Based Extraction Parameterized Parasitic Database DSPF SBPF SPEF SPICE SBPF SOEF SPICE PrimeTime, PrimeRail, HSPICE, PathMil, NanoTime PrimeTime, HSPICE >2X faster than 5-corner extraction Single Proces File Multiple Netlists Single Netlist With Sensitivity Statistical STA, Simulation flow Traditional corner-based STA, Signof flow Figure 2.9: Star-RCXT’ssensitivity-basedextractionsolution(adaptedfrom [33]).the fast and accurateRLCKextractionmake it an integratedextractionsolutionfor designimplementation and validationat 90 nm and below” [70].Figure 2.10 shows the key components of Cadence QRC Extraction,and multi-cornerand statisticalextractionare briefly discussedhere. Multi-cornerextractionis required topredictparasiticeffects,and the number of cornersand the processgeometrygrow inverselyproportionallytoeach other. Itextractsmulti-cornersatoncetoefficientlyreduceextractionruntimes at advanced process nodes. QRC also takes random parameter variations intoaccount to provide accurateresultsin statisticalextraction[70].24Chapter2. Background and Relevant Work Mixed-signal RF Analog Cel Custom Digital Distributed procesing Multi corner / Statistical Manufacturing efects Reduction Substrate Model-based CMP and Litho Hierarchical extraction Field Solver L and K extraction R and C extraction Fabrication Figure 2.10: CadenceQRC extraction’sadvanced capabilities(adaptedfrom [70]).2.3.3 Mentor Graphics- Calibre LFDThe key benefit of Mentor GraphicsLitho-FriendlyDesign(LFD)is “the capability to cap-tureprocessvariationsinthedesignflow.” Itcapturesinformationonprocesswindow effectsin orderfordesignersto improve thelayoutandmake a designmorerobustandlesssensitiveto process window variations[71].2.3.4 Magma- QuickCapQuickCap NX is a 3D parasiticextractorfor critical circuit analysis. As with Star-RCXT,Magmaclaims that “QuickCap NX is for parasiticextractionand in productionuse in thetop 10 semiconductorcompanies”[72].25Chapter2. Background and Relevant WorkMagma’s QuickCap NX is an accurate 3D extractor that precisely models advancedprocess effects. It is used in process studieswith performanceon accuratenoise and timinganalysis,proved to deliver capacitancevaluethatarewithin1 percent siliconmeasurements.Magma claims that “the average difference between QuickCap NX capacitancevalues andactualsiliconmeasurements have been reducedfrom 9.79 percent to 0.11 percent by takingprocess effects into account” [72]. In addition,QuickCap NX’s multiple techniques reduceruntime and makes it memory efficient. Figure 2.11 shows how QuickCap NX accuratelymodels advanced process effects. This thesis concentrated on the width variation. Nominal layout Width expanded = f(layer) OPC width = f(w,s) Sidewal shape = f(z) Sidewal, OPC = f(w,s,x) Thicknes = f(local density) Figure 2.11: QuickCap NX’s process variationsolution(adaptedfrom [72]).26Chapter2. Background and Relevant Work2.3.5 Space 3DSpace 3D is a layout-to-circuitextractor from OptEM Corporation, and it uses BEM toaccurately and efficiently compute 3D interconnect capacitances of ICs based upon thelayout description,which implies a lower number of discretizationelements is used for 3Dsituations. Moreover,theimplementationofa newmatrixinversiontechniquethatcomputesonlycouplingeffect between “nearby” elements makes itselfcapableof quick extractionandmemoryefficiency[56].2.3.6 IndustryParasitic ExtractionSummaryIt is noticed that parasitic extraction for process variation is the key challenge for theseindustryextractiontools as the real fabricationis not exactlythe same as the layout in thedesign. Table 2.2 shows a summaryof commercialstools with different types of extractionmethods. FEMand RWM extractorsare broadlyused in industriesfor parasiticextraction.As a result,the research of process variationis a necessity in modern technologies.Table 2.2: Commercialextractionmethods.Commercial Tools ExtractionMethodsBEM FEM RWM otherSynopsys-Star-RCXT multi-corner/statisticalSynopsys-Raphael√ √Synopsys-RaphaelNXT√Cadence-QRC Extraction multi-corner/statisticalMentor-Calibre designfor manufacturingMagma-QuickCap NX√Ansoft-Maxwell√OptEM-Space3D√27Chapter2. Background and Relevant Work2.4 MagicTechnologyFilesforLookUp-BasedMethodIn this section,a capacitancelibrarymodel procedurefor Magicis presented similarto thatshown in Figure2.8. This extractorconsistsof a file reader,a stack file, conductorlooping,2D field solver from [73], and Techgen to read in an input data, which includesanisotropicdielectriclayersandmultipletypesofmaterialproperties,andgeneratea technologyfilewithspecified sets of capacitancecoefficients. The procedure is used to computethe coefficientsfor CUP models, which will be introduced in Chapter 4, and a comparisonwill be madebetween Magicusing CUP models and Space 3D, a commercialcapacitanceextractiontoolfrom OptEMEngineeringInc., in Chapter5.2.4.1 Stack FileA stack file is composed of name, conductor,dielectric and some other sections, but onlythe important sections are discussed in this thesis. The name identifies the name of thestack. The conductoridentifies that data about the conductinglayers as follows. In eachlayer, layer order, layer name, minimum spacing, maximum spacing, width, thickness, andmax dist are listed. The dielectricidentifies that data about the dielectriclayers, and eachlayer containstheinformationof layer order,dielectricname,correspondingconductorlayer,thickness,anddielectricconstant. Thestackfileusedinthisthesisandadiagramillustratingits metal configurationis provided and presented in Appendix A.28Chapter2. Background and Relevant Work2.4.2 TechgenTechgenis theprogramthatimplements thecapacitancelibrarymodel procedurethatreadsin a Magictemplatetechnologyfileandgeneratesa newonewiththenewmodelparameters.Techgen then reads in a standardMagic technology file line by line, echoes each line, andadds or modifies the capacitancemodel informationthat needs to be changed. Below is amore in-depthdescriptionof each functionin techgen.Checkdimensions: This function checks for the first word “width” or “spacing”in thetechnologyfile,andit changesthedistancetoagreewiththestack file. A deeper explanationon widthand spacingdimensionscan be foundin the TechnologyFile sectionof Chapter3.Area and Overlap: Magic’s area model is specified in lines beginning with “areacap”or “overlap” in the technology file. This function checks for the first word “areacap” or“overlap”. Instead of replacing the Magic capacitancemodel value, it adds a similar linethat specifies CUP models.Sidewall and Sideoverlap: Magic’s lateral model is specified by in lines beginningwith“sidewall” and its fringe model is specified in lines beginning with “sideoverlap”. Thesefunctionsare similarto Areaand Overlap,and theyjust check the first word “sidewall” and“sideoverlap” and add anothersimilarline that includesCUP models with parameters.When techgen is completed,a new technology file is ready to be used in Magic, withthe original Magic capacitancemodels and new CUP models, both of which are read byMagic. TechgenandtherevisionstoMagictoreadtheenhancedtechnologyfilewerewrittenby undergraduatestudents Josh Schlenker and Travis Skippon. Some minor changes andcorrectionshave been made.29Chapter3ExistingCapacitanceExtractionModel of MagicThischapterbeginswitha briefoverviewof MagicVLSIinternalstructuresandthenfollowsthe technology file section and explanations of its extraction algorithms, which includesoverlap, sidewall, and sidewall overlap couplingcapacitances.After capacitanceextraction,a briefexplanationof extractionoutputis presented. Finally, a summaryof the MagicVLSIlayout tool is presented in the end of the chapter.Magic is an interactive layout editing system for creating and modifying VLSI circuitlayouts. Magicis not only a color painting tool, but it also provides the user with powerfuloperations. These include the feature of design-rulechecking to avoid layout violation atany time to enhance performance[74]. In addition, Magic contains approximately 90,000lines of code writtenin the C language. Magic’sextractoroccupiesone-tenth of Magic’sCcode [19, 75].30Chapter3. ExistingCapacitance Extraction Model of Magic3.1 MagicDatabaseAs mentioned to in Chapter1, Magic is an interactive layout editingsystemfor large-scaleMOS custom ICs. As in most layout editors, Magic layout consists of cells, and each cellcontains two types of things: geometricalshapes and subcells. In this section,the principledatabasein Magic is illustrated.3.1.1 GeometryGeometryis the basic database of a software, and a number of structuresapart from thebasiccell,plane,andtiledefinitions,areusedfrequently throughouttheMagicsource. Mostof thesebasicstructureshave to do withgeometryand can be foundin the geometryheaderfile under the Magic directory.3.1.1.1 PointA point in 2-dimensionalinteger space is referred to coordinates p x and p y. Figure 3.1shows the basic point structure. . (p_x, p_y) Figure 3.1: Point structure.3.1.1.2 RectangleA rectangle,with area specifiedby lower-leftand upper-right corners(points), is referredtopoint structuresr ll and r ur for the lower left-handcorner and upper right-hand corner,31Chapter3. ExistingCapacitance Extraction Model of Magicrespectively. Note that while the four coordinatesof a rectangleare, as defined, r ll.p x,r ll.p y, r ur.p x, and r ur.p y, the magic source code almost always refers to thesepoints by macro shorthand, which are r xbot, r ybot, r xtop, and r ytop respectively.Figure3.2 illustratesthe basic rectanglestructure. (r_xbot, r_ybot) (r_xbot, r_ybot) ..Figure 3.2: Rectanglestructure.3.1.2 Corner Stitched TileMagicusesa corner-stitchedstructuretopresent thesubstancesofcells,thatisa geometricaldatastructureforrepresentingrectangulartwo-dimensionalobjects[76], orcalledManhattanshapes (those whose boundariescontains only horizontal and vertical segments, see Figure3.3) Moreover, corner-stitching structureis the reasonfor fast extractionspeed in Magic. P2 P1 Manhattan = |x1 - x2|+|y1 - y2| Figure 3.3: Corner-stitching (Manhattanshape).A tile is a basic unit in a simple rectangular shape that corresponds to a length ofinterconnects. Each tile has the following structure32Chapter3. ExistingCapacitance Extraction Model of Magictypedef struct tile{ClientData ti_body; /* Body of tile */struct tile *ti_lb; /* Left bottom corner stitch */struct tile *ti_bl; /* Bottom left corner stitch */struct tile *ti_tr; /* Top right corner stitch */struct tile *ti_rt; /* Right top corner stitch */Point ti_ll; /* Lower left coordinate */ClientData ti_client; /* This space for hire. Warning: the default* value for this field, to which all users* should return it when done, is MINFINITY* instead of NULL.*/} Tile;This is the fundamental data structure in Magic. ti body describes which layer the tileis, and *ti lb, *ti bl, *ti tr, and *ti rt represent different corner stitched tiles respectively.Ti ll is the lower left coordinate,so the position of the any specific tile is recognized. Thefollowing figureillustratesthe tile structuresin details. The corner-stitched imageconnectseach tile to four sides of its neighbors.The heavily used macroson (Tile *)tilesin Magic are listed below.• TOP(tile)• BOTTOM(tile)• LEFT(tile)33Chapter3. ExistingCapacitance Extraction Model of Magic  Tile LB BL TR RT lower left Figure 3.4: Basic tile structure.• RIGHT(tile)• RT(tile)• LB(tile)• BL(tile)• TR(tile)The first four macros return a position in Magic’s internal coordinates, and the last fourmacros return a pointer to the appropriateneighboring tile (see Figure 3.4). This use hasmade the programmereasier to implement and reducethe confusionof tile definition.3.1.3 PlaneIn Magic,all geometriesare split into partiallyindependent planes. In general,theseplanescorrespondroughlytothemasklayersfromwhichanICisbuilt. Typically, onedefinesa newplaneforeach setoflayertypesthatarelargelynon-interactingwithothertypes. Thisworksespeciallywell for metalroutinglayers, sincethemetallayers arecompletelynon-interacting(excludingcapacitanceextraction,which is separatefromthe databaserepresentation),andonly interactwherecuts (vias)are defined. This works much less well for layers close to the34Chapter3. ExistingCapacitance Extraction Model of Magicoriginal wafer surface. Polysilicon, diffusion regions, and wells are all heavily interacting,and thereforetend to work best when they are definedall on a single plane.Even though it would be possible to define everything in the layout on one plane, thecorner-stitched tile structuresare broken up into pieces for the types overlap in the sameplane. For instance,if type1 and type2 are overlapped in a singleplane,Magicrequiressep-arate types type1, type2, and an additionaltype type1-plus-type2, and the corner-stitchedstructureswill be subdivideduntil each tile can be represented by one of these three types.Thisis highlyeffective in somecaseswhen,forexample,type1 is n-diffusion,type2 is polysil-icon, and thus type1-plus-type2 works out ”naturally”to be layer type n-transistor.The plane structureholds a corner-stitched tile representation and looks like:typedef struct{Tile *pl_left; /* Left pseudo-tile */Tile *pl_top; /* Top pseudo-tile */Tile *pl_right; /* Right pseudo-tile */Tile *pl_bottom; /* Bottom pseudo-tile */Tile *pl_hint; /* Pointer to a "hint" at which to* begin searching.*/} Plane;Each cell contains several corner-stitched planedto represent the cell’s geometriesand sub-cells,andeachplaneconsistsofrectangulartilesofdifferenttypes. Therearethreeimportant35Chapter3. ExistingCapacitance Extraction Model of Magicproperties in a corner-stitched plane: coverage, strips,and stitches.3.1.3.1 CoverageEvery point in a corner-stitched plane is contained in exactly one tile. Empty space isrepresented, as well as the area covered with material. Figure 3.5: Coverage tile.In the case shown in Figure3.5, there are three solid tiles and space tiles (dottedlines)cover the rest of the plane. The space tiles on the sides extend to infinity. In general, aplane can contain many different types of tiles.3.1.3.2 StripsHorizontal stripsrepresent materialof the sametype. The stripstructureprovidesa canon-ical form for the databaseand prevents it from fracturinginto a number of small tiles.Areas of the same type of material are represented with horizontal strips that are aswide as possible. In each of the Figure 3.6, the tile structure on the left is illegal and isconvertedinto the tile structureon the right. In Figure3.6 (a), all tilesmust be in rectangleshapes. In Figure3.6 (b), it is illegalfor two tiles of the same type to share a verticaledge.36Chapter3. ExistingCapacitance Extraction Model of Magic (a) (b) (c) Figure 3.6: Strips tile (adaptedfrom [19]).In Figure3.6 (c), the two tiles must be mergedas one becausethey share exactlythe samehorizontal span.3.1.3.3 StitchesThe records describingthe tile structureare linked in the databasethrough four links pertile, called stitches. The links point to neighboring tiles at two of the tile’s four corners.A illustrationin Figure3.7 shows the detailedstitch tilesin a planewithlabels pointingto each othertiles, wherespacetiles are definedwhenthere is no conductorpresented. Theboundaryof the planeis positive andnegative infinity definedin the corner(seeFigure3.7).Magic searches tiles in the “tile search” function. It first finds the left top tile in arectangleandthenwalksthroughrightward. A pseudocode is shown in Figure3.8, andthisfunction is heavily used throughoutMagic codes. Appendix B shows an example of howMagic searches tiles, step by step.37Chapter3. ExistingCapacitance Extraction Model of Magic              metal 1 space metal 1 metal 1 metal 1 space space space space space space +! -! -! -! -! +! +! +! Figure 3.7: Stitch tile.3.2 MagicTechnologyFileAs mentioned earlier,Magic reads in its own technologyfiles. Even thoughMagic containsan extensive amount of knowledgeabout integratedcircuits,it is a technology-independentlayout tool [74]. In other words, the informationis not embeddeddirectlyin code, and it iscontainedin a technologyfile thatMagicreadswhenlaunched. Thisfile definestheabstractlayers and the corner-stitched planes; it also describes design-rulechecking in detail, suchas minimum width and spacingbetween objects on the same layer. In addition,it provides38Chapter3. ExistingCapacitance Extraction Model of Magic tile is defined to be the left top tile of rectangle that is to be searched tp = tile; tpnew = new_tile; while (TOP(tile) > BOTTOM(rectangle) { enumerate:     if (tile is in the region) go to function;      tpnew = TR(tp);     if (LEFT(tpnew) < RIGHT(rect) /* */    {  while (BOTTOM(tpnew) >= BOTTOM(rect) tpnew = LB(tpnew);  if (BOTTOM(tpnew) >= BOTTOM(tp) | BOTTOM(tp) <= BOTTOM(rect)  {      tp = tpnew;      goto enumerate; }     }     while (LEFT(tp) > LEFT(rect) /* Each iteration returns one tile further to the left */    {  if (BOTTOM(tp) <= BOTTOM(rect) return (0);  tpnew = LB(tp);  tp = BL(tp);  if (BOTTOM(tpnew) >= BOTTOM(tp) | BOTTOM(tp) <= BOTTOM(rect)  {      tp = tpnew;      goto enumerate; }     }     for (tp = LB(tile); RIGHT(tp) <= LEFT(rect); tp = TR(tp) /* Walk down to next tile */ } Figure 3.8: Tile search algorithmpseudocode.the model coefficients for coupling capacitances, substrate capacitance and resistance fordifferent layers in the extractionsection.3.2.1 PlanesThe planes section of the technology file specifies how many planes will be used to storetiles in a given technology, and each plane has its own name. Each line in Table 3.1 definesa plane by giving a comma-separatedlist of the names[74].39Chapter3. ExistingCapacitance Extraction Model of MagicTable 3.1: Planessection.planeswell, wimplant, iactive, diffusion, polysilicon,ametal1,m1metal2,m2metal3,m3oxide, oxend3.2.2 ContactThecontactsectiondescribes which typesarecontactsandtheplanesandcomponent typesto which they are connectedin Magic. Each contact line begins with a tile type, base, tobe a contact. This type is then referredto as a contact’s base type. The remainderof eachline is a list of non-contact tile types that are connectedby the contact, referred to as theresidues of the contact. In Table 3.2, for instance,the type m2contact is the base type ofa contact connectingthe residuelayers on the planesmetal1and metal2[74].Table 3.2: Contact section.contactpcontact poly metal1ndcontact ndiff metal1pdcontact pdiff metal1ppcontact ppdiff metal1nncontact nndiff metal1m2contact metal2 metal1pad metal1 metal2 glassend40Chapter3. ExistingCapacitance Extraction Model of Magic3.2.3 DRCThedesignrulescheckedinMagicarecompletelyspecifiedinthetechnologyfile. Two simplerules are introduced in this section,width and spacing. Table 3.3 shows a sample widthand spacingrules in the drc section.Table 3.3: DRC section.drcwidth poly,pc/a 2 error messagespacing poly,pc/a poly 2 touching ok error messagewidth m1 3 error messagespacing m1 m1 3 touching ok error messagewidth m2 4 error messagespacing m2 m2 3 touching ok error messagewidth m3 4 error messagespacing m3 m3 4 touching ok error messageend3.2.3.1 WidthrulesThe minimum width of a collectionof types is expressedin the following format:widthtype-list width errorwheretype-listis a set of tile types, and widthis an integer,and erroris a string,which canbe printed to the consoleto let the user know if the rule is violated.3.2.3.2 SpacingrulesAnothersimplekind of designrule is the spacingrule, and it has two flavors: touching okand touching illegal, both with the following format:spacingtypes1 types2 distance flavor error41Chapter3. ExistingCapacitance Extraction Model of MagicThe touching ok allows types1 and types2 to be adjacent to each other, and it requiresthat any type in the set types1 must be separated by a “Manhattan”distance of at least“distance” units from any type in the set types2 that is not immediatelyadjacent to thetypes1. An exampleof Manhattandistanceis illustratedin Figure3.3.The other flavor of spacing rule, touching illegal, prohibits types1 and types2 frombeing immediatelyadjacent. This rule separatestypes1 and types2 from each other. touch-ing illegalis less frequently usedbecauseit is less significant thantouching ok, thus onlya brief explanationis provided here.3.2.4 ExtractThe extract section of a technology file provides the parametersused by Magic’s circuitextractor. A keyword in the beginningof each line specifiesthe remainderof the line. Table3.4 is a sampleextract sectionin a Magic technologyfile.The keywords areacapand perimcapdefine the capacitanceto substrate,and resistidentifies the sheet resistivity of each Magic layers. Their formats are followed by a list oftypes and a value respect to substrate,as follows:areacaptypes Cperimcintypes outtypes Cresisttypes Rwhere the C is in attofaradsper square lambda and R is in milliohmsper square. Once anextractionis performed,substratecapacitanceandsheetresistanceare outputin the output‘ext’ file in the node section(see Table 3.5).42Chapter3. ExistingCapacitance Extraction Model of MagicTable 3.4: Extractsection.extractstyle lambda=1.0lambda 100step 100sidehalo 6areacap poly 33areacap metal1 17areacap metal2 11perimc poly 80perimc metal1 41overlap metal1 poly 30overlap metal2 metal1 45overlap metal2 poly 19sidewall poly 15sidewall metal1 27sidewall metal2 33sideoverlap metal1 poly 41sideoverlap metal2 metal1 42sideoverlap metal2 poly 22resist poly 25resist metal1 60resist metal2 40endMagic also extractsinternodal couplingcapacitances,which involve keywords overlap,sidewall, sideoverlap, and sidehaloto provide the parametersto performthe task.Overlap capacitanceexists between two pairs of tile types when they overlap, and it isdescribed as the following:overlaptoptypes bottomtypes capMagic’s extractorsearches for tiles in toptypes that overlap tiles in bottomtypes. When an43Chapter3. ExistingCapacitance Extraction Model of Magicoverlapareais searched,the capacitanceto substratein types toptypes is deductedandthenreplacedby a capacitanceto types in bottomtypes.Sidewall, or parallel wire capacitance,is between pairs of edges of the same type in aclose separationdefinedby ‘sidehalo’parameteras follows:sidehalodistancesidewall intypes outtypes neartypes fartypes capSidehalo distance defines the threshold distance beyond which the effects of sidewall ca-pacitanceare neglected,and this method reduces the amount of searching time in Magic.The sidewall keyword is illustratedin Figure 3.9, where capacitanceapplies between tilestinsideand tfar. tfar fartypes neartypes outypes intypes tinside Figure 3.9: Sidewall technologyline description(adaptedfrom [19]).Sidewall overlap capacitancearises between materialon the inside of an edge and over-lappingmaterialof a different type, described as follows:sideoverlap intypes outytpes ovtypes cap44Chapter3. ExistingCapacitance Extraction Model of Magicwhere intypes are on the inside edge and outtypes are on the outside surface, and thatoverlapsa tile in ovtypes. The cap described in this sectionare all in attofaradsper lambdasquare.3.2.4.1 ResistanceMagic extracts a lumped resistancefor each node, rather than a point-to-point resistancebetween each pair of devices connectedto that node. The result is that all such point-to-point resistancesare approximatedby the worst-caseresistancebetween any two points inthat node [74].Node resistances are approximated rather than computed exactly by default. For anode comprised entirely of a single type of material, the node’s total perimeter and areaare computedby Magic [74]. Magic’sresistanceextractioncan be done with the command“extresist”.3.3 MagicCapacitanceExtractionThe databasein Magic makes circuit extractionalmost trivial. Magic uses the traditionalpattern-matchingmethodforcapacitanceextraction.Theextractordoesnotneedtoregisterlayers or infer the structureand type of transistorsand contacts; it only needs to traversethe tile structureand recordthe connectioninformation.ThisleadsMagicto becomea fastcircuitextractor.Magicextractsfour kinds of capacitances,and three of them are major couplingcapac-itances: overlap,sidewall, and sidewall overlap. A couplingcapacitanceis formedwhentwo45Chapter3. ExistingCapacitance Extraction Model of Magicdifferent layers overlapeach otheron the surfaceor edge,or whentwo of the samematerialsoverlap the edge within a certain distance defined in the technology file. In addition, theothercapacitanceis substratecapacitance.Each node has a correspondingsubstratecapac-itance respect to substrate. These values are computedin ‘ext’ file after a Magic layoutcircuitis extracted.3.3.1 Overlap CapacitanceExtractionOverlap capacitanceis the most straightforward of the three coupling capacitancecompo-nents. It is formedwhenoneconductoroverlapsanotherconductoron a different plane,andthey are not linked togetherin the same net. The following figure shows a simple exampleof overlap capacitancewith dashedlines indicatingthe minimum designof one λ unit. a b a b ly lx Coverlap(b,a) h (a) (b) Figure 3.10: Overlap capacitance.Figure 3.10 (a) shows the top view of the layout. The shaded area is the overlappingarea composed of lxand ly. Figure 3.10 (b) is the side view of the layout. The overlapcapacitanceis between conductora and b. The formula is well known as shown:Ca,b= epsilon1oepsilon1rAh= epsilon1lxlyh(3.1)46Chapter3. ExistingCapacitance Extraction Model of Magicwhere epsilon1 is the appropriatedielectriccoefficient of the volume separatingconductorsa andb, lxand lyare the horizontal and vertical rectangulardimensionsof the overlap area, andh is the dielectricthickness. In Magic,the formula could be simplifiedasCoverlapa,b= coefficient×A (3.2)where coefficient is definedand retrieved in technologyfile, and A is the overlap area. Thevalue of overlap capacitanceis accumulatedto the capacitancebetween the nets to which aand b belong and is outputin the ‘ext’ file.3.3.2 Sidewall CapacitanceExtractionSidewall capacitanceis formedwhen two adjacent conductorson the same level overlap onthe verticaledges. The following figure illustratesa simpleexample. a b a b ly lx Csidewal(a,b) (a)  (b)  Figure 3.11: Sidewall capacitance.Figure3.11 (a) shows the top viewof sidewall capacitancewithlxand lydetermination.Figure 3.11 (b) is the side view of sidewall capacitancebetween conductora and b. Magic47Chapter3. ExistingCapacitance Extraction Model of Magicuses a short-rangeformula as shown:Csidewalla,b= epsilon1lyhlx(3.3)and the formula could be simplifiedasCsidewalla,b= coefficient×LD(3.4)wherecoefficientis definedin the technologyfile, L is the lengthof the edge overlap,and Dis the distancebetween two conductors.Inaddition,thesidewallcapacitancecoefficient valueinMagic’stechnologyfileishalved,since Magic computessidewall capacitancetwice in its algorithms. In every plane, tiles arefoundby tilesearchingalgorithm. For each tile,Magiclooksfor sidewall capacitanceon fouredges of the rectangle. As a result, if a sidewall capacitanceis found, it will be found forthe secondtimein its correspondingtile. Thisleadsto two calculationsof the samesidewallcapacitance,and the coefficient parametersin the technologyfile need to be adjusted.In the Magic technology file, there is a parameternamed “sidehalo”to determinethefurthest distance D to have sidewall capacitancebetween conductors. This parameter isset to be a small number such as 6 by default. Any distance beyond that point will beconsideredzero capacitance,and sidewall capacitancewill not be extracted. Magicsearchesa short range on the outside of each edge for nearby parallel edges. The search is limitedto the sidehaloof a few units away from the originaledge becauseparalleledge capacitancedecreasesrapidlywith distance.48Chapter3. ExistingCapacitance Extraction Model of Magic Detected Not detected sidehalo Figure 3.12: Sidewall capacitance detection(adaptedfrom [19]).3.3.3 Sidewall Overlap CapacitanceExtractionSidewall overlap capacitanceariseswhenone verticaledge of a conductoroverlapsthe hori-zontalsurfaceofanotherconductoronadifferentplane. Magic’ssidewalloverlapcapacitanceestimateis unsophisticated.It does not accuratelycalculatefringingto finite-sizehorizontalsurfaceor account for shieldinginfluenceof nearby conductors. Moreover, if conductorsdonotoverlapor coincidewitheach other,Magicdoes notcalculatethesidewall overlapcapac-itance. The following figure shows three different examplesof sidewall overlap capacitancemodel in Magic.Figure 3.13 shows three different cases to account for sidewall overlap capacitanceinMagic. In Figure 3.13 (a), conductorb over conductora with edges overlappingsurfaceoneach other. Conductorb’s edge overlappingconductora’s surface is shown in Figure 3.13(b), and Figure3.13 (c) illustratesconductorb over conductora withoutedgesoverlapping.The formula used in Magic could be simplifiedas following:Csidewall−overlapa,b= coefficient×edge (3.5)49Chapter3. ExistingCapacitance Extraction Model of Magic a b a b b a b a b a b a ly (a) (b) (c) Figure 3.13: Sidewall overlap capacitance.ItisclearlyobservedthatMagicdoesnotaccountforfringingtofinite-sizehorizontalsurface;it only considersone lambda-size in estimatingsidewall overlap capacitance,which is sentto be completelyinaccuratewhen comparedto CUP models and OptEM in chapter 4. Inaddition,when two conductorsdo not overlap or coincidewith each other, Magic does notcalculatesidewalloverlapcapacitance(seeFigure3.13(c)). Thesidewalloverlapcapacitanceis proportionalto the lengthof the overlap edge.3.3.4 Substrate CapacitanceExtractionEvery node has a correspondingcapacitancerespect to substrate,and its value is computedin the ‘ext’ output file. The substrate capacitancecomputed in Magic is dependent ontwo factors: area and perimeter. In figure 3.14 (a), the substratecapacitanceof conductora is just its layout with respect to substrateas there is no shieldinglayer beneath it. Thesubstratecapacitanceof conductorb is the shaded layout because conductora is shielding50Chapter3. ExistingCapacitance Extraction Model of Magic a b a b Csubstrate(a) Csubstrate(b) Substrate Figure 3.14: Substratecapacitance.part of the layout of conductorb with respect to substrate.Csubstrateb= coefficient×area +coefficient×perimeter (3.6)3.4 MagicExtractionOutputAs mentioned in chapter 1, Magic is an interactive layout editing system for large-scaleMOS custom integrated circuits, and it creates a layout file with extension ‘mag’. Withthe ‘extract all’command,‘magic’files are extractedinto ‘extract’files. The circuitnetlist is then described in a text formatwith extension‘ext’, and this file can furtherbeconvertedto simulationfile formats,such as sim and spiceformats. Theopen sourceIRSIMsimulator can read in sim files and simulate the models of circuits. Spice files can also besimulatedwith similaropen sourcesoftware tools, such as ngspiceand hspice.51Chapter3. ExistingCapacitance Extraction Model of Magic3.4.1 ExtractionFileIn every ‘ext’ file, some standardinformationis listed, such as version, technology, style,scaleandresistclasses.Afterstandardinformation,eachsetofnodeandcouplingcapacitanceinformationis shown in the following format.Table 3.5: Node output.definition example unitNode name node“bottom layer” “a n8 28#primeprimeResistance 156 milliohmsSubstratecapacitance 21264 attoFaradLeft down corner(x) -8 λLeft down corner(y) 28 λLayer name pcNwell area 0 λ2Nwell perimeter 0 λPwell area 0 λ2Pwell perimeter 0 λPoly area 104 λ2Poly perimeter 60 λNwell area 0 λ2Nwell perimeter 0 λPwell area 0 λ2Pwell perimeter 0 λPoly area 0 λ2Poly perimeter 0 λMetal1area 328 λ2Metal1perimeter 180 λMetal2area 0 λ2Metal2perimeter 0 λMetal3area 0 λ2Metal3perimeter 0 λAndthe followingtableshows the couplingcapacitanceformatformedbetween any twocircuitnodes.52Chapter3. ExistingCapacitance Extraction Model of MagicTable 3.6: Couplingcapacitanceoutput.Cap ‘node one’ ‘node two’ Capacitancevalue (aF)cap “a 1 20#primeprime“a n8 28#primeprime31563.4.2 SimulationFileThere are plenty of simulation tools in the world to model the circuit. Simulations andanalysis do not perform what the circuit does, but it demonstrateswhat the model of thecircuitdoes.Two types of simulationfiles can be generatedfroman extractedfile by Magic: sim andspice. ‘Sim’ files work with the IRSIM simulator. SPICE is the most widely use circuitsimulator for detailed analysis of transistorlevel designs, and SPICE files work with verywell recognizedsimulators,such as Hspice,ngspice,and so on.Some applicationswith examplessimulatedin ngspiceare presented in Chapter5.3.5 SummaryThis chapter provides a brief explorationof the Magic VLSI layout tool, an open sourcetool that was originally developed at the University of California, Berkeley in 1983. It isshownthatMagicisanefficient hierarchicalcircuitextractorbecauseitusescorner-stitching,pattern-matching,andManhattandistance. Magic’sextractordemonstratescorner-stitchingis well-suitedfor use in a circuitextractor[19].Regarding Magic’s capacitance extraction, it is found that Magic calculates sidewalloverlap capacitance by a simple method; it does not calculate the fringing to finite-size53Chapter3. ExistingCapacitance Extraction Model of Magichorizontal surfaceor account for shieldinginfluenceof nearby conductor. In addition,side-wall capacitanceis computedin a short-rangeformula in Magic. As a result, to rectify thedeficienciesin Magic, CUP models were applied to Magic. The next chapter assesses theimplementation of CUP models and derivatives in Magic to improve the performance,thatis to increaseaccuracy, and computeprocess variationsensitivities.54Chapter4Integration of New Capacitive Modelinto MagicThischapterdescribestheimplementationofHILEX(HIerarchicalLayoutEXtractiontool)/CUPmodels in Magic with process variationsensitivity in capacitanceextraction.4.1 CUP modelsDigital Equipment Corp. developed proprietaryCAD software for layout extractioncalledHILEX/CUP, consistingof HILEX(roughlyequivalent to Magic)and CUP(roughlyequiv-alent to Magic’s parasitic capacitanceand resistance extractionalgorithms). These codeswere licensedto SimplexSolutionsInc. in 1995,wheretheyformedthe basisof the FireandIce interconnectphysical verificationsoftware, eventually acquiredby Cadence[67].HILEXreducedthelayoutgeometryinto baseelements or so calledtrapezoids,andthenthe transformationswere appliedto them to computethe capacitance. The transformation55Chapter4. Integration of New Capacitive Model into Magicwas necessary as capacitance models were extracted using 2-D simulations whereas theactual layout geometry was 3-D in nature. There were three components to estimate thecapacitanceof each trapezoid: area, lateral,and fringe capacitances.A descriptionof the capacitanceextractionprocedurein CUP is presented:• The layout obtainedfrom HILEXis flattenedand passedto CUP.• The layout geometryis dividedinto stripes.• Each stripe is fracturedinto elemental areas that consistof rectanglesor triangles.• Startingfrom the lowest level, capacitancefor each elemental area is calculated.Asmentionedearlier,thecapacitanceof interestat any node consistsof area,lateralandfringe capacitance(see Figure 4.1). In general,the interconnectcapacitanceat any node isgiven by the sum of all the capacitancecomponents.Ctotal=ΣCarea+ΣClateral+ΣCfringe(4.1)4.1.1 Area CapacitanceArea,or overlapin Magic,capacitanceis formedby the surfaceoverlapof two conductorsindifferent planes. Figure4.2showstheareacapacitancemodelincross-sectionalviewbetweenconductorsmetal 2 and metal 1 and between metal 1 and polysilicon,and the dimensionswidth(lx), thickness(t), and height (h) are labeled for reference. Lengthlyis into the page.Magicand CUPmodels use the sameequationto evaluateareacapacitance,the well-known56Chapter4. Integration of New Capacitive Model into Magic d      a Metal i Metal i+1 Metal i-1 Carea Cfringe Clateral Cfringe Carea b c Cfringe Cfringe Figure 4.1: Capacitanceconfiguration. Metal 2 Metal 1 t h Width (lx) Carea Carea Polysilicon Figure 4.2: Area capacitance.formula 3.1:Carea= epsilon1oepsilon1rAh= epsilon1lxlyh(4.2)where epsilon1 is the appropriatedielectricconstant. The interestingpart is to get the sensitivityof capacitanceextraction,so the derivatives of capacitanceformula are computedwith thefollowing formulae:57Chapter4. Integration of New Capacitive Model into Magic∂Carea∂x= epsilon1lyh;∂Carea∂ly= epsilon1lxh(4.3)The partial derivative with respect to x is just lytimes the coefficient (epsilon1h) in the Magictechnologyfile. Therefore,the derivative of area capacitanceis very straightforward.4.1.2 LateralCapacitanceThe lateral capacitance, or sidewall in Magic, is the coupling between two of the sameconductorswhen they are adjacent. An exampleof the lateral capacitancemodel is shownwith side view in Figure4.3. Metal 2 Metal 1 Cltr Polysilicon Separation (lx) Cltr Figure 4.3: Lateralcapacitance.The lateral capacitance depends on the length of the edge overlap, and the formulapresented in the CUP model is:Clateral=summationtextni=1Ai·Fil1l1(lx)·lylx·ly(4.4)58Chapter4. Integration of New Capacitive Model into MagicwhereFil1l1(lx)=a0+a1lx+a2lx2+a3lx3+a4lx4(4.5)whereAiis theareaof a regionwithinthelateralcapacitancerectanglewitha particularcombinationof upper and lower shadinglayers, i is the region number, n is the number ofshadingregions,lyis the length of edge parallelto the other, and lxis the separation. Thecoefficients are fitted to 2D numericalsimulations.Noticethat it is possibleto do process variationin MagicwithoutusingCUP formulae.However, the CUPformulaeshouldbe moreaccurate. Thederivative of Magic’sformula forsidewall capacitanceis shown below but not implemented:CMagicsidewall= epsilon1lyhlx⇒∂CMagicsidewall∂lx=−epsilon1lyhlx2(4.6)It is important to realize that lateral capacitancealso depends on the presenceof shadinglayers above and/or below the level of the two conductors, so separate sets of differentcoefficients were derived. Partially-shieldedcases are handledby an area-weighted average.A comprehensive figure illustratesthis procedure(see Figure4.4).It is observed that the lateral capacitancerectanglebetween two metal 1 conductorsisdividedinto separateregionsin Figure 4.4 (b). The area Aiof each region i is given by itslengthliand width di, and the sum of all the areas islxly=Σni=1Ai=Σni=1lidi(4.7)59Chapter4. Integration of New Capacitive Model into Magic 1 2 3 4 5 6 7 8 9 10 11 12 13 14 lx ly Poly Metal 1 Metal 1 Metal 3 Metal 2 (a) (b) d1 l1 Figure 4.4: Lateralcapacitanceschematic.Thecolorsindicatetherealedgesofinterestingsectiontoaccountforlateralcapacitance,andeach division with numbers labeled have a different set of shadinglayers above and below.The linewidthderivative of lateralcapacitancesis more complicatedthan area models.The lateralcapacitancein every regioncan now be expressedas:Clateralregion i=lidilxparenleftbigga0+a1lx+a2lx2+a3lx3+a4lx4parenrightbigg(4.8)withli·diequalto the area in Eq. 4.4. As a result,the linewidthderivative is computedas:∂Clateralregion i∂tmetal j=∂Ci∂di∂di∂tj+∂Ci∂li∂li∂tj+∂Ci∂lx∂lx∂tj(4.9)where j indicatesthe metal conductor,and the first term in each product are shown:∂Clateralregion i∂di=lilxparenleftbigga0+a1lx+a2lx2+a3lx3+a4lx4parenrightbigg(4.10)60Chapter4. Integration of New Capacitive Model into Magic∂Clateralregion i∂li=dilxparenleftbigga0+a1lx+a2lx2+a3lx3+a4lx4parenrightbigg(4.11)∂Clateralregion i∂lx= li·diparenleftbigg−a0lx2+−2a1lx3+−3a2lx4+−4a3lx5+−5a4lx6parenrightbigg(4.12)The secondfactor in each product in Eq. 4.9 is either a 0 or ±1, dependingon metal layerandshape. Each divisionhasa different setofshadinglayersabove andbelow. Apixel-basedsearch algorithmwas invented to perform the lateral and fringe capacitancecomputationsaccuratelyand is discussedin next section.4.1.3 Fringe CapacitanceIn earlier technologies prior to DSM technology, fringe capacitances could be neglectedbecausethey are very smallin termsof total capacitance.As the technologyscalesdown toDSM regime,fringe capacitanceis becomingincreasinglyimportant since the interconnectsare even closer than ever. Fringing becomes an important component, so it is necessaryto adjust the accuracy in order to compute the total capacitancecorrectly. As describedpreviously, fringe capacitanceis formedbetween the verticaledge of one conductorand thehorizontal surface of a second conductor above or below. Figure 4.5 illustrates the fringecapacitancefor the metal1conductorin the middlewith metal2and polysiliconconductorsin cross-sectionalview.61Chapter4. Integration of New Capacitive Model into Magic Metal 2 Metal 1 Polysilicon Cfrg Cfrg Cfrg Cfrg Figure 4.5: Fringe capacitance.The originalCUPformula for fringecapacitancerectifiedMagicsdeficienciesmentionedin Chapter3 by consideringfringingto finite areas:Cfringe= lyb0(e−b1x1−e−b1x2) (4.13)with coefficients b0, wherex1and x2are the distancesfrom the verticaledge of conductoratothenearandfaredgesofconductord (seeFigure4.6). Thesameapproach tohandlingthepresenceof shieldinglayers is appliedas in lateralcapacitance.Separatesets of coefficientswere fitted to account for shielding layers on above or below. With conductors a and doverlapped, x1is defined to be 0. The dotted line shows the rectangulararea which aretaken into account for fringe capacitancecomputation.62Chapter4. Integration of New Capacitive Model into Magic ly x1 x1=0 x2 x2 (a) (b) s s s s s s Figure 4.6: Lateralcapacitancebetween two layers.The CUP formula implemented in the present work also considersthe effect of a neigh-bouringconductorat distances to furtherimprove accuracyin the DSM regime.Cfringe= lybracketleftBiggb0+b1parenleftbig1+b2sparenrightbigb3parenleftbigg1−e−parenleftBigb4+xb5+s·b6parenrightBigparenrightbiggbracketrightBigg(4.14)In the limit x→+∞, for (b5+s·b6) > 0,Cfringe= lybracketleftBiggb0+b1parenleftbig1+b2sparenrightbigb3bracketrightBigg(4.15)63Chapter4. Integration of New Capacitive Model into MagicIn the limit s→+∞, x→+∞, for b6> 0 and b3>−1,Cfringe= ly·b0(4.16)The equation could be simplified if x or s approaches +∞. Eq. 4.15 is used to computefringing to substrate capacitanceas the distance is infinity. Eq. 4.16 is equivalent to theMagic model in having a single parameter and not taking into account the width of thehorizontal surface. xfar Poly Metal 1 Metal 1 Metal 3 Metal 2 xnear s (a) (b) Figure 4.7: Fringe capacitanceschematic.Figure4.7shows thetopandsideviewsof fringecapacitancemodels,andtheseparationof the sameconductorson the relevant edge is computed. If a conductoron the samemetallayer is not foundin the layout, s =+∞. Magicfringemodel is thus improved to the muchmore sophisticatedCUP fringemodel. The linewidthderivative of the CUP fringemodel is64Chapter4. Integration of New Capacitive Model into Magicgiven by∂Cfringe∂lmetal j=∂Cfringe∂s∂s∂lj+∂Cfringe∂x∂x∂lj(4.17)with the first factor in each product∂Cfringe∂s=−b1b6(b4+x)(b5+s·b6)2parenleftbig1+b2sparenrightbigb3parenleftBige−b4+xb5+s·b6parenrightBig+b1b2b3s2parenleftbig1+b2sparenrightbigb3+1parenleftBig1−e−b4+xb5+s·b6parenrightBig(4.18)∂Cfringe∂x=b1e−b4+xb5+s·b6(b5+s·b6)parenleftbig1+b2sparenrightbigb3(4.19)In the same way as for lateralcapacitance,the secondfactor in each product in Eq. 4.17 iseithera 0 or 1, andthepixel-basedsearch method is appliedto computefringingcapacitanceas well to minimizethe cost.4.1.4 Model FitAs discussed in chapter 2, CUP model coefficients are fitted to Field Solver results andgeneratedin Techgen, which uses the Levenberg-Marquardt(LM) method to fit the modelto the data. Thecurve fits to the fieldsolver resultsfiguresare plottedbelow for lateral(seeFigureF.1 to FigureF.3) and fringecapacitances(see FigureF.4 to FigureF.11) sinceareacapacitanceis straight-forward.Lateralcapacitanceshave a very accuratemodel fittingcurve as the lateralcapacitanceformula is not complicated. Lateral capacitancebetween three different levels on metal 1,2, and 3 is plottedseparatelywith different cases of shadinglayers.65Chapter4. Integration of New Capacitive Model into MagicFringe capacitancecurve fits provide a fairly good result for each case. There are morecasesin fringecapacitancebecausetwo parametersarespecifiedin theformula,s andx. Foreach case, a variationof s, separation,is applied and plotted. As separationof conductorsare furtherapart, the capacitancevalue is larger due to the less shieldinginfluence.4.2 Changesto MagicFile FormatsTheTechgenprogramwaswrittentogenerateCUPmodelsfitstoBEMfieldsolverresults. Itincludesfeaturessuch asanisotropicdielectriclayersandmultiplesetsofmaterialproperties.For example, both dielectric constants and thermal conductivity are included. Techgen’sresultsare used to modify existingMagic Technologyfiles as explainedhere.4.2.1 TechnologyFile ChangesSince new CUP models are implemented in Magic,some new parametersmust be includedin the technologyfile. Table 4.1 lists a set of new parameters,and they are loadedin whenMagicreadsthe technologyfile at startup. The extractedsectionof the technologyfile usedin this thesis is reproduced in Appendix D.4.2.2 New ExtractionOutputOnce a layout is finished,its parasiticcapacitanceis extractedto an outputfile for simula-tions. Sincederivatives are implemented in Magic,a newformatextractoutputfile needstobe generatedto writethe derivative information.Table4.2 shows the capacitancederivativearray implemented in Magic. ∂/∂L1and ∂/∂L2are linewidth derivatives. Two gradients66Chapter4. Integration of New Capacitive Model into MagicTable 4.1: New technologyparameters.parameter No. of coefficients new parameter No. of coefficientsareacap 1 CUPareacap 1sidewall 1 CUPsidewall 5sideoverlap 1 CUPsideoverlap 8resist 1 CUPresist 1cscale 1 CUPscale 1ExampleStandardMagicmodel statement:sideoverlap (m1,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc,pc,via)/m1∼(m1,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc,pc,via)/m1(m2,m2c,m3c,pad)/m213.27MagicCUP model statement:CUPsideoverlap (m1,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc,pc,via)/m1∼(m1,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc,pc,via)/m1(m2,m2c,m3c,pad)/m23.49874130.0683600.07495340.1247500.1016762.9155370.11248814.857140are presented for each layer, to handle coincident edges, as discussed in the next section.∂/∂t and ∂/∂h are thicknessandheight derivatives, andtheymay be implemented in futureprojects.The capacitancederivative array is addedto the end of every node and couplingcapac-itancein ‘ext’files. Simulators‘ext2sim’and ‘ext2spice’are also modifiedto read thederivatives aftereach capacitance.Theyoutputthe derivatives as comments in the sim andspice files. Typical examplesare shown in Appendix E.4.3 LinewidthVariationThereare many different types of process variations,and the focus in this research is on thelinewidthvariation. A figure is shown to explain the width expansionand reductionfor agiven a layout(seeFigure4.8). Supposean isometriclayoutis drawnwitheach gridshowingone λ unit. A width bloat by one λ would expandone λ in all widths. On the other hand,67Chapter4. Integration of New Capacitive Model into MagicTable 4.2: Capacitancederivative array.layer definition Magic/CUPcap [0]pwell ∂/∂L1[1]pwell ∂/∂L2[2]nwell ∂/∂L1[3]nwell ∂/∂L2[4]poly ∂/∂L1[5]poly ∂/∂L2[6]poly ∂/∂t [7]poly ∂/∂h [8]metal 1 ∂/∂L1[9]metal 1 ∂/∂L2[10]metal 1 ∂/∂t [11]metal 1 ∂/∂h [12]metal 2 ∂/∂L1[13]metal 2 ∂/∂L2[14]metal 2 ∂/∂t [15]metal 2 ∂/∂h [16]metal 3 ∂/∂L1[17]metal 3 ∂/∂L2[18]metal 3 ∂/∂t [19]metal 3 ∂/∂h [20]the shrinkingof one λ would reduce the layout by one λ. Of course, the variation in realfabricationis unpredictable,generallyonly a fractionof a λ unit, but the minimum designunitis one λ in Magic. Demonstrationsof bloatingandshrinkingin thisthesiswillthereforeall be shown in terms of whole λ units.Linewidthvariationon level i, ti, are consideredto be either shrinking (ti< 0), that isall real edges shift in the direction of the metal, or bloating (ti> 0), where all real edgesshift in the direction of dielectric. The set of linewidthvariations on all levels is given asvectort =(t1,t2,...).68Chapter4. Integration of New Capacitive Model into Magic Width bloated by 1 ! Width shrunk by 1 ! Figure 4.8: Linewidthvariation.4.4 AlgorithmsImplementationTo implement newextractionformulae(HILEX/CUPmodels),newmetalsearch algorithmsare invented and designed in Magic tool. That is, to include new data structuresfor newderivative informationand other physics, a significant modificationto Magic is necessary.To account for derivatives of capacitancesensitivity to variations,theinformationaboutthe layout planes that correspond to metal levels, and the types of edges around the rect-angular areas on which capacitanceis evaluated. The first change is the data structureofhash table which stores capacitancethroughoutMagic. OriginallyMagic only stores a realscalar capacitancevalue for each node-pair that has a coupling capacitance,but now thederivatives with respect to each metal layer need to be stored as well. Therefore, a 2-Dvectoris implemented to storethe capacitanceandtwo linewidthderivatives for every metallevel.69Chapter4. Integration of New Capacitive Model into MagicOnce the hash entry/tableis capableof storingthe 2-D matrix,the derivative informa-tion is ready to be implemented. The following sectionsdescribe the detaileddiscussionofreal and coincident edges and pixel-basedsearch algorithms.4.4.1 Real EdgesIn particular,edges may be real or unreal, and they may also be coincident, which will bediscussedin nextsubsection. A realedgeis an edgethatcorrespondsto a verticalconductorface. That is, the interestingedge in a given layout. For instance,Figure4.9 (a) illustratestwo overlapping conductorsX and Y on metal levels i and i-1, and the perimeter of thearea capacitancerectanglebetween X and Y composed by real edges is shown in (b).  (a)            (b) Y   i-1                         i             X              Figure 4.9: A samplelayout illustratingreal edges. (a) ConductorsX and Y on levels iand i-1. (b) The real edges of overlappingarea between X and Y.4.4.2 Coincident EdgesA coincident edge occurs when two or more real edgeson different levels coincidewith eachother. Insuch a scenario,realedgesmay be turnedintotwo ormoredifferent casesregardingthe treatment of bloatingand shrinkingon metallayers. The inclusionof coincident edge isinvented and presented to comprisea more accurateestimatein process variations.70Chapter4. Integration of New Capacitive Model into MagicIn the illustrationin Figure 4.10 (a), there are three overlappingconductorsU, V, andT on levels i+1, i, and i-1 respectively. ConsiderconductorV havinga coincident edgewithT on one edge. In this case, a distinctionmust be made between the handlingof bloatingand shrinking. In Figure 4.10 (b), conductors T’s edge is both real and coincident withV’s edge, and this case may be treated as default real edges for this layout. Figure 4.10(c) demonstrates when conductor V bloats, the area is reduced according to V, and realedges remain the same as the default. Another case is shown in Figure 4.10 (d), whereeither conductor V shrinks or conductor T shrinks. If V shrinks, the area is unaffected,whereas the areais reducedalongthe entire rectangularlengthif T shrinks. However, bothcases turn conductor T’s coincident edge, on the right side, to real edge. Consequently,  (a)     (b)    (c)    (d) i-1           T              i             V                       i+1     U Figure 4.10: A sample layout illustratingcoincident edges. (a) Three overlappingcon-ductors U, V, and T on metal levels i+1, i, and i-1, respectively. (b) The perimeter ofthe area capacitancerectangle between U and T consists of real edges. Conductor T’sedge is both real and coincident with V’s edge. (c) When level i bloats, the area is re-duced accordingto the length of the level i real edges. (d) When level i shrinks,the areacapacitanceis unaffected.separatebloatingand shrinkingderivatives for each layer are computedand storedwith theassumptionthat the other layer’s dimensionsremainconstant.71Chapter4. Integration of New Capacitive Model into MagicA newfunctionis writtento computetherealandcoincident edges,given two tilesalongwith coincident edges. A pseudo code is provided in Figure 4.11, and the C code can beobtainedin Appendix G.To beginwith,given two tilesand the areato search with,this extRealEdge()functiondeterminesthe real edges of the tiles in the given search area. First, it determinesif thearea is a vertical or horizontal segment. If the area is a vertical segment, it is easier toimplement the real edgesdue to the way tiles are defined. (A verticalsegment only involvesone tile). On the otherhand,if the area is a horizontal segment, it is harderto find the realedges for the tiles because there may be some tiles on the above or below attached to thehorizontal segment. A top or bottom walk is performedto take care of the unreal edges inthe algorithms.If the area is a normal rectangle, four sides: top, right, left, and bottom walks areperformed step by step. Once again, right and left side walks are easier to implementbecausethey are verticalsegments.An exampleof area capacitancereal edgeimplementationis providedin AppendixC. Itshows all cases for metal 3 over metal 2, metal 1 and polysilicon,and step by step solutionis illustrated.4.4.3 Pixel-basedSearch AlgorithmsIn order to calculate lateral and fringe capacitancesaccurately, a pixel-basedsearch algo-rithm is implemented to evaluate the capacitancemodel. A pixel corresponds to a squareof the minimum design unit λ. The presence of a conductor above or below is noted in72Chapter4. Integration of New Capacitive Model into Magic if (the search area is a vertical segment) {   if ( RIGHT/LEFT(tile_above/below) = segment )     compute the real edge for tile_above and tile_below; } else if (the search area is a horizontal segment) {   if (TOP(tile_below) = segment     walk thru TOP of tile_below and compute real/coincident edges   if (TOP(tile_above) = BOTOM(area)     walk thru TOP of tile_above and compute real/coincident edges   if (BOTOM(tile_below) = TOP(area)     walk thru BOTOM of tile_below and compute real/coincident edges   if (BOTOM(tile_above) = TOP(area)     walk thru BOTOM of tile_above and compute real/coincident edges } else /* the search area is a rectangle */ { /* TOP */   if ( TOP(tabove)>TOP(tbelow) & TOP(tbelow) = BOTOM(area) )     {     walk thru TOP of tile_below and compute real edge for tile_below;     }   else if ( TOP(tile_above) = TOP(area) )     {     compute real edges for tile_above;     if TOP(tile_above) = TOP(tile_below)     {        walk thru TOP of tile_below to compute coincident edges for tile_above/below;     }     walk thru TOP of tile_above;     subtract real edge of tile_above;     if ( TOP(tile_above) != TOP(tile_below) )       subtract coincident edge of tile_above;     if ( TOP(tile_above) = TOP(tile_below) )     {       walk thru TOP of tile_below and subtract real/coincident edges;       compute real_edge for tile_below;     }    }  /* RIGHT */   if ( RIGHT(tile_above)>RIGHT(tile_below) & RIGHT(tile_below) = RIGHT(area) )     {      walk thru RIGHT of tile_below and compute real/coincident edges for tile_below;     }   else if ( RIGHT(tile_above) = RIGHT(area) )     {     if ( RIGHT(tile_above) = RIGHT(tile_below) )       compute/subtract real/coincident edges for tile_above/below;       walk thru RIGHT of tile_above;     }  /* BOTOM */   folow the /*TOP*/ algorithms with oposite direction  /* LEFT */   folow the /*RIGHT*/ algorithms with oposite direction } Figure 4.11: extRealEdge()functionpseudocode.73Chapter4. Integration of New Capacitive Model into Magicevery pixelof the rectangle. Thederivatives are also calculatedwithrealedgesaccumulatedin the gradient data structure. Figure 4.12 shows a lateral capacitancesample layout withsensitivity extractionalgorithm.   i-1     E i  A i+1     D    i  B i+1 C (a) (b) Figure 4.12: Pixel-basedsearch algorithm.Figure4.12 (a) illustratesa samplelayout for lateralcapacitancebetween conductorsAand B on level i, with shielding conductorsC and D on level i + 1 and E on level i−1,and Figure4.12 (b) shows the rectangleon which lateralcapacitanceis calculated,showingλ-sized pixels.To account for fringe capacitance,a similar approach is applied to calculations. Onedifference is that each fringe capacitancerectanglehas a separatecapacitancewith respecttotheconductorabove orbelowineachpixel. Moreover,thereisamaximumsidedistancetocomputefringecapacitancein each conductor,andthe distanceto the edgeof a neighboringconductoron the same level is also consideredin every capacitancerectangle. The C codeis availablein Appendix G.74Chapter4. Integration of New Capacitive Model into Magic4.5 SummaryThis chapter first presents CUP models and then three main coupling capacitances: area,lateral,and fringe.CUP models have been implemented to improve Magic’s sidewall overlap capacitance.Magicis now able to calculatethe fringingto finite-sizehorizontal surfacesand account fornearby shielding conductors. Moreover, the CUP lateral capacitancemodel has improvedMagic’sshort-rangesidewall capacitanceextraction.Linewidth variations are implemented into Magic, and a new function is written tocalculaterealandcoincident edgesforderivative computationwhenevaluatingcapacitances.In thenextchapter,simulationsareperformedto demonstrateandvalidatetheCUPmodelsand linewidthprocess variationsensitivity.75Chapter5Simulationand EvaluationBefore the evaluation of process variation sensitivity is discussedfurther, a figure present-ing the abstract view of computer-aideddesign (CAD) flow in Magic before and after theproposed process is shown.Figure5.1(a)is theoriginalCADflow in Magic,which createstiletreesfromthelayout.Magiccomputesthe nominalcapacitancesand then lumpsC to node-pairsand storesthemin ‘ext’filesforsimulationsin SPICEor IRSIM.Figure5.1(b)showsthenewimplementedcapacitances,CUPmodels,withgradients,∇C. Someuser-specifiedprocessvariationvectorvectort is appliedto obtainvaried Cprime. A shell scriptis performedto mergeinformationto SPICEwirelistsprior to simulations.This chapter is divided into three parts: a capacitanceextractioncomparisonis madebetween Magic and a commercial tool, Space 3D from OptEM, to validate CUP modelcapacitancesvalues. Then linewidth process variation sensitivitiesare evaluated to deter-minethe accuracyof the derivative-basedmethod. Finallythe costof implemented method,76Chapter5. Simulationand Evaluationruntime, is discussed. Magic Layout Divided into tiles Calculate C on tiles alculate ! " on tiles Lump C and ! "C on tiles onto circuit node-pairs Magic extraction Spice file with extracted C and ! "C for each node-pair C and ! "C on tiles Tile tres Ext file with extracted C and ! "C for each node-pair Ext2spice C’=C+! "C*t Place ’ in wirelist Shel script SPICE wirelist with varied C’ Submodel coeficients Tile to node-pair mapping Variation t Spice wirelist Magic Layout Divided into tiles Calculate C on tiles Lump C on tiles onto circuit node-pairs Magic extraction Spice file with extracted C for each node-pair C on tiles Tile tres Ext file with extracted C for each node-pair Ext2spice Place C in wirelist Shel script SPICE wirelist with nominal C Submodel coeficients Tile to node-pair mapping Spice wirelist (a) (b) Figure 5.1: CAD flow.5.1 CapacitanceComparisonCapacitanceaccuracyis very important in the DSM technology. This makes the evaluationof CUP models very attractive. In this section,comparisonsare madebetween Magicusing77Chapter5. Simulationand EvaluationCUPmodelsandthestandardMagicmodels,andtheSpace3Dextractiontool fromOptEMfor the same technology.5.1.1 Space 3D - OptEMA circuit layout is designedand created in Space 3D, and then laid out again in Magic toperforman extractionto generatebothCUPandMagicnetlists. Thelayoutdrawn in Space3D is shown in Figure5.2.  CMF3X240  CMF6X240  CMF12X240  CMF3X240_1  CMF6X240_1  CMF12X240_1  CMS3X240_1  CMS6X240_1  CMS12X240_1  Figure 5.2: Space 3D layout.This layout is composed of nine pieces of metal layers, CMF3X240is a metal 1 con-ductor with dimension 3x240 λ2(width by length). CMF6X240 and CMF12X240 are 6and 12 λ wide respectively. A 3 λ distanceseparatesthese conductors. CMF3X2401 andCMS3X2401 are metal 1 and metal 2 layers overlapped exactly in superposition, and theremainingconductorsare also the same size and location. A 6 λ distance separatestheseconductorsfrom each other and CMF12X240. This circuit layout resulted in 27 separatecapacitancesin Space 3D, and the resultsare shown in the next section.78Chapter5. Simulationand Evaluation5.1.2 CapacitanceComparison ResultsThe capacitancevalueswith node namesand % errorare tabulatedin Table 5.1. Underthe‘CapacitanceLabel’ column, the ‘C’ section is the type of capacitanceextracted in CUPmodels,which onlyincludesarea,lateral,andfringecapacitances.SinceSpace3D is a BEMfield solver, it does not use these separatemodel types.Table 5.1: Capacitancecomparison.Capacitance Node1 Node2 Space 3D CUPC(fF) MagicC(fF)Label (C) C(fF) [% error] [% error]C1 (N/A) CMF3X240 CMF12X240 1.02 0 [-100%] 0 [-100%]C2 (N/A) CMS12X2401 CMS3X2401 1.02 0 [-100%] 0 [-100%]C3 (L) CMF12X240 CMF3X2401 8.28 9.4 [+13.57%] 6.7 [-19.05%]C4 (L) CMF3X240 CMF6X240 18.50 18.9 [+2.18%] 13.5 [-27.02%]C5 (L) CMF3X2401 CMF6X2401 7.54 9.4 [+24.73%] 6.7 [-11.10%]C6 (L) CMF6X240 CMF12X240 19.44 18.9 [-2.76%] 13.5 [-30.54%]C7 (L) CMF6X2401 CMF12X2401 7.65 9.4 [+22.91%] 6.7 [-12.39%]C8 (L) CMS12X2401 CMS6X2401 13.64 12.6 [-7.59%] 8.1 [-40.6%]C9 (L) CMS3X2401 CMS6X2401 12.77 12.6 [-1.34%] 8.1 [-36.58%]C10 (A) CMS12X2401 CMF12X2401 20.48 16.1 [-21.4%] 16.1 [-21.4%]C11 (A) CMF3X2401 CMS3X2401 6.89 4 [-41.91%] 4 [-41.91%]C12 (A) CMF6X2401 CMS6X2401 10.29 8.1 [-21.3%] 8.1 [-21.3%]C13 (F) CMS6X2401 CMF12X2401 1.87 1.5 [-19.59%] 0 [-100%]C14 (F) CMS3X2401 CMF6X2401 1.76 1.1 [-37.62%] 0 [-100%]C15 (F) CMF6X2401 CMS12X2401 1.84 1.4 [-23.92%] 0 [-100%]C16 (F) CMF12X240 CMS3X2401 5.86 1.3 [-77.82%] 0 [-100%]C17 (F) CMF12X240 CMS6X2401 0.66 0.2 [-69.85%] 0 [-100%]C18 (F) CMF3X2401 CMS6X2401 1.76 1 [-43.31%] 0 [-100%]C19 (A+F) CMF12X240 GND 28.41 27.6 [-2.84%] 21.5 [-24.31%]C20 (A+F) CMF12X2401 GND 33.17 38.1 [14.88%] 21.5 [-35.18%]C21 (A+F) CMF3X240 GND 19.33 17.5 [-9.49%] 5.4 [-72.07%]C22 (A+F) CMF3X2401 GND 13.28 14.2 [6.90%] 5.4 [-59.35%]C23 (A+F) CMF6X240 GND 17.98 12.7 [-29.35%] 10.8 [-39.92%]C24 (A+F) CMF6X2401 GND 18.22 19.9 [9.23%] 10.8 [-40.72%]C25 (A+F) CMS12X2401 GND 10.26 8.9 [-13.30%] 0 [-100%]C26 (A+F) CMS3X2401 GND 4.24 2.4 [-43.44%] 0 [-100%]C27 (A+F) CMS6X2401 GND 2.65 2.5 [-5.83%] 0 [-100%]Total 288.81 269.7 [-6.62%] 166.9 [-42.21%]*A=area,L=lateral,F=fringe,N/A=notavailableThecapacitancevaluesareplottedinFigure5.3withdifferentMagiccapacitancesectionson lateral, area, fringe, and area+fringe. For each point on the plot, CUP values have a79Chapter5. Simulationand Evaluationcloser point to Space 3D than Magic except for area and those ‘not available’capacitancesas they are one of limitationsdiscussedin Chapter6.Space 3D vs CUP vs Magic0.005.0010.0015.0020.0025.0030.0035.0040.00123456789101112131415161718192021222324252627Lateral AreaFringeArea+FringeCapacitance LabelCapacitance (fF)Space3DCUPMagicFigure 5.3: Capacitancecomparisonbetween Space 3D, CUP, and Magic.It is observed that lateralcapacitancehas the most accurateresultsin CUP models. Inarea capacitance,CUPand Magichave the samevaluessince they use the samecoefficientsandcomputationmethod. Thevaluesareall slightly lessthanSpace3D becauseMagicdoesnot evaluatethe verticaledgecapacitance,or co-facialcapacitance,between the overlappingareas. Fringecapacitancesextractedin CUPmodelsaresmallerthanSpace3Dmodels. Thereason for this is that, in Techgen, the fringe capacitanceis computedby subtractingtheareacapacitancefromthefield-solverstotalcapacitancefortheprimaryconductor.However,80Chapter5. Simulationand Evaluationthe overestimateof area capacitanceleads to an underestimateof fringe capacitance. Also,Magicis incapableof evaluatingfringeeffectsbetween the horizontal surfacesof conductors,which leads to the underestimation. However, the fringe capacitanceonly accounts for asmall portion of overall capacitanceand does not affect the overall capacitancemuch. Inaddition, it has been improved by a lot from Magic models, which does not compute thefringe capacitancein this case.Magic models have been replaced and improved by CUP models, and the accuracy ofthe totalcapacitancevalue has been improved from42.21% to 6.62 % errorin this examplelayout as comparedto Space 3D, which is taken as the true capacitance.5.2 LinewidthProcess Variation EvaluationTo validate the estimationof interconnectcapacitancesensitivity to linewidthvariation, asimple victim-aggressorcrosstalkconfigurationis presented. The focus of this sectionis onthe accuracyand effect of process variationssensitivity, and an applicationto the crosstalkproblemis implemented in Magic and simulatedin ngspice.5.2.1 CrosstalkAsa signalpropagatesina conductor,it may encountercorners,vias,tees,andconnectorsaswell as changesin couplingto the environment. Theseinstantaneouschangesin impedanceseenby thesignalcauseundesirablesignaleffectsinanothercircuit. Inaddition,neighboringconductorsmay induce unwanted signals on signal-carryingconductors. Such phenomenaare generallyreferredto as crosstalk [77].81Chapter5. Simulationand EvaluationWiththeshrinkingtechnology, higheraspectratioandreducedwiringpitcheshave madeitprogressivelymoredifficulttoanalyzecrosstalkofcoupledinterconnectconsideringprocessvariations. Thus, crosstalk has been recognized as the most critical signal integrity (SI)concern,andlikelypredeterminedtoplay a moreimportant roleinfuturescaledtechnologies[78, 79].A crosstalkconfigurationhas two signals: aggressorand victim(see Figure5.4). “Agresor” “Victim” Vdd Vout  Vcap net1 net2 R=1k! Figure 5.4: Crosstalkconfiguration.5.2.1.1 InterconnectA layout with two serpentine, highly-couplednets was createdalong with two straight cou-pling metal lines aside in Magic, and it is replicatedwith a 1 λ “bloat” on metal 1 (netsA and C), metal 2 (net B), and metal 3 (net D) to verify the accuracy of the linewidthvariationsensitivity extraction(see Figure5.5).Table 5.2 shows the comparison between the extracted C (e.g. 46.88 fF for nets A-gnd) and the estimatedCprime(e.g. 27.06 fF for nets B-gnd)capacitances,using the extractedgradients. Linewidthvariationgradients∇areformattedas ([t1> 0,t1< 0],[t2> 0,t2< 0])82Chapter5. Simulationand Evaluation        (a)         (b) Net A: Metal 1 highly coupled serpentine Net B: Metal 2 highly coupled serpentine Net C: Metal 1 horizontal straight line Net D: Metal 3 horizontal straight line Figure 5.5: Magicinterconnect layouts with nets A, C on metal1, B on metal2, and Don metal3. (a) Original,nominallinewidthlayout. (b) Layout withvectort=(1,1)bloatrelativeto nominallayout.83Chapter5. Simulationand Evaluationfor both nominaland bloatedlayouts. C extractedfrom bloatedlayout are to be comparedto estimatedCprime(varied)=C(nominal)+∇·vectort, withvectort =(a,b) for different process variationvectort. In this case,vectort is set to (1,0) (ie. metal 1 bloats, metal 2 is nominal width) or (0,1) fornominallayout. Capacitancesextractedfromthe bloatedlayout are likewisecomparedbackto nominalcapacitanceswith a shrinkingvectort.The gradients involving nets C-D have different “bloating”and “shrinking”derivativevalues because of the existenceof coincident edges between nets C and D. For instance, abloat of metal 1 will reduce the D-gnd capacitanceby 0.16 fF/λ because it increases theshielding area, and it will increase nets C-D (area) and A-C (lateral) as the overlap areaenlarges and the separationdistance shortens. However, a shrink in metal 1 will increaseD-gndcapacitanceby 0.162fF/λ and reduce C-D and A-C capacitancesby 0.30 fF/λ and1.09 fF/λ respectively. On the other hand, nets A-gnd and C-gnd capacitancesare notshieldedby any conductorand thereforelack coincident edges, hence the bloat and shrinkgradients are equal.The differencesbetween extractedand estimatedcapacitancevalues are evident in fourcases: area and lateral (Figure5.6), substratewith fringingeffect (Figure5.7), fringe (Fig-ure 5.8), and area with fringe (Figure 5.9). Extractedand estimatedcapacitancesare pre-sented in patternedand solid columns,respectively. The odd-number columnsfor each pairof nets demonstratesthe nominal-widthcapacitancecomparisonfor capacitanceextractedfromnominallayoutandestimatedfrombloatedlayout,andthecapacitancecomparisonforextractedbloatedlayout capacitancesare comparedwith estimatedbloated-linwidthcapac-itances estimatedfrom nominal layout in even-number columns. An error % is computed84Chapter5. Simulationand EvaluationTable 5.2: Extractedvs estimatedcapacitances.Nets NominalLayout BloatedLayout(C) C(fF) ∇C(fF/λ)vectort Cprime(fF) C(fF) ∇C(fF/λ)vectort Cprime(fF)Space3D Space3DA-gnd 46.88 {[31.30,31.30], 1 78.18 78.21 {[31.36,31.36], -1 46.85(A) n/a [0, 0]} 0 n/a [0, 0]} 0A-gnd 185 {[41.2, 41.2], 1 226.2 195 {[44.0, 44.0], -1 151(A+F) 140 [0, 0]} 0 159 [0, 0]} 0B-gnd 18.03 {[-0.17,-0.17], 0 27.06 27.06 {[-0.23,-0.23], 0 18.01(A) n/a [9.03, 9.03]} 1 n/a [9.05, 9.05]} -1B-gnd 22.9 {[-0.16,-0.16], 0 31.9 28.9 {[-0.23,-0.23], 0 19.8(A+F) 38.5 [9.03, 9.03]} 1 39.3 [9.05, 9.05]} -1C-gnd 3.98 {[2.05, 2.05], 1 6.03 6.06 {[2.11, 2.11], -1 3.95(A) n/a [0, 0]} 0 n/a [0, 0]} 0C-gnd 12.4 {[2.81, 2.81], 1 15.2 13.4 {[2.94, 2.94], -1 10.5(A+F) 12.3 [0, 0]} 0 14.0 [0, 0]} 0D-gnd 0.321 {[-0.16,-0.162], 0 0.486 0.497 {[-0.165,-0.165], 0 0.318(A) n/a [0.165,0.167]} 1 n/a [0.174,0.174]} -1D-gnd 1.07 {[-0.16,-0.162], 0 1.234 1.24 {[-0.165,-0.165], 0 1.07(A+F) 4.96 [0.165,0.167]} 1 5.39 [0.174,0.174]} -1A-C 3.34 {[3.27, 1.09], 1 6.61 6.45 {[9.40, 3.13], -1 3.32(L) 4.65 [0, 0]} 0 8.26 [0.026,0.008]} 0A-D 0.303 {[0.075,0.075], 0 0.369 0.386 {[0.096,0.096], 0 0.312(F) 0.675 [0.066,0.066]} 1 0.741 [0.074,0.074]} -1B-C 0.124 {[0.092,0.092], 0 0.195 0.213 {[0.145,0.145], 0 0.105(F) 1.34 [0.071,0.071]} 1 1.37 [0.108,0.108]} -1B-D 0.257 {[0.153,0.153], 1 0.410 0.440 {[0.233,0.233], -1 0.207(F) 3.94 [0.152,0.152]} 0 4.55 [0.236,0.236]} 0C-D 0.819 {[0.296,0.300], 1 1.115 1.018 {[0.277,0.277], -1 0.841(A+F) 1.61 [0.295,0.291]} 0 1.78 [0.304,0.304]} 0A-B 38.32 {[21.24,21.24], 0 55.62 55.51 {[28.00,28.00] 0 34.69(A+F) 94.8 [17.30,17.30]} 1 101 [20.82,20.82]} 1A-B 55.51 {[28.00,28.00], 1 83.51 79.06 {[34.17,34.17] -1 44.89(A+F) 101 [20.82,20.82]} 0 114 [27.95,27.95]} 0*A=area,L=lateral,F=fringe85Chapter5. Simulationand Evaluationon the top of each column. 0.1 1 10 100A-C (m1 bloated)D-gnd (m3 bloated)C-gnd (m1 bloated)B-gnd (m2 bloated)A-gnd (m1 bloated)Capacitance (fF)NetsExtracted vs Estimated Area and Lateral Capacitances0.064%0.038%0.11%0.00%0.75%0.50%0.93%1.2%0.60%2.48%Extracted CapacitanceEstimated CapacitanceFigure 5.6: Extractedvs estimatedarea and lateralcapacitances.From Figure5.6, it is observed that the average error for pure area capacitancesis verysmall (∼ 0.45%). In this case, the fringing to ground substrate capacitance is disabledbecause only pure area capacitanceis evaluated. Since there is no shading layer betweennets A,B,C,D-gnd,a very accurate result is computed. Lateral capacitancebetween netsA-C also shows a very accurateresult for both bloating and shrinking.In another case, the fringing to substrate is enabled. Figure 5.7 shows the averageerror % for area substratecapacitanceswith fringingeffect. It is shown that the estimatedcapacitancesare not as accurateas pure area capacitancein Figure 5.6, except for D-gnd,86Chapter5. Simulationand Evaluation 0.1 1 10 100D-gnd (m3 shrunk/bloated)C-gnd (m1 shrunk/bloated)B-gnd (m2 shrunk/bloated)A-gnd (m1 shrunk/bloated)Capacitance (fF)NetsExtracted vs Estimated Substrate Capacitances with Fringing18.4%16.0%17.5%10.4%15.3%13.4%0.01%0.40%Extracted CapacitanceEstimated CapacitanceFigure 5.7: Extractedvs estimatedsubstratecapacitanceswith fringing.in which the value is too small. Thisimpliesthe derivative of fringingcapacitancedecreasesthe overall performancefor the substratecapacitance.Pure fringe capacitancedoes not reveal a very accurateresult (see Figure5.8), but theaverage error % is still around 10%. The result varies depending on the layout dimensionitself. It is hard to predictthe fringe capacitancewith a very good result.For the nets that contain both area and fringe capacitances, results vary like fringecapacitancesincefringecapacitancedominatesareacapacitanceintheseexamples. However,the averageerror% is less thanpurefringecapacitance’s(∼7.8%). It gives a slightly betterresultbecausethe areacapacitanceplays an insignificant role between thesenets to balancethe error %.87Chapter5. Simulationand Evaluation 0.1 0.2 0.3 0.4 0.5B-D (m2 shrunk/bloated)B-C (m1 shrunk/bloated)A-D (m3 shrunk/bloated)Capacitance (fF)NetsExtracted vs Estimated Fringe Capacitances2.97%4.40%14.6%8.92%19.5%6.82%Extracted CapacitanceEstimated CapacitanceFigure 5.8: Extractedvs estimatedfringe capacitances.The accuracy of linewidth process variation sensitivity on three coupling capacitancescan be listed from highestto lowest: area, lateral,then fringe capacitance.5.2.2 CrosstalkSimulationResultsIn real fabrication, a bloat or shrink of λ is rather large. Since the derivatives for thenonlinear lateral and fringe models are first order, they are only strictly accurate at thenominallayout dimension. The extractedcapacitanceis only approximatedby the models,and the actualcapacitancesand its variationswill behave differently in real circuits.Thegraphof signalsin Figure5.10illustratescrosstalksensitivity to linewidthvariation.The outputwith nominallinewidthonly had a small glitch, but a 1 λ bloat on metal1 and88Chapter5. Simulationand Evaluation 0.1 1 10 100A-B (m2 bloated; m1 shrunk/bloated)A-B (m2 shrunk/bloated)C-D (m1 shrunk/bloated)Capacitance (fF)NetsExtracted vs Estimated Area + Fringe Capacitances2.69%9.53%9.45%0.18%5.63%19.1%Extracted CapacitanceEstimated CapacitanceFigure 5.9: Extractedvs estimatedarea + fringe capacitances.metal2 causeda glitch thatexceeds0.5Vdd. Thesensitivity informationis helpfulforlayoutdesignersto determinethe amount of variation necessaryto trigger this fault, or calculatethe functionalyield based on the foundryvariability information.Fromthesimulation,itisnoticedthatcrosstalkbecomesa seriousdifficulty inSI.Failureto meettargetedfrequenciesin productshashappenedto reduceproductyielddueto flawedcircuitbehavior in crosstalkaggravation. Sinceprocess variationshave an enormousimpacton the amount of crosstalk,circuitdesignersmust optimizedesignsto account for crosstalknoise [80].89Chapter5. Simulationand Evaluation-1 0 1 2 3 44003002001000Voltage (V)time (ns)Victim signals with and without process variationVcap without Process VariationVout without Process VariationVcap with Process VariationVout with Process VariationFigure 5.10: Victimsignalswith and withoutprocess variation.5.3 Runtime AnalysisAn analysison runtimeis simulatedin thissection. A ComplexProgrammableLogicDevice(CPLD),product-termbased, layout was used for analysiswith layout size 2224 x 2671 λ2(see Figure5.11).The runtime analysis is performed under different cases. Since the standard Magic90Chapter5. Simulationand Evaluationcapacitancemodel is alreadyimplemented in Magictool, it would be run for analysiseverytime. For CUP models, the area capacitance,lateral capacitance,and fringe capacitanceare run in two combinations: with and without derivatives. The results are tabulated inTable 5.3 with a check mark indicatingwhich analysiscases were enabled. It is found thatfringe capacitanceoccupies most of the runtime (73%) because it involves the pixel searchalgorithmon each of four sides in every tile with a certain distanceto look for, and it alsosearches for conductorson the planes above and below, which takes more runtime in theimplementation. However, no additionalmemory allocation is required in the pixel-basedsearch algorithm.Figure 5.11: CPLDlayout.91Chapter5. Simulationand EvaluationTable 5.3: Runtime record.CPLD(2224 x 2671 λ2)Magic CUP Space 3D Runtime∇C area lateral fringe (seconds)√1.85√ √ √17.2√ √16.9√ √ √15.7√ √11.1√ √ √72.3√ √54.2√ √ √ √ √100.6√118768System: SUSE Linux EnterpriseDesktop10Processor: AMD Athlon(tm)64x2 Dual Core Processor 3800+Memory: 2GBTheresultsare plottedin Figure5.12to show the percentageoccupationof each capaci-tancemodel. Amongall threecapacitancemodels,lateralcapacitanceaccounts for the leastand fringe capacitanceaccounts for the most runtime.Runtime Analysisother2%area13%lateral12%58%15%fringe73%otherarealateralfringe capacitancefringe derivativeFigure 5.12: Runtime analysis.The runtime analysiswas first performedin the layout shown in Figure5.2, and it tookexactlyfour minutes to extractthe circuitin Space3D whileit only took less thana second92Chapter5. Simulationand EvaluationforCUPmodelsinMagic. Fromthisexample,MagicwithCUPmodelsandprocessvariationextractedthe small layout shown in Figure5.2∼250X faster than Space 3D in overall.Space3Dtakesmuch longertimetoextractthesamecircuit. AccordingtoTable5.3, thetotalruntime for Magiccircuitextractionof CPLDwith standardmodels was 1.85 seconds,and with the CUP models including the derivative was 100.6 seconds. The CPLD circuitextractionexample was also run in Space 3D, and the runtime of the completeextractionwas 118768 seconds. This result concludes that the execution had proceeded for ∼1180XlongerthanMagicwithCUPmodels. If accurateresultscanbe obtainedusingCUPmodels,Magic could becomea standardVLSI layout tool.5.4 SummaryThis chapter first compares CUP models with the Space 3D extractiontool from OptEMfor capacitance evaluation and then performs linewidth process variation sensitivity in acrosstalk application. Magic has been improved to include CUP models with a certainbetterperformancein termsof capacitanceaccuracy. Moreover, it is notedthat area capac-itance linewidth process variation estimationhas the best result out of the three types ofcouplingcapacitanceswhile lateral also gives a good result, and crosstalkmust be reducedfor optimizationto minimize the possibility of false circuit behavior in a product. In ad-dition, the runtime analysis is presented to discuss the cost of methods implemented intoMagic,in which fringecapacitancesoccupiesthe most runtime. In next chapter,conclusionand future work are discussedto summarizethis thesis.93Chapter6Conclusionand Future Work6.1 ContributionsInthisthesis,Magicwasdescribedwithitsinternalstructures,anditscapacitanceextractionwasdetaileddiscussedwithequations. CUPmodelswereimplementedandfoundtobe muchmore accurate than the standard Magic models. Taking advantage of CUP capacitancemodels’accuracy, the sensitivity of linewidthprocessvariationon layout was examined,andapplied to an example of Magic layout with a crosstalkapplication. Results are discussedin next section.6.2 Interpretationof ResultsBased on the assumption that Space 3D results are the true solution, Magic has beenimproved by the additionof CUP models. In the exampleof Figure 5.2, total capacitance94Chapter6. Conclusionand Future Workestimatedby the standardMagicmodels had an error of 42.21 % with respect to the Space3D field solver results,but the CUP models had an error of 6.62 % in total capacitance.In linewidthprocess variationsensitivity, the pure area model provides a very accurateresult(within1%error),andlateralalsoprovidesagoodresult(within5%error)whilefringecapacitancehas a variousaccuracy(∼10-15%errorgenerally). Thereasonfor variousfringeand lateral capacitanceis the s variable. The derivative formula for separationvariable isnot accurate in terms of variation estimation in lateral and fringe capacitanceequations.On the other hand, the derivative formula for area capacitanceis straightforward, thus itslinewidthprocess variationsensitivity has a very accurateresult.Thereis always a costfor a betterperformance.In this project, as accuracyis improvedandprocessvariationsensitivity is implemented,thecostis theruntimeincircuitextraction.In exampleof Figure5.11, the runtime of CUP models is ∼55X slower than originalMagicmodel. And it will grow exponentially as the layout is larger. However, accuracy is moreimportant than runtime. If the accuracycould be improved within5% error in overall, thisMagictool will becomea betterand trustfulVLSIcircuitlayout tool as its runtime is muchfaster than commercialfield solvers.6.3 LimitationsMagic only considers2-D effects while Space 3D is a true 3-D capacitanceextractor,thusMagic could never be as accurateas Space 3D.Table 5.2 shows that there are two sets of capacitances that could not be found inMagic: C1 and C2. These are the capacitance models between two of the same kind of95Chapter6. Conclusionand Future Workmetallayers with a shieldingsame kind of metal layer foundin Space3D. In Magic’smetalsearch algorithm, this kind of capacitancecould not be found and therefore is computedwith a zero capacitance,resulting in a 100 % error. In addition, The area capacitanceisalways underestimatedin both the standard Magic and CUP capacitancemodels becausethe vertical edge capacitance is neglected between the overlapping areas in Magic’s 2Dmethod. Thesecapacitancemodels couldbe includedfor betterperformancein futureworkas discussedbelow.6.4 Future WorkSeveral areas for future work are discovered and described throughoutthe thesis, and theyare discussedbelow.6.4.1 Process VariationsTheprocessvariationimplementationin thisthesisis onlyfor linewidth. However, therearemore process variationparameters,as discussedin previouschapter, such as height, thick-ness, and inter-layer dielectricthickness. These variations could be implemented once theinformationis all given, and it will involve more complicatedformulae and data structures.6.4.2 CapacitanceModelsThe capacitancemodels introduced in this thesis include area (overlap in Magic terminol-ogy), lateral (sidewall in Magic), and fringe (sidewall overlap in Magic). However, these96Chapter6. Conclusionand Future Worktechniques may be extendedbeyond these models to include the capacitanceof more con-figurationsof metalsurfacerelevant to DSMinterconnect. In [7], parallel,cofacialand crosscapacitancemodels are introduced and thus their sensitivitiesto process variations couldalso be appliedin Magic.6.4.3 AccuracyLateral and fringe capacitances have been improved dramatically in CUP models overMagic’s unsophisticatedmodels. However, the accuracy for fringe capacitance is not asgood as lateral model, and it is underestimated. A possible reason is that there might bea systematic underestimationof the magnitude of the fringe capacitance in the Techgenfield solver. Althoughthe trendsof capacitancewith distanceare correct,the scale may bewrong.6.4.4 RuntimeThereare severalreasonsfor the increaseof runtimein extraction,which includesderivativeimplementation for all three couplingcapacitancemodels, and the pixel search algorithms.Since the pixel search algorithmis used to evaluate all couplingcapacitancemodels, a so-lution to reduce the runtime for the pixel search algorithmis proposed here: For each sideof edges to performpixel algorithm,insteadof searching pixel by pixel, the requiredarea issearched first along with conductorsand real edges. This method will requiremore compli-catedalgorithmsthanthe pixelalgorithm,but it will definitelyreduceruntimesignificantly.97Bibliography[1] R. H. J. M. Otten, “Global wires: harmful?,” InternationalSymposium on PhysicalDesign, pp. 104–109,1998.[2] M. Walker, “Modeling the Wiring of Deep SubmicronICs,” IEEE Spectrum, vol. 37,pp. 65–71,March 2000.[3] J. Cong and D. Pan, “InterconnectEstimationand Planningfor Deep SubmicronDe-signs,”Proceedings of 36th Design AutomationConference, pp. 507–510,1999.[4] M. Bachtold, M. Spasojevic,C. Lage,and P. Ljung,“A Systemfor Full-Chipand Crit-ical Net Parasitic Extraction for ULSI Interconnectsusing a Fast 3-D Field Solver,”IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,vol. 19, pp. 325–338,March 2000.[5] International Technology Roadmaps for Semiconductors Interconnect 2007http://www.itrs.net/Links/2007ITRS/Home2007.htm.[6] T. El-Moselhy and L. Daniel, “Stochastic Integral Equation Solver for EfficientVariation-Aware InterconnectExtraction,”45th ACM/IEEEDesign AutomationCon-ference (DAC), 2008., pp. 415–420,June 2008.[7] A. Labun, “RapidMethod to Account for Process Variationin Full-ChipCapacitanceExtraction,”IEEE Transactionson Computer-Aided Design of Integrated Circuits andSystems, vol. 23, pp. 941–951,June 2004.[8] Z. J. Lin,C. Spanos,L. Millor,andY. T. Lin,“Studyof CircuitSensitivity to Intercon-nect Variation,”2nd InternationalWorkshopon Statistical Metrology, pp. 28–31,June1997.[9] N. Lu, “Statisticaland CornerModelingof InterconnectResistanceand Capacitance,”IEEE 2006 Custom Intergrated Circuits Conference (CICC), pp. 853–856, September2006.[10] T. El-Moselhy, I. Elfadel, and D. Widiger, “Efficient Algorithmfor the Computationof On-chip CapacitanceSensitivitieswith respect to a Large Set of Parameters,”45thACM/IEEEDesign AutomationConference (DAC), 2008., pp. 906–911,June 2008.98Bibliography[11] R. Ananthakrishnaand S. Batterywala, “MoM- A Process Variationaware StatisticalCapacitanceExtractor,” 19th InternationalConference on VLSI Design, 2006. Heldjointly with 5th InternationalConference on Embedded Systems and Design., January2006.[12] B. Li, L.-S. Peh, and P. Patra, “Impact of Process and Temperature Variations onNetwork-on-ChipDesign Exploration,”IEEE InternationalSymposium on Networks-on-Chip, pp. 117–126,April 2008.[13] K. J. Kuhn,“ReducingVariationin AdvancedLogicTechnologies: Approaches to Pro-cess and Design for Manufacturability of NanoscaleCMOS,”IEEE InternationlElec-tronic Devices Meeting, pp. 471–474,December 2007.[14] F. Huebbers, A. Dasdan,andY. Ismail,“Computationof accurateinterconnectprocessparametervalues for performancecornersunder process variations,”43rd ACM/IEEEDesign AutomationConference, pp. 797–800,July 2006.[15] E. Acar, S. Nassif, Y. Liu, and L. Pileggi, “Assessment of True Worst Case CircuitPerformanceunderInterconnectParameterVariations,”2001InternationalSymposiumon Quality Electronic Design, pp. 431–436,2001.[16] G. Lopez, R. Murali, R. Sarvari, K. Bowman, J. Davis, and J. Meindl, “The Impactof Size Effects and Copper InternationalProcess Variationson the Maximum CriticalPathDelayofSingleandMulti-CoreMicroprocessors,”IEEEInternationalInterconnectTechnology Conference, pp. 40–42,June 2007.[17] A. Bansal, B. C. Paul, and K. Roy, “An AnalyticalFringe CapacitanceModel for In-terconnectsUsingConformalMapping,”IEEETransactionon Computer-Aided Designof Integrated Circuits and Systems, vol. 25, pp. 2765–2774,December 2006.[18] A. Mutlu, J. Le, R. Molina, and M. Celik, “Parametric Analysis to Determine Ac-curate Interconnect Extraction Corners for Design Performance,” 10th InternationalSymposium on Quality Electronic Design., vol. 0, pp. 419–423,2009.[19] W. S. Scottand J. K. Ousterhout,“Magic’sCircuitExtractor,”IEEE Designand Testof Computers, vol. 3, pp. 24–34,February1986.[20] H. Kitada, T. Suzuki, T. Kimura, H. Kudo, H. Ochimizu, S. Okano, A. Tsukune,S. Suda, S. Sakai, N. Ohtsuka, T. Tabira, T. Shirasu, M. Sakamoto, A. Matsuura,Y. Asada, and T. Nakamura, “The Influence of the Size Effect of Copper Intercon-nects on RC Delay Variability beyond 45nm Technology,” IEEE 2007 InternationalInterconnect Technology Conference, pp. 10–12,June 2007.[21] N.LuandJ. H.McCullen,“Enablement of Variation-AwareTiming: Treatment of Par-asiticResistanceandCapacitance,”8th InternationalSymposiumon QualityElectronicDesign, ISQED ’07., pp. 743–748,March 2007.99Bibliography[22] N. Nagaraj, W. Hunter, P. Chidambaram, T. Garibay, U. Narasimha, A. Hill, andH. Shichijo, “Impact of InterconnectTechnology Scaling on SOC Design Methodolo-gies,”Proceedings of the IEEE 2005 InternationalInterconnect Technology Conference,2005., pp. 71–73,June 2005.[23] V. Venkatraman and W. Burleson, “Impact of Process Variations on Multi-level Sig-naling for On-Chip Interconnects,” 18th International Conference on VLSI Design,pp. 362–367,January 2005.[24] V. Hoang, G. Doornbos, J. Michelon, A. Kumar, A. Nackaerts, and P. Christie,“Bal-ancing Resistance and Capacitanceof Signal Interconnectsfor Power Saving,” IEEE2007 InternationalInterconnect Technology Conference, pp. 126–128,June 2007.[25] R. Hoofman, J. Michelon, P. Bancken, R. Daamen, G. Verheijden, V. Arnal,O. Hinsinger,L. Gosset,A. Humbert, W. Besling,C. Goldberg, R. Fox, L. Michaelson,C. Guedj, J. Guillaumond,V. Jousseaume,L. Arnaud, D. Gravesteijn, J. Torres, andG. Passemard, “Reliability Challenges Accompanied with Interconnect DownscalingandUltraLow-KDielectrics,”Proceedingsof the IEEE2005 InternationalInterconnectTechnology Conference, 2005., pp. 85–87,June 2005.[26] T. Harada,A. Ueki,K. Tomita,K. Hashimoto,J. Shibata,H. Okamura, K. Yoshikawa,T. Iseki, M. Higashi, S. Maejima, K. Nomura, K. Goto, T. Shono, S. Muranaka,N. Torazawa, S. Hirao, M. Matsumoto,T. Sasaki, S. Matsumoto,S. Ogawa, M. Fuji-sawa, A. Ishii,M. Matsuura,andT. Ueda,“ExtremelyLow Keff(1.9)Cu Interconnectswith Air Gap FormedUsing SiOC,”IEEE 2007 InternationalInterconnect TechnologyConference, pp. 141–143,June 2007.[27] The NationalTechnologyRoadmapsfor Semiconductors(SIA)TechnologyNeeds1997Edition.[28] K. Banerjeeand A. Mehrotra,“Analysisof On-ChipInductanceEffects for DistributedRLC Interconnects,”IEEE Transactionson Computer-Aided Design of Integrated Cir-cuits and Systems, vol. 21, pp. 904–915,August2002.[29] T.-H. Chen, C. Luk, H. Kim, and C. Chung-PingChen, “INDUCTWISE:Inductance-Wise InterconnectSimulator and Extractor,”2002 IEEE/ACM InternationalConfer-ence on ComputerAided Design. ICCAD 2002., pp. 215–220,November 2002.[30] C. Luk, T.-H. Chen, and C.-P. Chen, “Frequency-Dependent ReluctanceExtraction,”Proceedings of the ASP-DAC 2004. Asia and South Pacific Design Automation Con-ference, 2004., pp. 793–798,January 2004.[31] K. Gala, V. Zolotov, R. Panda, B. Young, J. Wang, and D. Blaauw, “On-Chip In-ductanceModelingand Analysis,”Proceedings of 37th DesignAutomationConference,2000., pp. 63–68,2000.[32] M. Beattie and L. Pileggi, “Inductance101: Modeling and Extraction,”ProceedingsDesign AutomationConference, 2001., pp. 323–328,2001.100Bibliography[33] “Synopsys- Star-RCXT Datasheet,”2009. Availablefrom http://www.synopsys.com.[34] Y. Du and W. Dai, “Partial Reluctance Based Circuit Simulation Is Efficient andStable,” Proceedings of the 2005 conference on Asia South Pacific design automation,pp. 483–488,2005.[35] R. Jiang and C. Chung-PingChen, “SCORE:SPICECOmpatibleReluctanceExtrac-tion,” Proceedings Design Automationand Test in Europe Conference and Exhibition,2004., vol. 2, pp. 948–953,February2004.[36] A.Devgan,H.Ji,andW.Dai,“HowtoEfficientlyCaptureOn-ChipInductanceEffects:Introducinga New CircuitElement K,” 2000 IEEE/ACM InternationalConference onComputerAided Design. ICCAD-2000., pp. 150–155,2000.[37] W. Chang, “AnalyticalIC Metal-LineCapacitanceFormulas,” IEEE TransactionsonMicrowave Theory and Techniques, vol. 24, pp. 608–611,September 1976.[38] C. Yuan and T. Trick, “A Simple Formula for the Estimationof the CapacitanceofTwo-DimensionalInterconnectsinVLSICircuits,”IEEEElectron Device Letters, vol.3,pp. 391–393,December 1982.[39] T. Sakurai and K. Tamaru, “Simple Formulas for Two- and Three-DimensionalCa-pacitances,” IEEE Transactions on Electron Devices, vol. 30, pp. 183–185, February1983.[40] N. V. Meijs and J. T. Fokkema, “VLSI Circuit Reconstructionfrom Mask Topology,”Integration - The VLSI Journal, vol. 2, no. 2, pp. 85–119,1984.[41] E. Barke, “Line-to-GroundCapacitanceCalculationfor VLSI: A Comparison,”IEEETransactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 7,pp. 295–298,February1988.[42] Y. Le Coz and R. Iverson, “A Stochastic Algorithmfor High Speed CapacitanceEx-traction in Integrated Circuits,” Solid-State Electronics, vol. 35, no. 7, pp. 513–520,1992.[43] Y. Le CozandR. Iverson,“A High-SpeedCapacitanceExtractionAlgorithmfor Multi-Level VLSI Interconnects,”Proceedings of Eighth InternationalIEEE VLSI MultilevelInterconnection Conference, 1991., pp. 364–366,June 1991.[44] R. Iverson and Y. L. Coz, “A Floating Random-Walk Method for Efficient RC Ex-traction of Complex IC-Interconnect Structures,” Technical Proceedings of the 1998InternationalConference on Modeling and Simulation of Microsystems, pp. 117–121,1998.[45] “Magma- QuickCap Datasheet,”2006. Availablefrom http://www.magma-da.com.[46] “Synopsys-RaphaelNXTDatasheet,”2009.Availablefromhttp://www.synopsys.com.101Bibliography[47] A. Zemanian,R. Tewarson, C. Ju, and J. Jen, “Three-DimensionalCapacitanceCom-putations for VLSI/ULSI Interconnections,”IEEE Transactions on Computer-AidedDesign of Integrated Circuits and Systems, vol. 8, pp. 1319–1326,December 1989.[48] A. Seidl, H. Klose, M. Svoboda, J. Oberndorfer, and W. Rosner, “CAPCAL-A3-DCapacitanceSolver for Support of CAD Systems,”IEEE Transactionson Computer-Aided Design of Integrated Circuits and Systems, vol. 7, pp. 549–556,May 1988.[49] M. Mukai, T. Tatsumi,N. Nakauchi, T. Tobayashi,K. Koyama,Y. Komatsu,R. Bauer,G. Rieger, and S. Selberherr, “The Simulation System for Three-DimensionalCapaci-tanceandCurrent Density Calculationwitha UserFriendlyGUI,”Simulationof Semi-conductorDevices and Processes, vol. 6, pp. 151–154,September 1995.[50] A. van Genderen and N. van der Meiis, “Using Articulation Nodes to Improve theEfficiency of Finite-Element Based Resistance Extraction,” 33rd Design AutomationConference Proceedings 1996, pp. 758–763,June 1996.[51] R. Martins, W. Pyka, R. Sabelka, and S. Selberherr, “High-PrecisionInterconnectAnalysis,” IEEE Transactions on Computer-Aided Design of Integrated Circuits andSystems, vol. 17, pp. 1148–1159,November 1998.[52] “Ansoft - Maxwell Datasheet,”2009. Availablefrom http://www.ansoft.com.[53] “Synopsys- RaphaelDatasheet,”2006. Availablefrom http://www.synopsys.com.[54] J. Phillips and J. White, “A Precorrected-FFTMethod for ElectrostaticAnalysis ofComplicated3-D Structures,”IEEE Transactionson Computer-Aided Design of Inte-grated Circuits and Systems, vol. 16, pp. 1059–1072,October 1997.[55] Z.-Q.Ning,P. M.Dewilde,andF. L. Neerhoff, “CapacitanceCoefficients forVLSIMul-tilevel MetallizationLines,” IEEE Transactionson Electron Devices, vol. 34, pp. 644–649, March 1987.[56] “OptEM- Inspector User Manual, Space 3D,” 2008.[57] K. Nabors and J. White,“FastCap: A Multipole Cccelerated3-D CapacitanceExtrac-tion Program,” IEEE Transactions on Computer-Aided Design of Integrated Circuitsand Systems, vol. 10, pp. 1447–1459,November 1991.[58] W. Yu, Z. Wang, and J. Gu, “Fast CapacitanceExtraction of Actual 3-D VLSI In-terconnectsusing Quasi-MultipleMedium AcceleratedBEM,” IEEE Transactions onMicrowave Theory and Techniques, vol. 51, pp. 109–119,January 2003.[59] N. Shahbazi and H. Sarbazi-Azad,“Accelerating3-D CapacitanceExtractionin DeepSub-MicronVLSI Design using Vector/ParallelComputing,”InternationalConferenceon Parallel and Distributed Systems,2007, vol. 2, pp. 1–8, December 2007.102Bibliography[60] S. Kapur and D. Long, “IES3: A Fast Integral Equation Solver for Efficient 3-Dimensional Extraction,” IEEE/ACM International Conference on Computer-AidedDesign, 1997., pp. 448–455,November 1997.[61] W. Shi, J. Liu, N. Kakani, and T. Yu, “A Fast Hierarchical Algorithm for Three-DimensionalCapacitanceExtraction,”IEEE Transactionson Computer-Aided Designof Integrated Circuits and Systems, vol. 21, pp. 330–336,March 2002.[62] W. Shi, J. Liu, N. Kakani, and T. Yu, “A Fast Hierarchical Algorithmfor 3-D Capaci-tance Extraction,”Proceedings of Design AutomationConference, 1998., pp. 212–217,June 1998.[63] M. Beattie and L. Pileggi, “Error Bounds for Capacitance Extraction via WindowTechniques,”IEEE Transactionson Computer-Aided Designof Integrated Circuits andSystems, vol. 18, pp. 311–321,March 1999.[64] S. Kapur and D. Long, “Large-Scale Capacitance Calculation,” Proceedings of 37thDesign AutomationConference, 2000., pp. 744–749,2000.[65] W. Yu and Z. Wang, “EnhancedQMM-BEMSolver for Three-DimensionalMultiple-DielectricCapacitanceExtractionwithin the Finite Domain,” IEEE Transactions onMicrowave Theory and Techniques, vol. 52, pp. 560–566,February2004.[66] W. Ding and G. Wang, “An Efficient PreconditioningScheme for Fast HierarchicalMethod in 3-D CapacitanceExtractionof IC Interconnect,”7th InternationalConfer-ence on ASIC, 2007. ASICON’07., pp. 1190–1192,October 2007.[67] N. D. Arora,K. V. Raol, R. Schumann,and L. M. Richardson,“Modelingand Extrac-tion of InterconnectCapacitancesfor Multiplayer VLSI Circuits,”IEEE Transactionson Computer-Aided Designof Integrated Circuits and Systems, vol. 15, pp. 58–67,Jan-uary 1996.[68] U. Choudhury and A. Sangiovanni-Vincentelli, “AutomaticGeneration of AnalyticalModelsfor InterconnectCapacitances,”IEEETransactionson Computer-Aided Designof Integrated Circuits and Systems, vol. 14, pp. 470–480,April 1995.[69] S.-Y. Oh, W.-Y. Jung, J.-T. Kong, and K.-H. Lee, “Interconnect Modeling in DeepSubmicronDesign,”6th InternationalConference on VLSIand CAD,1999.ICVC ’99.,pp. 73–80,1999.[70] “CadenceQRC ExtractionDatasheet,”2008.Availablefromhttp://www.cadence.com.[71] “Mentor - CalibreLFD Datasheet,”2005. Availablefrom http://www.mentor.com.[72] “Magma-QuickCapNXDatasheet,”2008.Availablefromhttp://www.magma-da.com.[73] C. Wei, R. Barrington,J. Mautz, and T. Sarkar, “MulticonductorTransmission LinesIn MultilayeredDielectricMedia,”IEEETransactionson MicrowaveTheory and Tech-niques, vol. 32, pp. 439–450,April 1984.103Bibliography[74] T. Edwards, “Magic VLSI Layout Tool,” 2008. Available fromhttp://www.opencircuitdesign.com/magic/.[75] J. K. Ousterhout, G. T. Hamachi, R. N. Mayo, W. S. Scott, and G. S. Talor, “TheMagic VLSI Layout System,”IEEE Design and Test of Computers, vol. 2, pp. 19–30,January 1985.[76] J. K. Ousterhout, “Corner Stitching: A Data Structuring Technique for VLSI Lay-out Tools,” IEEE Transactionson Computer-Aided Design of Integrated Circuits andSystems, vol. 3, pp. 87–100,January 1984.[77] A. Kuo, A. Labun,N. Swart, and A. Ivanov, “CrosstalkTimingModel for High-SpeedInterconnectswith Impedance Discontinuity,” IEEE Workshopon Signal Propagationon Interconnects, 2007. SPI 2007., pp. 194–197,May 2007.[78] M. Martina and G. Masera, “A Statistical Model for Estimating the Effect of Pro-cess Variationson CrosstalkNoise,”Proceedings of the 2004 internaionalworkshoponSystem level interconnect prediction, pp. 115–120,February2004.[79] X. Li, J. Wang, W. Tang, and H. Wu, “Stochastic Analysis for Crosstalk Noise ofCoupled Interconnects with Process Variations,” IEEE International Conference onIntegrated Circuit Design and Technology and Tutorial,2008. ICICDT2008., pp. 289–292, June 2008.[80] A. Sinha, S. Nazarian, and T. Mak, “Simulating the Effects of Process Variations onCapacitive Crosstalk,” 13th IEEE International Conference on Electronics, Circuitsand Systems,2006. ICECS ’06., pp. 604–607,December 2006.104Appendices105Appendix AStack fileA.1 Createa Stack FileA stack file is createdto run in Techgen.----------------------------------------------------------------------------------.NAME AR=1.5SIO2! For Lambda=1um (AR=1.5 Eps=3.8 process).CONDUCTOR!number of conductors3!order layer min_spacing max_spacing width thickness max_dist1 PMT1 3 8 3 5 502 PMT2 3 8 4 6 303 PMT3 4 9 4 6 50.DIELECTRIC!num7!order NAME layer thickness e_x e_y1 Di1 1 5 3.8 3.82 Di2 1 4.5 3.8 3.83 Di3 2 6 3.8 3.84 Di4 2 6 3.8 3.85 Di5 3 6 3.8 3.86 Di6 3 6 3.8 3.87 Di7 4 4 3.8 3.8.PARAMS!number of parameters1Thermal12 1212 1212 1212 1212 1212 1212 12----------------------------------------------------------------------------------106A.2 Stack DiagramFigureA.1 shows the metal configurationfrom the stack file createdabove.substrateDielectric 4Dielectric 3Dielectric 2Dielectric 5Dielectric 6Dielectric 7Dielectric 1PMT 1PMT 2PMT 3Figure A.1: Metal configurationfrom the stack file.107Appendix BMagicTile Search AlgorithmThe following figure shows a sample of Magic tile search algorithms and is based on thepseudo code in figure 3.8. Tiles in alphabetical order indicatingthe tile search transition,and each arrow indicatesan actionafter a certainconditionis found. A B C D G E F H I L K J M . start LB RB BB TB Figure B.1: Magictile search algorithm.Given a rectangular area, Magic starts to search tiles one by one. This tile searchalgorithm finishes running completely in five while loops, and each loop is described indetailsbelow:108• Loop One: tp = ‘A’, tpnew= ‘RB’→tpnew= LB(tp)= ‘B’, tp = tpnew = ‘B’.• Loop Two: tp = ‘B’, tpnew = ‘C’, tp = tpnew = ‘C’ → a metal conductoris found,go to function.tpnew= ‘D’, tp = tpnew=‘D’, tpnew= ‘RB’→tpnew= LB(tp)= ‘E’, tp = tpnew= ‘E’, tpnew = ‘J’→tpnew = LB(tp)= ‘F’, tp = BL(tp)= ‘C’, tpnew = LB(tp)=‘F’, tp = BL(tp)= ‘B’, tp = LB(tp)= ‘F’.• Loop Three: tp = ‘F’, tpnew= ‘J’→tpnew= LB(tp)= ‘G’, tp = LB(tp)= ‘G’.• Loop Four: tp = ‘G’, tpnew = ‘H’, tp = tpnew = ‘H’→ a metal conductoris found,go to function.tpnew= ‘I’, tp = tpnew= ‘I’, tpnew= ‘J’, tp = tpnew= ‘J’→a metalconductorisfound,go to function.tpnew= ‘K’, tp = tpnew= ‘K’, tpnew= ‘RB’→tpnew= LB(tp)= ‘L’, tp = LB(tp)= ‘J’, tpnew= LB(tp)= ‘L’, tp = BL(tp)= ‘I’, tpnew= LB(tp)= ‘L’, tp = BL(tp)= ‘H’, tp = tpnew = ‘L’, tpnew = TR(tp) = ‘RB’→ tpnew = LB(tp) = ‘M’, tp =BL(tp)= ‘H’, tpnew= LB(tp)= ‘M’, tp = BL(tp)= ‘G’, tp = LB(tp)= ‘M’.• Loop Five: tp = ‘M’, tpnew= ‘RB’,→tpnew= LB(tp)= ‘BB’, tp = tpnew= ‘BB’.109Appendix CArea CapacitanceEdgeImplementationFigure C.1 shows the real edges in an area capacitance. Cases are shown for metal 3 overmetal 2, metal 3 over metal 1, and metal 3 over poly. The ‘+’ and ‘-’ signs are defined tocorrespond to its own color edges.A step-by-step descriptionis provided in the case of metal 3 overlappingmetal 1.• Metal 1 is found to be overlappingwith metal 3.• Computethe real edges for the overlappingarea between metal 1 and metal 3.• A shieldingmetal 2 layer is found in the overlappingarea.• Computethe real edges for the overlappingarea between metal 1 and metal 2.• Add the real edge of the shieldinglayer (metal2).• Subtractthe real edge for the bottom layer (metal1) shieldedby metal 2.110 Poly Metal 1 Metal 2 Metal 3 Metal 3 Metal 2 Metal 3 Metal 1 = Metal 3 Poly = Figure C.1: Area capacitanceedge computation.111Appendix DMagicTechnologyFile on ExtractionThe following contains the partial extraction section in the Magic technology file used inthis thesis.-------------------------------------------------------------------------------------------extract# Interconnect based on the lambda=0.5 style from the Magic scmos tech filestyle AR=1.5CUPcscale 1Thermalcscale 1ThermalCUPcscale1cscale 1lambda 100step 100sidehalo 20areacap (ndiff,nsd,ndc,nsc)/a0perimc (ndiff,nsd,ndc,nsc)/aspace,pwell 0areacap (pdiff,psd,pdc,psc)/a0perimc (pdiff,psd,pdc,psc)/aspace,nwell 0areacap (poly,pc)/a 11.21areacap cc/a,cap 11.21overlap (poly,pc)/a nwell,pwell 33.63areacap poly2,ec/a 11.21perimc (poly,pc)/a ~(poly,pc)/a 16.815sideoverlap (poly,pc)/a ~(poly,pc)/a nwell,pwell 50.44CUPareacap (m1,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc,pc,via)/m17.476870ThermalCUPareacap(m1,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc,pc,via)/m12.666667112Thermalareacap (m1,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc,pc,via)/m12.666667areacap (m1,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc,pc,via)/m17.476870overlap (m1,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc,pc,via)/m1nwell,pwell 0.1053(poly,pc)/a,(ndiff,pdiff,em,col,ppd,nnd,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc)/aoverlap (m1,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc,pc,via)/m1(ndiff,pdiff,em,col,ppd,nnd,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc)/a0.1053overlap (m1,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc,pc,via)/m1(poly,pc)/a 0.2106overlap (m1,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc,pc,via)/m1poly2,cap 0.243sideoverlap (m1,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc,pc,via)/m1~(m1,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc,pc,via)/m1nwell,pwell 2.97((poly,pc)/a,(ndiff,pdiff,em,col,ppd,nnd,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc)/a)sideoverlap (m1,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc,pc,via)/m1~(m1,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc,pc,via)/m1(ndiff,pdiff,em,col,ppd,nnd,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc)/a2.97sideoverlap (m1,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc,pc,via)/m1~(m1,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc,pc,via)/m1(poly,pc)/a 2.97CUPsideoverlap (m1,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc,pc,via)/m1~(m1,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc,pc,via)/m1(m2,m2c,m3c,pad)/m2-3.507350 30.106000 0.074497 40.455530 0.103507 2.906032 0.113898 14.857140ThermalCUPsideoverlap(m1,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc,pc,via)/m1~(m1,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc,pc,via)/m1(m2,m2c,m3c,pad)/m2-1.250622 10.743480 0.081591 37.003110 0.103311 2.904532 0.114126 14.857140Thermalsideoverlap(m1,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc,pc,via)/m1~(m1,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc,pc,via)/m1(m2,m2c,m3c,pad)/m20.976629sideoverlap (m1,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc,pc,via)/m1~(m1,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc,pc,via)/m1(m2,m2c,m3c,pad)/m213.267799CUPsideoverlap (m1,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc,pc,via)/m1~(m1,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc,pc,via)/m1(m3,m3c,pad)/m3-2.106622 12.042360 0.076343 32.146360 0.134950 11.066430 -0.275945 50.000000ThermalCUPsideoverlap(m1,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc,pc,via)/m1~(m1,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc,pc,via)/m1(m3,m3c,pad)/m3-0.751709 4.300820 0.096063 25.656080 0.136128 11.058780 -0.274670 50.000000Thermalsideoverlap(m1,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc,pc,via)/m1~(m1,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc,pc,via)/m1(m3,m3c,pad)/m31.193190sideoverlap (m1,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc,pc,via)/m1~(m1,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc,pc,via)/m1(m3,m3c,pad)/m322.447109CUPsidewall (m1,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc,pc,via)/m1~(m1,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc,pc,via)/m1~(m1,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc,pc,via)/m1(m1,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc,pc,via)/m1-14.011380 394.547900 -601.013900 988.395000 -698.710000ThermalCUPsidewall(m1,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc,pc,via)/m1~(m1,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc,pc,via)/m1~(m1,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc,pc,via)/m1(m1,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc,pc,via)/m1-4.997234 140.717600 -214.354800 352.516300 -249.198600Thermalsidewall(m1,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc,pc,via)/m1~(m1,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc,pc,via)/m1~(m1,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc,pc,via)/m1(m1,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc,pc,via)/m130.000000sidewall (m1,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc,pc,via)/m1113~(m1,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc,pc,via)/m1~(m1,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc,pc,via)/m1(m1,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc,pc,via)/m184.114805CUPareacap (m2,m2c,m3c,pad)/m22.170705ThermalCUPareacap(m2,m2c,m3c,pad)/m20.774193Thermalareacap (m2,m2c,m3c,pad)/m20.774193areacap (m2,m2c,m3c,pad)/m22.170705overlap (m2,m2c,m3c,pad)/m2nwell,pwell 0.03005 (poly,pc)/a,(m1,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc,pc,via)/m1,(ndiff,pdiff,em,col,ppd,nnd,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc)/aoverlap (m2,m2c,m3c,pad)/m2(ndiff,pdiff,em,col,ppd,nnd,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc)/a0.03005(m1,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc,pc,via)/m1overlap (m2,m2c,m3c,pad)/m2(poly,pc)/a 0.035073(m1,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc,pc,via)/m1overlap (m2,m2c,m3c,pad)/m2poly2 0.0324(m1,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc,pc,via)/m1CUPoverlap (m2,m2c,m3c,pad)/m2(m1,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc,pc,via)/m15.607653ThermalCUPoverlap(m2,m2c,m3c,pad)/m2(m1,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc,pc,via)/m15.607653Thermaloverlap (m2,m2c,m3c,pad)/m2(m1,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc,pc,via)/m15.607653overlap (m2,m2c,m3c,pad)/m2(m1,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc,pc,via)/m15.607653sideoverlap (m2,m2c,m3c,pad)/m2~(m2,m2c,m3c,pad)/m2nwell,pwell 1.98((m1,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc,pc,via)/m1,(poly,pc)/a,(ndiff,pdiff,em,col,ppd,nnd,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc)/a)sideoverlap (m2,m2c,m3c,pad)/m2~(m2,m2c,m3c,pad)/m2(ndiff,pdiff,em,col,ppd,nnd,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc)/a1.8(m1,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc,pc,via)/m1sideoverlap (m2,m2c,m3c,pad)/m2~(m2,m2c,m3c,pad)/m2(poly,pc)/a 1.98(m1,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc,pc,via)/m1CUPsideoverlap (m2,m2c,m3c,pad)/m2~(m2,m2c,m3c,pad)/m2(m1,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc,pc,via)/m1-6.003871 19.457710 0.069604 43.480850 -0.042962 3.750783 0.023243 30.000000ThermalCUPsideoverlap(m2,m2c,m3c,pad)/m2~(m2,m2c,m3c,pad)/m2(m1,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc,pc,via)/m1-1.566505 9.652053 0.086266 34.510350 0.042902 3.684667 0.031321 30.000000Thermalsideoverlap(m2,m2c,m3c,pad)/m2~(m2,m2c,m3c,pad)/m2(m1,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc,pc,via)/m10.976629sideoverlap (m2,m2c,m3c,pad)/m2~(m2,m2c,m3c,pad)/m2(m1,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc,pc,via)/m113.267799CUPsideoverlap (m2,m2c,m3c,pad)/m2~(m2,m2c,m3c,pad)/m2(m3,m3c,pad)/m3-3.376266 30.750130 0.076322 41.179970 0.007847 2.966524 0.084409 30.000000ThermalCUPsideoverlap(m2,m2c,m3c,pad)/m2~(m2,m2c,m3c,pad)/m2(m3,m3c,pad)/m3-1.663323 11.153050 0.060601 46.574010 0.219921 2.877683 0.091172 30.000000Thermalsideoverlap(m2,m2c,m3c,pad)/m2~(m2,m2c,m3c,pad)/m2(m3,m3c,pad)/m30.976629sideoverlap (m2,m2c,m3c,pad)/m2~(m2,m2c,m3c,pad)/m2(m3,m3c,pad)/m313.267799CUPsidewall (m2,m2c,m3c,pad)/m2~(m2,m2c,m3c,pad)/m2~(m2,m2c,m3c,pad)/m2114(m2,m2c,m3c,pad)/m2-5.301961 427.496300 -652.724900 1189.587000 -928.858800ThermalCUPsidewall(m2,m2c,m3c,pad)/m2~(m2,m2c,m3c,pad)/m2~(m2,m2c,m3c,pad)/m2(m2,m2c,m3c,pad)/m2-2.280283 153.747500 -235.337400 425.043000 -328.899500Thermalsidewall(m2,m2c,m3c,pad)/m2~(m2,m2c,m3c,pad)/m2~(m2,m2c,m3c,pad)/m2(m2,m2c,m3c,pad)/m236.000000sidewall (m2,m2c,m3c,pad)/m2~(m2,m2c,m3c,pad)/m2~(m2,m2c,m3c,pad)/m2(m2,m2c,m3c,pad)/m2100.937766CUPareacap (m3,m3c,pad)/m31.223488ThermalCUPareacap(m3,m3c,pad)/m30.436364Thermalareacap (m3,m3c,pad)/m30.436364areacap (m3,m3c,pad)/m31.223488overlap (m3,m3c,pad)/m3nwell,pwell 0.014013 (poly,pc)/a,(m1,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc,pc,via)/m1,(m2,m2c,m3c,pad)/m2,(ndiff,pdiff,em,col,ppd,nnd,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc)/aoverlap (m3,m3c,pad)/m3(ndiff,pdiff,em,col,ppd,nnd,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc)/a0.014013 (m1,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc,pc,via)/m1,(m2,m2c,m3c,pad)/m2overlap (m3,m3c,pad)/m3(poly,pc)/a 0.015066(m1,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc,pc,via)/m1,(m2,m2c,m3c,pad)/m2CUPoverlap (m3,m3c,pad)/m3(m1,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc,pc,via)/m11.869218 (m2,m2c,m3c,pad)/m2ThermalCUPoverlap(m3,m3c,pad)/m3(m1,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc,pc,via)/m11.869218 (m2,m2c,m3c,pad)/m2Thermaloverlap (m3,m3c,pad)/m3(m1,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc,pc,via)/m11.869218 (m2,m2c,m3c,pad)/m2overlap (m3,m3c,pad)/m3(m1,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc,pc,via)/m11.869218 (m2,m2c,m3c,pad)/m2CUPoverlap (m3,m3c,pad)/m3(m2,m2c,m3c,pad)/m25.607653ThermalCUPoverlap(m3,m3c,pad)/m3(m2,m2c,m3c,pad)/m25.607653Thermaloverlap (m3,m3c,pad)/m3(m2,m2c,m3c,pad)/m25.607653overlap (m3,m3c,pad)/m3(m2,m2c,m3c,pad)/m25.607653sideoverlap (m3,m3c,pad)/m3~(m3,m3c,pad)/m3nwell,pwell 1.53((ndiff,pdiff,em,col,ppd,nnd,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc)/a,(poly,pc)/a,(m1,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc,pc,via)/m1,(m2,m2c,m3c,pad)/m2)sideoverlap (m3,m3c,pad)/m3~(m3,m3c,pad)/m3(ndiff,pdiff,em,col,ppd,nnd,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc)/a1.53((m1,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc,pc,via)/m1,(m2,m2c,m3c,pad)/m2)sideoverlap (m3,m3c,pad)/m3~(m3,m3c,pad)/m3(poly,pc)/a 1.53((m1,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc,pc,via)/m1,(m2,m2c,m3c,pad)/m2)CUPsideoverlap (m3,m3c,pad)/m3~(m3,m3c,pad)/m3(m1,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc,pc,via)/m1-3.049528 9.633470 0.064389 42.184760 0.402869 13.609610 -0.364724 50.000000((m2,m2c,m3c,pad)/m2)ThermalCUPsideoverlap(m3,m3c,pad)/m3~(m3,m3c,pad)/m3(m1,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc,pc,via)/m1-0.979124 4.835686 0.061433 39.960010 0.442047 16.097220 -0.509733 50.000000((m2,m2c,m3c,pad)/m2)Thermalsideoverlap(m3,m3c,pad)/m3~(m3,m3c,pad)/m3(m1,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc,pc,via)/m11151.193190 ((m2,m2c,m3c,pad)/m2)sideoverlap (m3,m3c,pad)/m3~(m3,m3c,pad)/m3(m1,ndc,pdc,nwc,pwc,nbdc,capc,ec,clc,emc,pbc,pc,via)/m122.447109 ((m2,m2c,m3c,pad)/m2)CUPsideoverlap (m3,m3c,pad)/m3~(m3,m3c,pad)/m3(m2,m2c,m3c,pad)/m2-4.670860 21.080550 0.074197 58.957620 -0.511804 3.204557 0.089685 50.000000ThermalCUPsideoverlap(m3,m3c,pad)/m3~(m3,m3c,pad)/m3(m2,m2c,m3c,pad)/m2-1.379702 10.856200 0.074391 50.353130 -0.027483 3.639437 0.086175 50.000000Thermalsideoverlap(m3,m3c,pad)/m3~(m3,m3c,pad)/m3(m2,m2c,m3c,pad)/m20.976629sideoverlap (m3,m3c,pad)/m3~(m3,m3c,pad)/m3(m2,m2c,m3c,pad)/m213.267799CUPsidewall (m3,m3c,pad)/m3~(m3,m3c,pad)/m3~(m3,m3c,pad)/m3(m3,m3c,pad)/m3-3.591101 527.719200 -1355.391000 3383.379000 -3528.000000ThermalCUPsidewall(m3,m3c,pad)/m3~(m3,m3c,pad)/m3~(m3,m3c,pad)/m3(m3,m3c,pad)/m3-0.354863 180.661800 -455.155600 1150.623000 -1212.000000Thermalsidewall(m3,m3c,pad)/m3~(m3,m3c,pad)/m3~(m3,m3c,pad)/m3(m3,m3c,pad)/m336.000000sidewall (m3,m3c,pad)/m3~(m3,m3c,pad)/m3~(m3,m3c,pad)/m3(m3,m3c,pad)/m3100.937766device mosfet pfet pfet pdiff,pdc nwell Vdd! 204 450device mosfet nfet nfet ndiff,ndc pwell Gnd! 150 450device mosfet epfet epfet pdiff,pdc nwell Vdd! 204 450device mosfet enfet enfet ndiff,ndc pwell Gnd! 150 450device capacitor None cap,capc/a poly,pc 120 745device bjt npn pbase,pbc/a emit,emc/a nwell# resistances based on the non-specific 0.18 micron process# sample6m.tech at http://www.opencircuitdesign.com/magic/index.htmlfetresis nfet linear 8000fetresis pfet linear 8000fetresis nfet saturation 8000fetresis pfet saturation 8000fetresis enfet linear 8000fetresis epfet linear 8000fetresis enfet saturation 8000fetresis epfet saturation 8000CUPresist (ndiff,nsd,ndc/act,nsc/act)8000Thermalresist (ndiff,nsd,ndc/act,nsc/act)8000ThermalCUPresist(ndiff,nsd,ndc/act,nsc/act)8000resist (ndiff,nsd,ndc/act,nsc/act)8000CUPresist (pdiff,psd,pdc/act,psc/act)8000Thermalresist (pdiff,psd,pdc/act,psc/act)8000ThermalCUPresist(pdiff,psd,pdc/act,psc/act)8000resist (pdiff,psd,pdc/act,psc/act)8000CUPresist (poly,pc/act,pfet,nfet)7400Thermalresist (poly,pc/act,pfet,nfet)7400ThermalCUPresist(poly,pc/act,pfet,nfet)7400116resist (poly,pc/act,pfet,nfet)7400CUPresist poly2,ec/a,enfet,epfet,cap,capc/a,nffet,pffet,hnfet,hpfet7400Thermalresist poly2,ec/a,enfet,epfet,cap,capc/a,nffet,pffet,hnfet,hpfet7400ThermalCUPresistpoly2,ec/a,enfet,epfet,cap,capc/a,nffet,pffet,hnfet,hpfet7400resist poly2,ec/a,enfet,epfet,cap,capc/a,nffet,pffet,hnfet,hpfet7400CUPresist em,emc/a 7400Thermalresist em,emc/a 7400ThermalCUPresistem,emc/a 7400resist em,emc/a 7400CUPresist pbase,pbc/a 900000Thermalresist pbase,pbc/a 900000ThermalCUPresistpbase,pbc/a 900000resist pbase,pbc/a 900000CUPresist (metal1,m2c/metal1)110Thermalresist (metal1,m2c/metal1)110ThermalCUPresist(metal1,m2c/metal1)110resist (metal1,m2c/metal1)110CUPresist (metal2,via/m2,pad)80Thermalresist (metal2,via/m2,pad)80ThermalCUPresist(metal2,via/m2,pad)80resist (metal2,via/m2,pad)80CUPresist (metal3) 80Thermalresist (metal3) 80ThermalCUPresist(metal3) 80resist (metal3) 80CUPresist nwell 900000Thermalresist nwell 900000ThermalCUPresistnwell 900000resist nwell 900000contact pc 4 10000contact ec/a,capc/a 4 10000contact ndc,pdc,nsc,psc4 10000contact pdc/a,psc/a 4 10000contact m2c,m3c 4 6800planeorder implant 0planeorder well 1planeorder active 2planeorder metal1 3planeorder metal2 4planeorder metal3 5planeorder oxide 6end-------------------------------------------------------------------------------------------117Appendix EMagicOutputFilesThe following contains the output files (‘ext’ and ‘spice’) extracted from the MagicVLSI layout tool in layout Figure 5.5 (a). Gradients informationis shown in the end ofevery capacitancenode and is shown in the next line in this Appendix.E.1 Ext FileThefollowingis the ‘ext’file extracteddirectlyfroma layout in the MagicVLSIlayout tool.----------------------------------------------------------------------------------timestamp 1248734708version 7.5tech scmos_m3_L1.0AR1.5CUPstyle AR=1.5scale 1000 1 100resistclasses 8000 8000 7400 7400 7400 900000 110 80 80 900000#Node contains substrate gradient cap info in the endnode "D" 3 1070.75 -1 -7 m3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 524 270 0 00 0 0 0 0 0 0 0 -160 -162 0 0 0 0 0 0 167 165 0 0node "B" 42 22944.5 6 0 m2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 8412 4214 0 0 0 00 0 0 0 0 0 0 0 -156 -156 0 0 9030 9030 0 0 0 0 0 0node "C" 4 12405.2 -3 -9 m1 0 0 0 0 0 0 0 0 0 0 0 0 532 274 0 0 0 0 0 00 0 0 0 0 0 0 0 2810 2810 0 0 0 0 0 0 0 0 0 0node "A" 77 184628 0 0 m1 0 0 0 0 0 0 0 0 0 0 0 0 6270 4186 0 0 0 0 0 00 0 0 0 0 0 0 0 41184 41184 0 0 0 0 0 0 0 0 0 0cap "A" "D" 302.8970 0 0 0 0 0 0 0 75.1041 75.1041 0 0 0 0 0 0 66.0343 66.0343 0 0cap "D" "B" 256.9330 0 0 0 0 0 0 0 0 0 0 0 152.97 152.97 0 0 152.055 152.055 0 0cap "C" "A" 3335.280 0 0 0 0 0 0 0 3274.03 1091.34 0 0 0 0 0 0 0 0 0 0cap "C" "B" 123.9270 0 0 0 0 0 0 0 92.2553 92.2553 0 0 71.3081 71.3081 0 0 0 0 0 0cap "A" "B" 383171180 0 0 0 0 0 0 0 21248.6 21248.6 0 0 17301.4 17301.4 0 0 0 0 0 0cap "C" "D" 818.5530 0 0 0 0 0 0 0 296.284 300.022 0 0 0 0 0 0 295.03 291.292 0 0----------------------------------------------------------------------------------E.2 Spice FileThe following is the ‘spice’file converted from ext file in Magic.----------------------------------------------------------------------------------* SPICE3 file created from xtalk.ext - technology: scmos_m3_L1.0AR1.5CUP.option scale=1uC0 A D 0.3fF * 0 0 0 0 0 0 0 0 0.075104 0.075104 0 0 0 0 0 0 0.066034 0.066034 0 0C1 C B 0.1fF * 0 0 0 0 0 0 0 0 0.092255 0.092255 0 0 0.071308 0.071308 0 0 0 0 0 0C2 B D 0.3fF * 0 0 0 0 0 0 0 0 0 0 0 0 0.15297 0.15297 0 0 0.152055 0.152055 0 0C3 A B 38.3fF * 0 0 0 0 0 0 0 0 21.2486 21.2486 0 0 17.3014 17.3014 0 0 0 0 0 0C4 C D 0.8fF * 0 0 0 0 0 0 0 0 0.296284 0.300022 0 0 0 0 0 0 0.29503 0.291292 0 0C5 A C 3.3fF * 0 0 0 0 0 0 0 0 3.27403 1.09134 0 0 0 0 0 0 0 0 0 0C6 D GND 1.1fF **FLOATING 0 0 0 0 0 0 0 0 -0.16 -0.162 0 0 0 0 0 0 0.167 0.165 0 0C7 B GND 22.9fF **FLOATING 0 0 0 0 0 0 0 0 -0.156 -0.156 0 0 9.03 9.03 0 0 0 0 0 0C8 C GND 12.4fF **FLOATING 0 0 0 0 0 0 0 0 2.81 2.81 0 0 0 0 0 0 0 0 0 0C9 A GND 184.6fF **FLOATING 0 0 0 0 0 0 0 0 41.184 41.184 0 0 0 0 0 0 0 0 0 0----------------------------------------------------------------------------------E.3 Final Spice FileThe following is the final ‘spice’ file after runningthe shell script.----------------------------------------------------------------------------------*Process Variation t-vector: pw=0.0 nw=0.0 py=0.0 m1=1.0 m2=0.0 m3=0.0* SPICE3 file created from xtalk.ext - technology: scmos_m3_L1.0AR1.5CUP.option scale=1uC0 A D 0.38fFC1 C B 0.19fFC2 B D 0.30fFC3 A B 59.55fFC4 C D 1.10fFC5 A C 6.57fFC6 D GND 0.94fFC7 B GND 22.74fFC8 C GND 15.21fFC9 A GND 225.78fF----------------------------------------------------------------------------------119Appendix FModel Fit to Field SolverThe following figures show the curve fits to field solver results for lateral (Figure F.1 toFigureF.3) and fringe capacitances(FigureF.4 to FigureF.11).In the field solver, the first thing to deal with fringe capacitance is to subtract theparallel plate value for the area capacitance. However, since the parallel plate formulaassumesuniformelectricalflux concentration for the entire plate, it overestimatesthe truearea capacitance,which is reduced near the edges. The negative fringe flux for very smallfringe areas is thus made to be negative to compensate for the overestimationof the areacapacitance. It is an artificial and computationaleffect (see Figure F.4 to Figure F.11 atsmall λ).120Figure F.1: Lateralcapacitanceon metal 1 per λ.121Figure F.2: Lateralcapacitanceon metal 2 per λ.122Figure F.3: Lateralcapacitanceon metal 3 per λ.123Figure F.4: Fringe capacitancemetal 1 to metal 2 with substrateper λ.124Figure F.5: Fringe capacitancemetal 1 to metal 3 with substrateper λ.125Figure F.6: Fringe capacitancemetal 2 to metal 1 with metal 3 above per λ.126Figure F.7: Fringe capacitancemetal 2 to metal 1 with space above per λ.127Figure F.8: Fringe capacitancemetal 2 to metal 3 with substrateper λ.128Figure F.9: Fringe capacitancemetal 2 to metal 3 with metal 1 below per λ.129Figure F.10: Fringe capacitancemetal 3 to metal 1 with space above per λ.130Figure F.11: Fringe capacitancemetal 3 to metal 2 with space above per λ.131Appendix GMagicCodesThis Appendix contains the Magic codes for real/coincident edges and pixel-basedsearchalgorithmsG.1 Real and Coincident Edge AlgorithmsThe followingis the real and coincident algorithms,and this functionhas been used heavilythroughoutMagic.---------------------------------------------------------------------------------/* RealEdge() to calculate the real edge of tabove and tbelow */// re->a and re->b must be initialized to zero before entering this functionintextRealEdge(tile,re)Tile *tile;struct real_edge *re;{Rect b, b2, r;Tile *tCheck, *tCheck2;re->a[0] = re->a[1] = re->b[0] = re->b[1] = 0;if ( tile != NULL ){132re->tbelow = tile;if (re->tabove == NULL){TITORECT(tile, &r);GEOCLIP(&re->area,&r);re->tabove = tile;re->tbelow = tile;}}/* first define 4 sides to be re->a (tabove edge) or re->b (tbelow edge) *//* subtract the edge if same layer is connectd to tile *tabove and *tbelow */if ( re->area.r_xtop== re->area.r_xbot){// the segment is verticalif (RIGHT(re->tbelow)== re->area.r_xtop)re->b[0] += re->area.r_ytop- re->area.r_ybot;if (RIGHT(re->tabove)== re->area.r_xtop)re->a[0] += re->area.r_ytop- re->area.r_ybot;if (LEFT(re->tbelow)== re->area.r_xbot)re->b[0] += re->area.r_ytop- re->area.r_ybot;if (LEFT(re->tabove)== re->area.r_xbot)re->a[0] += re->area.r_ytop- re->area.r_ybot;}else if ( re->area.r_ytop== re->area.r_ybot){// the segment is horizontalif (TOP(re->tbelow)== re->area.r_ybot){re->b[0] += MIN(re->area.r_xtop,RIGHT(re->tabove))-MAX(re->area.r_xbot,LEFT(re->tabove));for (tCheck = RT(re->tbelow);RIGHT(tCheck) > re->area.r_xbot;tCheck = BL(tCheck)){if ( TiGetTypeExact(tCheck)!= TiGetTypeExact(re->tbelow))continue;if ( BOTTOM(tCheck) > re->area.r_ytop)continue;if ( LEFT(tCheck) >= re->area.r_xtop)continue;b.r_xbot = MAX(re->area.r_xbot,LEFT(tCheck));b.r_xtop = MIN(re->area.r_xtop,RIGHT(tCheck));re->b[0]-=(b.r_xtop- b.r_xbot);re->a[1]+=(b.r_xtop- b.r_xbot);}}if (TOP(re->tabove)== re->area.r_ybot)133{re->a[0] += MIN(re->area.r_xtop,RIGHT(re->tabove))-MAX(re->area.r_xbot,LEFT(re->tabove));for (tCheck = RT(re->tabove);RIGHT(tCheck) > re->area.r_xbot;tCheck = BL(tCheck)){if ( TiGetTypeExact(tCheck)!= TiGetTypeExact(re->tabove))continue;if ( BOTTOM(tCheck) > re->area.r_ytop)continue;if ( LEFT(tCheck) >= re->area.r_xtop)continue;b.r_xbot = MAX(re->area.r_xbot,LEFT(tCheck));b.r_xtop = MIN(re->area.r_xtop,RIGHT(tCheck));re->a[0]-=(b.r_xtop- b.r_xbot);re->b[1]+=(b.r_xtop- b.r_xbot);}}if (BOTTOM(re->tbelow)== re->area.r_ytop){re->b[0] += MIN(re->area.r_xtop,RIGHT(re->tabove))-MAX(re->area.r_xbot,LEFT(re->tabove));for (tCheck = LB(re->tbelow);LEFT(tCheck) < re->area.r_xtop;tCheck = TR(tCheck)){if ( TiGetTypeExact(tCheck)!= TiGetTypeExact(re->tbelow))continue;if ( TOP(tCheck) < re->area.r_ybot)continue;if ( RIGHT(tCheck) <= re->area.r_xbot)continue;b.r_xbot = MAX(re->area.r_xbot,LEFT(tCheck));b.r_xtop = MIN(re->area.r_xtop,RIGHT(tCheck));re->b[0]-=(b.r_xtop- b.r_xbot);re->a[1]+=(b.r_xtop- b.r_xbot);}}if (BOTTOM(re->tabove)== re->area.r_ytop){re->a[0] += MIN(re->area.r_xtop,RIGHT(re->tabove))-MAX(re->area.r_xbot,LEFT(re->tabove));for (tCheck = LB(re->tabove);LEFT(tCheck) < re->area.r_xtop;tCheck = TR(tCheck)){if ( TiGetTypeExact(tCheck)!= TiGetTypeExact(re->tabove))continue;if ( TOP(tCheck) < re->area.r_ybot)continue;if ( RIGHT(tCheck) <= re->area.r_xbot)continue;b.r_xbot = MAX(re->area.r_xbot,LEFT(tCheck));b.r_xtop = MIN(re->area.r_xtop,RIGHT(tCheck));re->a[0]-=(b.r_xtop- b.r_xbot);134re->b[1]+=(b.r_xtop- b.r_xbot);}}}else{/* Top */if (TOP(re->tabove)> TOP(re->tbelow)&& TOP(re->tbelow)== re->area.r_ytop){re->b[0]+=(re->area.r_xtop- re->area.r_xbot);re->b[1]+=(re->area.r_xtop- re->area.r_xbot);for (tCheck = RT(re->tbelow);RIGHT(tCheck) > re->area.r_xbot;tCheck = BL(tCheck)){// tCheck must be same as re->tbelowif ( TiGetTypeExact(tCheck)!= TiGetTypeExact(re->tbelow))continue;// BOTTOM(tCheck) can’t be higher than TOP(area)if ( BOTTOM(tCheck) > re->area.r_ytop)continue;// LEFT(tCheck) can’t be righter than RIGHT(area)if ( LEFT(tCheck) >= re->area.r_xtop)continue;// LEFT = most right of LEFT(area) and LEFT(tCheck)b.r_xbot = MAX(re->area.r_xbot,LEFT(tCheck));// RIGHT = most left of RIGHT(area) and RIGHT(tCheck)b.r_xtop = MIN(re->area.r_xtop,RIGHT(tCheck));re->b[0]-=(b.r_xtop- b.r_xbot);re->b[1]-=(b.r_xtop- b.r_xbot);}}else if ( TOP(re->tabove)== re->area.r_ytop){// tabove shrinks or tbelow bloatsre->a[0]+=(re->area.r_xtop- re->area.r_xbot);// tabove shrinks or tbelow bloatsre->a[1]+=(re->area.r_xtop- re->area.r_xbot);if (TOP(re->tabove)== TOP(re->tbelow)){// tbelow shrinks or tabove bloatsre->b[1]+=(re->area.r_xtop- re->area.r_xbot);// tabove shrinks or tbelow bloatsre->a[1]-=(re->area.r_xtop- re->area.r_xbot);for (tCheck2 = RT(re->tbelow);RIGHT(tCheck2) > re->area.r_xbot;tCheck2 = BL(tCheck2)){if ( TiGetTypeExact(tCheck2)!= TiGetTypeExact(re->tbelow))continue;if ( BOTTOM(tCheck2)> re->area.r_ytop)continue;135if ( LEFT(tCheck2) >= re->area.r_xtop)continue;if ( RIGHT(tCheck2) <= re->area.r_xbot||LEFT(tCheck2) >= re->area.r_xtop) continue;b2.r_xbot = MAX(re->area.r_xbot,LEFT(tCheck2));b2.r_xtop = MIN(re->area.r_xtop,RIGHT(tCheck2));re->b[1]-=(b2.r_xtop- b2.r_xbot);re->a[1]+=(b2.r_xtop- b2.r_xbot);}}for (tCheck = RT(re->tabove);RIGHT(tCheck) > re->area.r_xbot;tCheck = BL(tCheck)){// tCheck must be same as re->taboveif ( TiGetTypeExact(tCheck)!= TiGetTypeExact(re->tabove))continue;// BOTTOM(tCheck) can’t be higher than TOP(area)if ( BOTTOM(tCheck) > re->area.r_ytop) continue;// LEFT(tCheck) can’t be righter than RIGHT(area)if ( LEFT(tCheck) >= re->area.r_xtop)continue;b.r_xbot = MAX(re->area.r_xbot,LEFT(tCheck));b.r_xtop = MIN(re->area.r_xtop,RIGHT(tCheck));re->a[0]-=(b.r_xtop- b.r_xbot);if (TOP(re->tabove)!= TOP(re->tbelow))re->a[1]-=(b.r_xtop- b.r_xbot);if ( TOP(re->tabove)== TOP(re->tbelow)){for (tCheck2 = RT(re->tbelow);RIGHT(tCheck2) > b.r_xbot;tCheck2 = BL(tCheck2)){if ( TiGetTypeExact(tCheck2)!= TiGetTypeExact(re->tbelow))continue;if ( BOTTOM(tCheck2)> re->area.r_ytop)continue;if ( LEFT(tCheck2) >= b.r_xtop) continue;if ( RIGHT(tCheck2) <= b.r_xbot || LEFT(tCheck2) >= b.r_xtop)continue;b2.r_xbot = MAX(b.r_xbot,LEFT(tCheck2));b2.r_xtop = MIN(b.r_xtop,RIGHT(tCheck2));re->b[0]-=(b2.r_xtop- b2.r_xbot);re->a[1]-=(b2.r_xtop- b2.r_xbot);}re->b[0]+=(b.r_xtop- b.r_xbot);}}}/* Right */if (RIGHT(re->tabove)> RIGHT(re->tbelow)&&RIGHT(re->tbelow)== re->area.r_xtop)136{re->b[0]+=(re->area.r_ytop- re->area.r_ybot);re->b[1]+=(re->area.r_ytop- re->area.r_ybot);for (tCheck = TR(re->tbelow);TOP(tCheck) > re->area.r_ybot;tCheck = LB(tCheck)){if ( TiGetTypeExact(tCheck)!= TiGetTypeExact(re->tbelow))continue;if ( LEFT(tCheck) > re->area.r_xtop)continue;if ( BOTTOM(tCheck) >= re->area.r_ytop)continue;b.r_ybot = MAX(re->area.r_ybot,BOTTOM(tCheck));b.r_ytop = MIN(re->area.r_ytop,TOP(tCheck));re->b[0]-=(b.r_ytop- b.r_ybot);re->b[1]-=(b.r_ytop- b.r_ybot);}}else if (RIGHT(re->tabove)== re->area.r_xtop){re->a[0]+=(re->area.r_ytop- re->area.r_ybot);re->a[1]+=(re->area.r_ytop- re->area.r_ybot);if (RIGHT(re->tabove)== RIGHT(re->tbelow)){re->b[1]+=(re->area.r_ytop- re->area.r_ybot);re->a[1]-=(re->area.r_ytop- re->area.r_ybot);}for (tCheck = TR(re->tabove);TOP(tCheck) > re->area.r_ybot;tCheck = LB(tCheck)){if ( TiGetTypeExact(tCheck)!= TiGetTypeExact(re->tabove))continue;if ( LEFT(tCheck) > re->area.r_ytop)continue;if ( BOTTOM(tCheck) >= re->area.r_ytop)continue;b.r_ybot = MAX(re->area.r_ybot,BOTTOM(tCheck));b.r_ytop = MIN(re->area.r_ytop,TOP(tCheck));re->a[0]-=(b.r_ytop- b.r_ybot);re->a[1]-=(b.r_ytop- b.r_ybot);}}/* Bottom */if (BOTTOM(re->tabove)< BOTTOM(re->tbelow)&&BOTTOM(re->tbelow)== re->area.r_ybot){re->b[0]+=(re->area.r_xtop- re->area.r_xbot);re->b[1]+=(re->area.r_xtop- re->area.r_xbot);for (tCheck = LB(re->tbelow);LEFT(tCheck) < re->area.r_xtop;tCheck = TR(tCheck)){137if ( TiGetTypeExact(tCheck)!= TiGetTypeExact(re->tbelow))continue;if ( TOP(tCheck) < re->area.r_ybot)continue;if ( RIGHT(tCheck) <= re->area.r_xbot) continue;b.r_xbot = MAX(re->area.r_xbot,LEFT(tCheck));b.r_xtop = MIN(re->area.r_xtop,RIGHT(tCheck));re->b[0]-=(b.r_xtop- b.r_xbot);re->b[1]-=(b.r_xtop- b.r_xbot);}}else if ( BOTTOM(re->tabove)== re->area.r_ybot){re->a[0]+=(re->area.r_xtop- re->area.r_xbot);re->a[1]+=(re->area.r_xtop- re->area.r_xbot);if (BOTTOM(re->tabove)== BOTTOM(re->tbelow)){re->b[1]+=(re->area.r_xtop- re->area.r_xbot);re->a[1]-=(re->area.r_xtop- re->area.r_xbot);for (tCheck2 = LB(re->tbelow);LEFT(tCheck2) < re->area.r_xtop;tCheck2 = TR(tCheck2)){if ( TiGetTypeExact(tCheck2)!= TiGetTypeExact(re->tbelow))continue;if ( BOTTOM(tCheck2)> re->area.r_ybot)continue;if ( LEFT(tCheck2) >= re->area.r_xtop)continue;if ( RIGHT(tCheck2) <= re->area.r_xbot||LEFT(tCheck2) >= re->area.r_xtop) continue;b2.r_xbot = MAX(re->area.r_xbot,LEFT(tCheck2));b2.r_xtop = MIN(re->area.r_xtop,RIGHT(tCheck2));re->b[1]-=(b2.r_xtop- b2.r_xbot);re->a[1]+=(b2.r_xtop- b2.r_xbot);}}for (tCheck = LB(re->tabove);LEFT(tCheck) < re->area.r_xtop;tCheck = TR(tCheck)){if ( TiGetTypeExact(tCheck)!= TiGetTypeExact(re->tabove))continue;if ( TOP(tCheck) < re->area.r_ybot) continue;if ( RIGHT(tCheck) <= re->area.r_xbot) continue;b.r_xbot = MAX(re->area.r_xbot,LEFT(tCheck));b.r_xtop = MIN(re->area.r_xtop,RIGHT(tCheck));re->a[0]-=(b.r_xtop- b.r_xbot);if (BOTTOM(re->tabove)!= BOTTOM(re->tbelow))re->a[1]-=(b.r_xtop- b.r_xbot);if ( BOTTOM(re->tabove)== BOTTOM(re->tbelow)){138for (tCheck2 = LB(re->tbelow);LEFT(tCheck2) < b.r_xtop;tCheck2 = TR(tCheck2)){if ( TiGetTypeExact(tCheck2)!= TiGetTypeExact(re->tbelow))continue;if ( BOTTOM(tCheck2)> re->area.r_ybot)continue;if ( LEFT(tCheck2) >= b.r_xtop) continue;if ( RIGHT(tCheck2) <= b.r_xbot || LEFT(tCheck2) >= b.r_xtop)continue;b2.r_xbot = MAX(b.r_xbot,LEFT(tCheck2));b2.r_xtop = MIN(b.r_xtop,RIGHT(tCheck2));re->b[0]-=(b2.r_xtop- b2.r_xbot);re->a[1]-=(b2.r_xtop- b2.r_xbot);}re->b[0]+=(b.r_xtop- b.r_xbot);}}}/* Left */if (LEFT(re->tabove)< LEFT(re->tbelow)&&LEFT(re->tbelow)== re->area.r_xbot){re->b[0]+=(re->area.r_ytop- re->area.r_ybot);re->b[1]+=(re->area.r_ytop- re->area.r_ybot);for (tCheck = BL(re->tbelow);BOTTOM(tCheck) < re->area.r_ytop;tCheck = RT(tCheck)){if ( TiGetTypeExact(tCheck)!= TiGetTypeExact(re->tbelow))continue;if ( RIGHT(tCheck) < re->area.r_xbot)continue;if ( TOP(tCheck) <= re->area.r_ybot)continue;b.r_ybot = MAX(re->area.r_ybot,BOTTOM(tCheck));b.r_ytop = MIN(re->area.r_ytop,TOP(tCheck));re->b[0]-=(b.r_ytop- b.r_ybot);re->b[1]-=(b.r_ytop- b.r_ybot);}}else if ( LEFT(re->tabove)== re->area.r_xbot){re->a[0]+=(re->area.r_ytop- re->area.r_ybot);re->a[1]+=(re->area.r_ytop- re->area.r_ybot);if (LEFT(re->tabove)== LEFT(re->tbelow)){re->b[1]+=(re->area.r_ytop- re->area.r_ybot);re->a[1]-=(re->area.r_ytop- re->area.r_ybot);}for (tCheck = BL(re->tabove);BOTTOM(tCheck) < re->area.r_ytop;139tCheck = RT(tCheck)){if ( TiGetTypeExact(tCheck)!= TiGetTypeExact(re->tabove))continue;if ( RIGHT(tCheck) < re->area.r_ybot)continue;if ( TOP(tCheck) <= re->area.r_ybot)continue;b.r_ybot = MAX(re->area.r_ybot,BOTTOM(tCheck));b.r_ytop = MIN(re->area.r_ytop,TOP(tCheck));re->a[0]-=(b.r_ytop- b.r_ybot);re->a[1]-=(b.r_ytop- b.r_ybot);}}}return (0);}---------------------------------------------------------------------------------G.2 Pixel-BasedSearch AlgorithmsThe following shows the pixel-basedsearch algorithmsfor the right side of each tile. Left,top, and bottom sides could also be implemented similarly. The pixel search algorithmisused for lateral,fringe and substratecapacitancecomputations./** ----------------------------------------------------------------------------** extSideRight --** Searching to the right of the boundary ’bp’, we found the tile* ’tpfar’ which may lie on the far side of an edge to which the* edge bp->b_inside | bp->b_outside has sidewall coupling capacitance.** The pixel search algorithm is implemented to compute* lateral capacitance. Similar method is applied to* extSideTop, but not to extSideLeft and extSideBottom* to avoid twice computations.** Results: Returns 0 always.** ----------------------------------------------------------------------------*/int140extSideRight(tpfar,bp)Tile *tpfar;Boundary *bp;{NodeRegion *rinside = (NodeRegion *) extGetRegion(bp->b_inside);NodeRegion *rfar = (NodeRegion *) extGetRegion(tpfar);Tile *tpnear;//NKH: parameters addedint i, j, pNum, l_a, l_b, l_o, l_op, l_tp;Rect r, r2;struct real_edge se;Tile *above, *below, *tclose;if (rfar != (NodeRegion *) extUnInit && rfar != rinside){int sep = LEFT(tpfar) - bp->b_segment.r_xtop;int limit = MIN(bp->b_segment.r_ytop,TOP(tpfar));int start = MAX(bp->b_segment.r_ybot,BOTTOM(tpfar));for (tpnear = BL(tpfar); BOTTOM(tpnear) < limit; tpnear = RT(tpnear)){int overlap = MIN(TOP(tpnear),limit) - MAX(BOTTOM(tpnear),start);if (overlap > 0){extSideCommon(rinside,rfar, tpnear, tpfar, overlap, sep);tclose = tpnear;}}/* NKH: pixel version added */if (CAP_LATERAL){for (i=start;i<limit;i++){for(j=RIGHT(bp->b_inside);j<LEFT(tpfar);j++){above = below = NULL;l_a = l_b = l_op = l_tp = 0;r.r_ybot=i;r.r_ytop=i+1;r.r_xbot=j;r.r_xtop=j+1;r2.r_xbot=r.r_xbot-1;r2.r_xtop=r.r_xtop+1;r2.r_ybot=r.r_ybot-1;r2.r_ytop=r.r_ytop+1;se.tabove = tpfar;141se.tbelow = NULL;se.area = r;for (pNum = PL_TECHDEPBASE;pNum < DBNumPlanes; pNum++){if (PlaneMaskHasPlane(*bp->cd_pmask,pNum)){(void) DBSrPaintArea((Tile*) NULL,bp->cd_plane[pNum],&r, bp->cd_bmask,extRealEdge, (ClientData) &se);if (se.tbelow == NULL){se.tabove = NULL;(void) DBSrPaintArea((Tile*) NULL,bp->cd_plane[pNum],&r2, bp->cd_bmask,extRealEdge, (ClientData) &se);l_o=-1; // at -1 if shrinking}else l_o=1; // if overlapped, l_o = 1 for bloating//define the closest tile above and below for lateralif (se.tbelow != NULL){if ( TiGetTypeExact(se.tbelow)>TiGetTypeExact(bp->b_inside)){if (above !=NULL){if ( TiGetTypeExact(se.tbelow)<TiGetTypeExact(above)){l_a=0;above = se.tbelow;l_a+=l_o*MAX(se.b[0],se.b[1]);}else if (l_o == 1 && l_op != 1){l_a=0;above = se.tbelow;l_a+=l_o*MAX(se.b[0],se.b[1]);}}else{above = se.tbelow;l_a+=l_o*MAX(se.b[0],se.b[1]);}}if ( TiGetTypeExact(se.tbelow)<142TiGetTypeExact(bp->b_inside)){if (below !=NULL){if ( TiGetTypeExact(se.tbelow)>TiGetTypeExact(below)){l_b=0;below = se.tbelow;l_b+=l_o*MAX(se.b[0],se.b[1]);}}else{below = se.tbelow;l_b+=l_o*MAX(se.b[0],se.b[1]);}}}l_op = l_o;}}if ( j==RIGHT(bp->b_inside)|| j==LEFT(tpfar)-1) l_tp+=1;if ( i==start ) l_tp+=1;if ( i==limit-1 ) l_tp+=1;// go to lateral function if j is within regionextLateral(rinside,rfar, tclose, tpfar, above, l_a, below,l_b, sep, l_tp);}}}}return (0);}/** ----------------------------------------------------------------------------** extGndRight --** Searching the fringing to GND effects on the* right edge of each tile. Similar methods are applied to* extGndTop, extGndLeft, extGndBottom* to account for fringing effects on substrate capacitance** Results: Returns 0 always.*143* ----------------------------------------------------------------------------*/intextGndRight(esws)extSidewallStruct*esws;{NodeRegion *rsub = (NodeRegion *) extGetRegion(esws->bp->b_inside);int i, j, sep, pNum;Rect r;struct real_edge test;test.tabove = test.tbelow = esws->bp->b_inside;for (i=esws->bp->b_segment.r_ybot;i<esws->bp->b_segment.r_ytop;i++){for(j=RIGHT(esws->bp->b_inside)+edgeHalo;j>=RIGHT(esws->bp->b_inside);j--){r.r_ybot=i;r.r_ytop=i+1;r.r_xbot=j;r.r_xtop=j+1;test.area = r;for (pNum = PL_TECHDEPBASE;pNum < esws->plane_of_boundary;pNum++){(void) DBSrPaintArea((Tile*) NULL, esws->bp->cd_plane[pNum],&r, esws->bp->cd_bmask,extRealEdge, (ClientData) &test);}(void) DBSrPaintArea((Tile*) NULL,esws->bp->cd_plane[esws->plane_of_boundary],&r,esws->edge, extRealEdge, (ClientData) &test);}if (test.tbelow != esws->bp->b_inside)sep = LEFT(test.tbelow)- RIGHT(esws->bp->b_inside);else sep = edgeHalo;if (sep>0) AddGndCap(rsub,sep);}return(0);}/** ----------------------------------------------------------------------------** extSideOverRight--** Search fringe capacitance pixel by pixel on the right edge144* of each tile, similar methods are applied to* extSideOverTop,extSideOverLeft,extSideOverBottom* functions to account for fringe capacitance** Results: Returns 0 always.** ----------------------------------------------------------------------------*/intextSideOverRight(esws)extSidewallStruct*esws; /* Overlapping edge and plane information */{int pNum, i, j, sep, l_a, l_b, l_p, side, side_x;Rect r;struct real_edge se, test;Tile *above, *below;test.tabove = test.tbelow = esws->bp->b_inside;/*NKH: pixel version added*/for (i=esws->bp->b_segment.r_ybot;i<esws->bp->b_segment.r_ytop;i++){for(j=RIGHT(esws->bp->b_inside)+sideHalo;j>=RIGHT(esws->bp->b_inside);j--){r.r_ybot=i;r.r_ytop=i+1;r.r_xbot=j;r.r_xtop=j+1;test.area = r;(void) DBSrPaintArea((Tile*) NULL,esws->bp->cd_plane[esws->plane_of_boundary],&r,esws->edge, extRealEdge, (ClientData) &test);}if (test.tbelow != esws->bp->b_inside)sep = LEFT(test.tbelow)- RIGHT(esws->bp->b_inside);else sep = 0;if (sep!=0) side_x=sep;else side_x=sideHalo;for(j=RIGHT(esws->bp->b_inside);j<RIGHT(esws->bp->b_inside)+sideHalo;j++){above = below = NULL;l_a = l_b = l_p = side = 0;r.r_ybot=i;r.r_ytop=i+1;r.r_xbot=j;r.r_xtop=j+1;se.tabove = se.tbelow = esws->bp->b_inside;145se.area = r;for (pNum = PL_TECHDEPBASE;pNum < DBNumPlanes; pNum++){if (PlaneMaskHasPlane(*esws->bp->cd_pmask,pNum)){esws->plane_checked= pNum;(void) DBSrPaintArea((Tile*) NULL, esws->bp->cd_plane[pNum],&r, esws->bp->cd_bmask,extRealEdge, (ClientData) &se);}/* define the closest tile above and below for fringe */if (TiGetTypeExact(se.tbelow)>TiGetTypeExact(esws->bp->b_inside)){if (above == NULL){above = se.tbelow;l_a+=MAX(se.b[0],se.b[1]);}elseif ( TiGetTypeExact(se.tbelow)<TiGetTypeExact(above)){above = se.tbelow;l_a+=MAX(se.b[0],se.b[1]);}}if (TiGetTypeExact(se.tbelow)<TiGetTypeExact(esws->bp->b_inside)){if (below == NULL){below = se.tbelow;l_b+=MAX(se.b[0],se.b[1]);}elseif ( TiGetTypeExact(se.tbelow)>TiGetTypeExact(below)){below = se.tbelow;l_b+=MAX(se.b[0],se.b[1]);}}}if (above != NULL){if (r.r_ytop==TOP(esws->bp->b_inside)&&r.r_ytop==TOP(above))l_a-=1;else if (r.r_ytop==TOP(esws->bp->b_inside)&&r.r_ytop<TOP(above))l_a+=1;if (r.r_ybot==BOTTOM(esws->bp->b_inside)&&r.r_ybot==BOTTOM(above))146l_a-=1;else if (r.r_ybot==BOTTOM(esws->bp->b_inside)&&r.r_ybot>BOTTOM(above)) l_a+=1;if (r.r_ytop==TOP(esws->bp->b_inside)&&r.r_ytop<TOP(above))l_p=1;if (r.r_ybot==BOTTOM(esws->bp->b_inside)&&r.r_ybot>BOTTOM(above))l_p=1;if (j==LEFT(above)|| j==RIGHT(above)-1)side = 1;if (j-RIGHT(esws->bp->b_inside)==0){side=-1;l_a-=1;}extFringe(above,l_a, esws, sep, j-RIGHT(esws->bp->b_inside),l_p, side);}if (below != NULL){if (r.r_ytop==TOP(esws->bp->b_inside)&&r.r_ytop==TOP(below))l_b-=1;else if (r.r_ytop==TOP(esws->bp->b_inside)&&r.r_ytop<TOP(below))l_b+=1;if (r.r_ybot==BOTTOM(esws->bp->b_inside)&&r.r_ybot==BOTTOM(below))l_b-=1;else if (r.r_ybot==BOTTOM(esws->bp->b_inside)&&r.r_ybot>BOTTOM(below)) l_b+=1;if (r.r_ytop==TOP(esws->bp->b_inside)&&r.r_ytop<TOP(below))l_p=1;if (r.r_ybot==BOTTOM(esws->bp->b_inside)&&r.r_ybot>BOTTOM(below))l_p=1;if (j==LEFT(below)|| j==RIGHT(below)-1)side = 1;if (j-RIGHT(esws->bp->b_inside)==0){side=-1;l_b-=1;}extFringe(below,l_b, esws, sep, j-RIGHT(esws->bp->b_inside),l_p, side);}}}return (0);}147

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Country Views Downloads
United States 21 4
China 5 28
Russia 5 0
New Zealand 4 0
Germany 3 20
Italy 1 0
Brazil 1 19
France 1 0
City Views Downloads
Ashburn 18 0
Unknown 10 56
Christchurch 4 0
Shenzhen 3 25
Beijing 2 0
Atlanta 1 0
Saint Petersburg 1 0
Redmond 1 0
Rome 1 0

{[{ mDataHeader[type] }]} {[{ month[type] }]} {[{ tData[type] }]}
Download Stats

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.24.1-0067690/manifest

Comment

Related Items