United States Patent
`US 6,499,129 Bl
`(10) Patent No.:
`(12)
`Srinivasanet al.
`(45) Date of Patent:
`Dec. 24, 2002
`
`
`US006499129B1
`
`(75)
`
`(54) METHOD OF ESTIMATING PERFORMANCE
`OF INTEGRATED CIRCUIT DESIGNS
`Inventors: Arvind Srinivasan, San Jose, CA (US);
`Haroon Chaudhri, Berkeley, CA (US);
`Alexandre Zavorine Campbell CA ,
`(US)
`,
`>
`oo
`(73) Assignee: Circuit Semantics, Inc., San Jose, CA
`(US)
`
`(*) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`US.C. 154(b) by 0 days.
`
`(60)
`
`21)
`(21)
`22)
`
`.
`Appl. No.: 09/357,940
`PP
`°
`(357,
`iled:
`ul.
`21,
`Filed
`Jul. 21, 1999
`Related U.S. Application Data
`Provisional application No. 60/093,830, filed on Jul. 22,
`1998.
`(SD) Unt. C07 voccceccccccsccssscesesseessssveeereeseeseeesen GO6F 17/50
`(52) US. Ch. oer 716/4; 716/7; 703/13
`(58) Field of Search ..0..0..0.ee 716/1, 2, 3, 4,
`716/5,
`6,
`7,
`8,
`9, 10,
`11, 18: 703/13, 14
`0 oe 15 19
`,
`
`(56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`Eo
`Eo
`Eo
`Eo
`Eo
`Eo
`
`5,305,229 A
`5,416,721 A
`5,553,008 A
`5,640,328 A
`6,138,266 A
`6,249,898 B1
`
`4/1994 Dhar ou... 364/489
`5/1995 Nishiyamaet al.
`......... 364/491
`9/1996 Huangetal. ........000.. 364/578
`
` 6/1997 Lam ........ eee
`
`10/2000 Ganesan etal. ...
`6/2001 Kohet al. oe eee
`
`OTHER PUBLICATIONS
`Ohlrich, Miles et al., “SubGemini: Identifying SubCircuits
`Using a Fast Subgraph Isomorphism Algorithm,” 30% ACM/
`IEEE Design Automation Conference, Jan. 1993 (ACM
`0-89791-577-1/93/0006—-0031 1.50), pp. 31-37.
`Bryant, R.-E. et al., “Extraction of Gate Level Models from
`Transistor Circuits by Four—Valued Symbolic Analysis,”
`199IEEE (CH306—2/91/0000/0350/$01.00), pp. 350-353.
`Shepard, Kenneth et al., “Noise in Deep Submicron Digital
`Design,” ICCAD ’96, 1063-6757/96, 1996 IEEE 8 pages.
`Bryant, R.E., “Graph—Based Algorithms for Boolean Func-
`tion Manipulation,” IEEE Trans. Comput., vol. C-35, Aug.
`1986, pp. 677-691.
`Appenzeller, David P. et al., “Format Verification of a
`PowerPC™ Microprocessor,” Report RC (19971), IBM T.J.
`Watson Research Center, Yorktown Heights, NY 10598,
`ar.
`»
`pp.
`1-6.
`Mar.
`1995, pp. 1-6
`* cited by examiner
`Primary Examiner—Leigh M. Garbowski
`(74) Attorney, Agent, or Firm—Townsend and Townsend
`and Crew LLP
`(57)
`
`ABSTRACT
`
`.
`.
`.
`A technique to verify, evaluate, and estimate the perfor-
`mance of an integrated circuit is embodied in a computer
`software program that is executable by a computer system.
`The technique accurately estimates of the performance(e.g.,
`transient delays) of an integrated circuit, and has fast execu-
`tion times. The technique is applicable to small circuits
`having relatively few transistors, and especially well suited
`for integrated circuits having millions of transistors and
`components. The technique handles the effects of deep-
`submicron integrated circuit technology.
`
`55 Claims, 11 Drawing Sheets
`
`ih
`
`CLOCK NETWORK
`ANALYSIS
`
`PARTITION
`
`INTO SCCs
`
`CHECK EACH SCC FOR
`MATCHIN DATABASE
`
`457 -
`
`460—
`
`464
`
`467
`
`469 —
`
`x ~NS
`
`
`
`FUNCTION GENERATION &
`STATE POINT IDENTIFICATION
`
`STRONG NODE
`IDENTIFICATION
`
`DON'T.~CARE
`EXPANSION
`
`VECTOR
`GENERATION
`
`STIMULUS
`GENERATION
`
`SIMULATION
`
`MODEL
`GENERATION
`
`APPLE 1115
`APPLE1115
`
`475 477
`
`
`1
`
`

`

`U.S. Patent
`
`Dec. 24, 2002
`
`Sheet 1 of 11
`
`US 6,499,129 B1
`
`
`
`FIG. 1
`
`2
`
`

`

`U.S. Patent
`
`Dec. 24, 2002
`
`Sheet 2 of 11
`
`US 6,499,129 B1
`
`O¢L
`
`colv0
`
`[
`
`90I
`
`aL’
`
`SIT
`
`Zl6
`
`Cll
`
`COld
`
`HOVAAAINI
`AUYOMLAN
`HOVUOLS
`SSVIdaAdn
`
`LuOd
`
`TVITdaSs
`YOLINOW
`
`SOT
`
`AVIdSIC
`
`UdLdVaV
`
`dAAVaAdS
`YOSSHVOad
`IVALNYDO
`AYOWHAN
`YATIOULNOOD
`
`WHILSAS
`
`O/l
`
`3
`
`
`
`
`
`

`

`U.S. Patent
`
`Dec. 24, 2002
`
`Sheet 3 of 11
`
`US 6,499,129 B1
`
`DESIGN ENTRY OR
`LOGIC SYNTHESIS
`
`LAYOUT
`GENERATION
`
`RC EXTRACTION
`
`308
`
`312
`
`
`
`303
`
`
`
`
`
`317
`
`PERFORMANCE
`ESTIMATION
`
`320
`
`FIG. 3
`
`4
`
`

`

`U.S. Patent
`
`Dec. 24, 2002
`
`Sheet 4 of 11
`
`US 6,499,129 B1
`
`404
`
`409
`
`414
`
`419
`
`424
`
`
`
`
`
`
`
`NETLIST
`
`PARTITIONINGand
`LEVELIZING
`
`BINARY VECTOR
`GENERATION
`
`WAVEFORM
`GENERATION
`
`SIMULATION
`
`OUTPUT i
`
`FIG. 4A
`
`431
`
`Characterization
`database
`
`5
`
`

`

`U.S. Patent
`
`Dec. 24, 2002
`
`Sheet 5 of 11
`
`US 6,499,129 B1
`
`451
`
`454
`
`457
`
`460
`
`464
`
`467
`
`469
`
`472
`
`475
`
`477
`
`CLOCK NETWORK
`ANALYSIS
`
`PARTITION INTO SCCs
`
`CHECK EACH SCC FOR
`MATCH IN DATABASE
`
`FUNCTION GENERATION &
`STATE POINT IDENTIFICATION
`
`STRONG NODE
`IDENTIFICATION
`
`DON'T-CARE
`EXPANSION
`
`VECTOR
`GENERATION
`
`STIMULUS
`GENERATION
`
`SIMULATION
`
`MODEL
`GENERATION
`
`FIG. 4B
`
`6
`
`

`

`U.S. Patent
`
`Dec. 24, 2002
`
`Sheet 6 of 11
`
`US 6,499,129 B1
`
`2?
`
`“510
`
`515
`
`FIG, 5
`
`630-1 _
`
`7
`
`

`

`U.S. Patent
`
`Sheet 7 of 11
`
`Dec. 24, 2002
`
`US 6,499,129 B1
`
`8
`
`

`

`U.S. Patent
`
`Dec. 24, 2002
`
`Sheet 8 of 11
`
`US 6,499,129 B1
`
`903
`
`a
`
`917
`
`915
`
`|>o— Yo
`
`
`907
`
`b
`
`979
`
`925
`
`FIG. 9
`
`9
`
`

`

`U.S. Patent
`
`Dec. 24, 2002
`
`Sheet 9 of 11
`
`US 6,499,129 B1
`
`
`
`10
`
`

`

`U.S. Patent
`
`Dec. 24, 2002
`
`Sheet 10 of 11
`
`US 6,499,129 B1
`
`FIG.12
`
`11
`
`

`

`U.S. Patent
`
`Dec. 24, 2002
`
`Sheet 11 of 11
`
`US 6,499,129 B1
`
`FIG.13
`
`12
`
`

`

`US 6,499,129 B1
`
`1
`METHOD OF ESTIMATING PERFORMANCE
`OF INTEGRATED CIRCUIT DESIGNS
`
`This application claims the benefit of U.S. provisional
`patent application No. 60/093,830, filed Jul. 22, 1998. The
`above provisional application and all the references cited in
`this application are incorporated by reference.
`
`MICROFICHE APPENDIX
`
`This application includes a microfiche appendix having 5
`sheets and a total of 404 frames. This microfiche appendix
`contains a C++ source codelisting.
`A portion of the disclosure of this patent document
`contains material which is subject to copyright protection.
`The copyright owner has no objection to the facsimile
`reproduction by anyoneof the patent documentorthe patent
`disclosure, as it appears in the Patent and Trademark Office
`patent file or records, but otherwise reserves all copyright
`rights whatsoever.
`
`BACKGROUND OF THE INVENTION
`
`The present invention relates to the field of electronic
`design automation (EDA)software, and morespecifically, to
`techniques of verifying, evaluating, and estimating the per-
`formance of integrated circuits.
`Integrated circuit technology is a marvel of the modem
`age. Integrated circuits are used in many applications such
`as computers, consumer electronics, networking, and tele-
`communications. There are manytypes of integrated circuits
`including microprocessors, microcontrollers, application
`specific integrated circuits (ASICs), gate arrays, program-
`mable logic devices (PLDs), field programmable gate arrays
`(FPGAs), dynamic random access memories (DRAMSs),
`static random access memories (SRAMs),erasable program-
`mable read only memories (EPROMs), electrically erasable
`programmable read only memories (EEPROMs), and Flash
`memories. Integrated circuits are also sometimesreferred to
`as “chips.”
`technology continues to rapidly
`Integrated circuit
`advance. Automation tools are needed to simplify and expe-
`dite the task of designing an integrated circuit. It is important
`to be able to accurately predict or estimate the performance
`of an integrated circuit before the integrated circuit
`is
`fabricated. Techniques are needed to provide accurate, fast
`estimates of the performance of an integrated circuit.
`As semiconductor processing techniques continue to
`improve, the performance of integrated circuits also contin-
`ues to improve. Deep-submicron integrated he circuit tech-
`nology has enabled commercial multimillion transistor com-
`mercial integrated circuits operating at, for example, 500
`megahertz. High clock frequencies require the ability to
`reliably analyze the performance of circuits with little tol-
`erance for error. A 10 percent tolerance in a performance
`estimate of a 500 megahertz design equates to a margin of
`200 picoseconds, which is 0.200 nanoseconds. In other
`words,there is little room for error in performance estima-
`tion.
`
`In addition to accuracy, capacity, and speed are also
`important considerations for any performance estimation
`technique. For example, time-to-market pressures demand
`performance analysis tools with the ability to obtain an
`accurate snapshot of the performance of a 10-miullion-
`transistor design within a day so that system architects can
`make meaningful architectural tradeoffs without having to
`wait for days to obtain an accurate result.
`
`10
`
`15
`
`20
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`techniques are needed to predict and
`As can be seen,
`estimate the performance of integrated circuits, especially
`fast and efficient techniques that provide accurate results for
`integrated circuit designs with a large numberof transistors.
`SUMMARYOF THE INVENTION
`
`The present invention provides a technique for the per-
`formance verification, evaluation, and estimation of inte-
`grated circuits. In an embodiment,
`the technique of the
`present invention is embodied in a computer software pro-
`gram that
`is to be executed by a computer system.
`In
`particular, the technique facilitates accurate estimates of the
`performance (e.g., transient delays) of an integrated circuit
`and has fast execution times. Although applicable to small
`circuits having relatively few transistors, the technique is
`especially suited for integrated circuits having millions of
`transistors and components.
`The technology of the present invention is broadly appli-
`cable to custom, semicustom, and high-performance inte-
`grated circuits. The present invention may be used to accu-
`rately estimate the performance of all
`the paths of an
`integrated circuit. When used in designs operating in the 250
`megahertz to 1 gigahertz range, and greater, the software of
`present invention can provide results within a design toler-
`ance of about two percent.
`Further, the present invention handles the complexities of
`integrated circuit
`technology,
`including deep-submicron
`effects. To achieve such tight tolerances, the performance
`estimation technique handles the deep-submicroneffects of
`RC-interconnect and transistor interaction, cross-coupling
`capacitance, simultaneous-switching, and waveform shape.
`These effects are dynamic in nature and traditional tech-
`niquesofstatic transistor-level path analysis or library-based
`approaches cannot incorporate these dynamic effects. The
`present invention provides significantly more accurate per-
`formance estimates for deep-submicron designs compared
`to other techniques such as static path analysis.
`Since the present invention uses a dynamic simulation
`approach,
`it
`is able to incorporate cross-coupling
`capacitance, simultaneous-switching, and waveform shape
`effects with results that are comparable to Spice-level simu-
`lation. The present invention also produces fewer false paths
`with resulting savings in designer time and effort. A divide-
`and-conquer approach enables the present invention to deal
`with very large designs, with turnaround times of under a
`day for 10-million-transistor designs.
`In an embodiment of the present invention, the perfor-
`mance of an integrated circuit is estimated by partitioning a
`netlist into strongly coupled components (SCCs). A plurality
`of vectors is generated tor each of the strongly coupled
`components. Strongly driven nodes are determined for each
`SCC. Vector pairs are sequenced and accurate simulation is
`performed on each strongly coupled component. The result
`is an accurate estimate of the performanceof the integrated
`circuit, covering all the paths. Moreover, strongly coupled
`components and the simulation results obtained duringa first
`execution of software of the present invention are saved in
`a database. During subsequent executions,
`these saved
`strongly coupled components and the simulation results are
`reused for those strongly coupled components that are
`unchanged, saving considerable time.
`Other aspects of the present
`invention include tighter
`integration between timing analysis and characterization by
`including Boolean information and automatic elimination of
`global (block-level) false paths.
`In an embodiment, the invention is a method of evaluating
`the performance of an integrated circuit. A netlist or circuit
`
`13
`
`13
`
`

`

`US 6,499,129 B1
`
`3
`description is partiuioned into strongly coupled components.
`A numberof vectors is generated for the strongly coupled
`components. The strongly driven nodes are determined.
`Stimulus is generated for the strongly coupled components.
`A strongly coupled component
`includes a first channel-
`connected componentand a second channel-connected com-
`ponent. The first channel-connected componentinfluences a
`Boolean output of the second channel-connected
`component, and the second channel-connected component
`influences a Boolcan output of the first channel connected
`component. A strongly driven node includes a logical ele-
`ment driving the node with a drive strength greater than
`another logical element driving the same node.
`In another embodiment,
`the invention is a computer
`program product including a computer usable medium with
`computer readable code for causing an evaluation of the
`performanceof an integrated circuit. The computer program
`product includes computer readable code devices configured
`to cause a computer to effect partitioning a netlist
`into
`strongly coupled components; computer readable code
`devices configured to cause a computer to effect generating
`a plurality of vectors for the strongly coupled components;
`and computer readable code devices configured to cause a
`computer to effect determining strongly driven nodes.
`The invention is further a method of estimating the
`performanceof an integrated circuit design including select-
`ing a circuit block of the integrated circuit design. The
`circuit block may be described in a Spice or netlist format.
`A logic function is obtained for a node of the circuit block.
`In a specific embodiment, the logic function includes four
`subfunctions f0, f1, f0', and f1'. Using the logic function, a
`set of vectors is determined that switch or transition the logic
`function at the node. A table is formed including the set of
`vectors.
`
`In a further embodiment, the invention is a method of
`estimating the performance of an integrated circuit design
`including makinga first estimation of the performanceof the
`integrated circuit design. During the first estimation of the
`performance of the integrated circuit design, a database is
`created to store estimated performance results for the inte-
`grated circuit design. A second estimation of the perfor-
`mance of the integrated circuit design is made. During the
`second estimation of the performance of the integrated
`circuit design, the database is read. The stored estimated
`performanceresults from the database ofat least a portion of
`the integrated circuit design are used, where the performance
`results for the portion of the integrated circuit design was
`estimated during the first estimation.
`‘The invention includes a method of estimating the per-
`formanceof an integrated circuit design including selecting
`a circuit block of the integrated circuit design. A logic
`function for a nodeof the circuit block is obtained. Using the
`logic function, a set of vectors is determined that will switch
`the logic function at the node. A table including the set of
`vectors is formed.
`
`The invention includes a method of estimating the per-
`formance of an integrated circuit design including dividing
`the integrated circuit design into channel-connected
`components, where a channel-connected component
`includes nodes and transistors reachable by tracing source-
`drain connections of the transistors. Channel-connected
`components are identified that are connected in a feedback
`loop, where a feedback loop of channel-connected compo-
`nents includes an output of a first channel-connected com-
`ponent driving an input of a second channel-connected
`componentand an output of the second channel-connected
`
`10
`
`15
`
`20
`
`30
`
`35
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4
`component driving an input of the first channel-connected
`component. Channel-connected components connected in a
`feedback loop are merged together to form first strongly
`coupled components.
`Other objects, features, and advantages of the present
`invention will become apparent upon consideration of the
`following detailed description and the accompanying
`drawings, in whichlike reference designations representlike
`features throughout the figures.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`invention of
`FIG. 1 shows a system of the present
`estimating the performance of an integrated circuit;
`FIG. 2 shows a system block diagram of a computer
`system used to execute the software of the present invention;
`FIG. 3 shows a flow diagram for
`the design of an
`integrated circuit;
`FIG. 4A showsa flow diagram of a technique of perfor-
`mance estimation of the invention;
`FIG. 4B shows a more detailed flow diagram of the
`technique of performance estimation of the invention;
`T'IG. 5 shows a channel-coupled circuit;
`FIG. 6 shows another channel-coupled circuit;
`FIG. 7 showsa strongly coupled circuit;
`FIG. 8 showsanother strongly coupled circuit;
`FIG. 9 shows a multiplexer circuit as an example of a
`strongly coupled component;
`FIG. 10 shows a circuit description partitioned into
`strongly coupled components;
`FIG. 11 shows a waveform represented using a set of
`coefficients;
`FIG. 12 shows a multiplexer circuit with output functions
`that can be handled using don’t care expansion; and
`FIG. 13 shows a strongly coupled circuit where logic
`functions are to be determined at a node of the circuit.
`
`DETAILED DESCRIPTION
`
`invention for
`FIG. 1 shows a system of the present
`estimating the performance of an integrated circuit. FIG. 1
`may comprise a computer or digital system used to execute
`the software of the present
`invention. For example,
`the
`method of the present invention may be performed using a
`computer workstation. FIG. 1 shows a computer system 1
`that includes a monitor 3, screen 5, cabinet 7, keyboard 9,
`and mouse 11. Mouse 11 may have one or more buttons such
`as mouse buttons 13. Cabinet 7 houses familiar computer
`components, some of which are not shown, such as a
`processor, memory, mass storage devices 17, and the like.
`Mass storage devices 17 may include mass disk drives,
`floppy disks, Iomega® ZIP™ disks, magnetic disks, fixed
`disks, hard disks, CD-ROMs, recordable CDs, DVDs, tape
`storage, reader, and other similar media, and combinations
`of these. A binary, machine-executable version, of the soft-
`ware of the present invention may be stored or reside on
`mass storage devices 17. Furthermore, the source code of the
`software of the present invention may also be stored or
`reside on mass storage devices 17 (e.g., magnetic disk,tape,
`or CD-ROM).
`FIG. 2 showsa system block diagram of computer system
`1 used to execute the software of the present invention. As
`in FIG. 1, computer system 1 includes monitor 3, keyboard
`9, and mass storage devices 17. Computer system 1 further
`includes subsystems such as central processor 102, system
`
`14
`
`14
`
`

`

`US 6,499,129 B1
`
`5
`(I/O) controller 106, display
`input/output
`memory 104,
`adapter 108, serial port 112, network interface 118, and
`speaker 120. The invention may also be use with computer
`systems with additional or fewer subsystems. For example,
`a computer system could include more than one processor
`102 (i.e., a multiprocessor system) or a system may include
`a cache memory.
`Arrowssuch as 122 represent the system bus architecture
`of computer system 1. However, these arrowsareillustrative
`of any interconnection scheme serving to link the sub-
`systems. For example, speaker 120 could be connected to
`the other subsystems througha port or have an internal direct
`connection to central processor 102. Computer system 1
`shown in FIG. 2 is but an example of a computer system
`suitable for use with the present invention. Other configu-
`rations of subsystems suitable for use with the present
`invention will be readily apparent to one of ordinary skill in
`the art.
`
`A system including a computer or other programmed
`machine executing electronic design automation (EDA)
`software is used in the design of integrated circuits. EDA
`software tools include schematic editors, performance esti-
`mation software, circuit simulators, layout editors, design
`rule checkers, parasitic extractors, and many others. In a
`preferred embodiment, the techniques of the present inven-
`tion are implemented in an EDA software program and
`executed on a computer. The software of the present inven-
`tion provides performance estimation and verification of
`integrated circuits. The software may be stored on a mass
`storage device such as a disk drive or other computer
`readable medium,and then loaded (partially or entirely) into
`the memory of the computer for execution.
`FIG. 3 showsa design flow for the design of an integrated
`circuit. This process may be used to design of a deep-
`submicron integrated circuit. In step 303,
`the design of
`circuitry and logic gates for the integrated circuit is defined.
`A circuit or logic design engineer defines the integrated
`circuit by inputting a schematic, specifying the logic using
`a high level design language (e.g., VHDL or Verilog), or
`otherwise synthesizing the logic. The result is a netlist file
`containing components and connections between the com-
`ponents.
`Interconnections between the components are
`referred to as nets. The netlist file can also be used to
`estimate performance of the circuitry and verify proper
`functionality of the logic. For example, a Spice file can be
`created from the netlist. A circuit simulator such as Spice
`uses the Spice file to estimate the timing of the circuity.
`In step 308, a layout for the integrated circuit is created.
`The layout can be manually generated or automatically
`generated. The layoutis typically contained in a databasefile
`such as a GDSII formatfile. The layout contains polygons
`and geometries on various layers that are used to generate
`the mask set for fabricating the integrated circuit. In step
`312, parasitic and other parameters affecting circuit perfor-
`mance are extracted from the layout. Before the layout is
`prepared, the design engineer cannotbe certain of what the
`parasitic capacitance and resistance the nets will be. Using
`the layout, the lengths, widths, area, and sizes of various
`circuit paths are measured. The capacitance and resistance
`parameters for a process technology are defined in a tech-
`nology modcl file. Using these process parameters and the
`circuit path information, the parasitic capacitances andresis-
`tances are calculated. Parasitic capacitance and resistance
`creates propagation delays based on resistance-capacitance
`(RC) delay.
`In step 317, the parasitic capacitances and resistances are
`put into the netlist or Spice file. This approachis referred to
`
`10
`
`15
`
`20
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6
`as backannotaling the parasilics into the simulation file. The
`circuit simulator analyzes and estimates the performance of
`the circuitry with the parasitic resistance and capacitance
`information. In step 320, the design engineer looks at the
`performance estimates to see whether they meet the pertor-
`mancetargets. If not, the design engineer may need to make
`changes to the circuit or logic design or layout.
`If the
`performance targets are met, the integrated circuit design
`can be fabricated.
`
`Although the techniques may be applied with any, process
`technology,
`in an embodiment,
`the invention specifically
`handles CMOStechnology. CMOStechnology makesuse of
`PMOSand NMOStransistors. A MOStransistor has drain,
`gate, source, and substrate or well connections. A size of a
`MOStransistor is defined by its gate width (W) and channel
`length (L). The principles of the invention are applicable to
`designs using technologies other than MOStransistor tech-
`nology by analogy. For example, an NMOStransistor has a
`source and a drain whichare analogous to the collector and
`emitter of a npn bipolar transistor.
`Some factors to consider when designing integrated cir-
`cuit is that with advances in process technology, integrated
`circuits continue to become smaller and faster. Channel
`lengths of transistors are much less than one micron.In fact,
`integrated circuits are being designed with transistors having
`channel lengths in the range from about 0.18 micronsto 0.35
`microns. And,
`in the future, transistors will undoubtedly
`have even shorter channel lengths. The channel length is
`also referred to as “L effective” or Leff. The characteristics
`and performance of short-channel-length transistors are gov-
`erned in part by what are knownas short channeleffects. For
`long channel length transistors such as those with channel
`lengths greater than one micron,the short channeleffects are
`largely negligible compared to the basic transistor charac-
`teristics. However, for short channel transistors, the short
`channel effects are significant and become more of a domi-
`nant factor in the performance. Short channel effects are
`modeled using somewhat complex equations, and consider-
`ation of short channel effects generally requires more com-
`puting time.
`As process technology advances, integrated circuits gen-
`erally become smaller. More transistors and circuits are
`being placed on a single chip. Consequently, there are a
`greater numberofcircuit paths within the integrated circuit
`for which the performance needs to be considered. And,to
`make the task more complicated, some of the paths may be
`dependent on other paths. To estimate the performance of
`the integrated circuit, each of the various paths needs to be
`identified and analyzed. The performance of these circuit
`paths are compared against the target of expected perfor-
`mance for the integrated circuit. As the numberof circuit
`paths increase, there will be more paths to check, and this
`will increase the computing time.
`A typical integrated circuit system can be divided into a
`number of functional blocks ranging in size from about
`50,000 to over 500,000 transistors. During the initial phases
`of the design process, integrated circuit designers create
`functional blocks with estimated resistive and capacitive
`interconnect models. Later on in the design cycle, accurate
`netlists for the functional blocks may be extracted from
`layout geometry. Extracted netlists are typically very large.
`For example, a 500,000-transistor design may contain from
`3 million to 5 million devices (including MOSFETs,
`resistors, and capacitors) after extraction.
`Therefore, when designing a modem integrated circuit, it
`is important to consider short-channel or deep-submicron
`
`15
`
`15
`
`

`

`US 6,499,129 B1
`
`7
`transistor effects and interconnect behaviors to obtain an
`accurate performance estimate. It is important to considerall
`the critical circuit and performance paths. And, it is impor-
`tant that these performance estimates be done efficiently to
`minimize processing time of the system.
`FIG. 4A shows a flow diagram for a technique of the
`invention to estimate the performance of an integrated
`circuit. An example of computer software that may be used
`to perform performance estimation of integrated circuits is
`the DynaBlock™software. A source codelisting in the C++
`programming languageis provided in the microfiche appen-
`dix. Other examples of performance estimation software
`include DynaCore™, DynaRAM™, and DynaCell™. The
`technique of the present invention includes areas from logic
`minimization to automated test pattern generation (ATPG),
`switch-level analysis simulation, and graph isomorphism.
`In step 404, the invention takes as input either a prelayout
`or extracted netlist for a design. The input also includes
`boundary information such as inputs, outputs, clocks, input
`arrival time windows, and output required time windows
`and clock timing information. Additionally,
`the user can
`specify input waveform information, such as rise and fall
`slew rates, and second-order rate of change of slew infor-
`mation. This second-order information allows the tool to
`
`model the input waveform very accurately. Since the input
`waveform may affect
`the performance of the integrated
`circuit, the user can specify the input waveform and evaluate
`its effect on performance.
`In step 409, the netlist is partitioned into strongly coupled
`components (SCCs), which are fundamental units of analy-
`sis. One SCC may also be referred to as one partition.
`Strongly coupled components typically range in size from,
`for example, 5 to 2000 transistors. Strongly coupled com-
`ponents are analyzed in level order, and logic functions are
`derived for the outputs of the strongly coupled components
`including the effect of charging and discharging times.
`Strongly coupled components are then classified as combi-
`national or state holding. The logic functions are represented
`using a modification of ordered-binary-decision diagrams
`(OBDDs).
`In step 414, the logic functions are used derive a set of
`sensitizing vectors for each SCC output. During the sensi-
`tization process, great care is taken to generate true vectors
`that do not cause a conflict or exercise “sneak” paths. A
`conflict occurs when there are simultaneous charging and
`discharging paths in the SCC. Conflicting or false paths
`cause problems during simulation because they lead spuri-
`ous (usually high) delay results. The result of the sensitiza-
`tion process is a set of vectors for the slowest and fastest
`input sequences for each output of a strongly coupled
`component, taking into account the state-dependent behav-
`ior of the SCC.
`
`Thesensitization process may generate a large numberof
`vectors, especially for strongly coupled circuits such as
`barrel shifters and wide multiplexers. A two-level
`logic
`minimization algorithm is utilized to reduce the vectorset.
`The minimization algorithm models the delay of a term to
`obtain a reduced set of delay vectors.
`Subsequently, in step 419, waveform stimulus is gener-
`ated for
`the strongly coupled components taking into
`account the arrival
`time windows at a strongly coupled
`component. Each strongly coupled componentis simulated
`in level order. Input waveforms are modeled using a three-
`coefficient piecewise linear function.
`In step 424, the user simulates the circuitry. The technique
`of the invention allows the user to choose among different
`
`10
`
`15
`
`20
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`8
`simulation techniques providing the designer trade off
`between run time and accuracy. For example, some of the
`simulation techniques the user can choose include the high
`performance simulation technique of the invention, com-
`mercially available Spice software, and commercially avail-
`able piecewise linear simulation. The simulation is per-
`formed “in-place,” to preserve the exact driver and load
`information for the strongly coupled component.
`The simulation technique of the invention performs out-
`put data reduction and circuit equation reduction to speed up
`simulation and reduce memory consumption without sacri-
`ficing accuracy. A two-terminal capacitor model, such as a
`BSIM3 version 3 capacitor model,
`is used to speed up
`simulation of load devices. The BSIM user’s guide is
`incorporated by reference.
`Output delays and output waveform shape coefficients are
`derived from the simulation and this information is passed to
`the next strongly coupled component in level order. Since
`dynamic simulation is utilized during the delay calculation
`process, the present invention permits the accurate modeling
`of the effects of coupling capacitance, simultancous-
`switching, and waveform shape.
`A technique of the invention is to maintain a database 431
`of strongly coupled components and their associated char-
`acterization information during its operation. Using this
`technique reduces the execution time of the software. Before
`a strongly coupled component
`is simulated, a database
`search is performedto identify a match based upon topology,
`load and input arrival, and slew. If a match is found in the
`database, simulation can be avoided completely. For data-
`path circuits such as adders, multipliers, and comparators,
`the time saved using this method can be enormous. When a
`run is completed, the database is stored on disk. Subsequent
`reruns of the software can utilize the information in the
`database. For example, during the design phase, as the
`designer makes modifications to the design and reruns the
`software, only the strongly coupled components that were
`not matched in the database are resimulated. This incremen-
`
`tal recharacterization feature enables completing perfor-
`mance verification of multimillion-transistor designs
`quickly.
`FIG. 4B showsa more detailed diagram of the flow of the
`invention. The steps in the flow are clock network analysis
`451, partition into SCCs 454, check each SCC for match in
`the model database 457, function generation and state point
`identification 460, strong node identification 464, don’t care
`expansion 467, vector generation 469, waveform or stimulus
`generation 472, simulation 475, and model generation 477.
`Moredetail about these steps are provided in the source code
`appendix andare also discussed below. Steps 451, 454, 457,
`460, and