VLSI Physical Design Automation.ppt

VLSI

1. VLSI Design Automation
•Thisrapidgrowthinintegrationtechnology
hasbeenmadepossiblebytheautomationof
variousstepsinvolvedinthedesignand
fabricationofVLSIchips.
•Integratedcircuitsconsistofanumberof
electroniccomponents,builtbylayering
severaldifferentmaterialsinawell-defined
fashiononasiliconbasecalledawafer.

2. VLSI Design Automation
•ThedesignerofanICtransformsacircuit
descriptionintoageometricdescription,
calledthelayout.
•Alayoutconsistsofasetofplanargeometric
shapesinseverallayers.
•Thelayoutischeckedtoensurethatitmeets
allthedesignrequirements.
•Theresultisasetofdesignfilesthatdescribes
thelayout.

3. VLSI Design Automation
•Anopticalpatterngeneratorisusedtoconvert
thedesignfilesintopatterngeneratorfiles.
•Thesefilesareusedtoproducepatternscalled
masks.
•Duringfabrication,thesemasksareusedto
patternasiliconwaferusingasequenceofphoto-
lithographicsteps.
•Thecomponentformationrequiresveryexacting
detailsaboutgeometricpatternsandthe
separationbetweenthem.

4. VLSI Design Automation
•Theprocessofconvertingthespecificationofan
electricalcircuitintoalayoutiscalledthephysical
designprocess.
•Duetothetighttolerancerequirementsandthe
extremelysmallsizeoftheindividual
components,physicaldesignisanextremely
tediousanderrorproneprocess.
•Duetothelargenumberofcomponents,andthe
exactingdetailsrequiredbythefabrication
process,physicaldesignisnotpracticalwithout
thehelpofcomputers.

5. VLSI Design Automation
•Asaresult,almostallphasesofphysicaldesign
extensivelyuseComputerAidedDesign(CAD)tools,
andmanyphaseshavealreadybeenpartiallyorfully
automated.
•VLSIPhysicalDesignAutomationisessentiallythe
research,developmentandproductizationof
algorithmsanddatastructuresrelatedtothephysical
designprocess.
•Theobjectiveistoinvestigateoptimalarrangementsof
devicesonaplaneandefficientinterconnection
schemesbetweenthesedevicestoobtainthedesired
functionalityandperformance.

6. VLSI Design Automation
•Sincespaceonawaferisveryexpensivereal
estate,algorithmsmustusethespacevery
efficientlytolowercostsandimproveyield.
•Inaddition,thearrangementofdevicesplays
akeyroleindeterminingtheperformanceofa
chip.
•Algorithmsforphysicaldesignmustalso
ensurethatthelayoutgeneratedabidesbyall
therulesrequiredbythefabricationprocess.

7. VLSI Design Automation
•Fabricationrulesestablishthetolerancelimitsof
thefabricationprocess.
•Finally,algorithmsmustbeefficientandshould
beabletohandleverylargedesigns.
•Efficientalgorithmsnotonlyleadtofastturn-
aroundtime,butalsopermitdesignerstomake
iterativeimprovementstothelayouts.
•TheVLSIphysicaldesignprocessmanipulates
verysimplegeometricobjects,suchaspolygons
andlines.

8. VLSI Design Automation
•Asaresult,physicaldesignalgorithmstendtobevery
intuitiveinnature,andhavesignificantoverlapwith
graphalgorithmsandcombinatorialoptimization
algorithms.
•Inviewofthisobservation,manyconsiderphysical
designautomationthestudyofgraphtheoreticand
combinatorialalgorithmsformanipulationof
geometricobjectsintwoandthreedimensions.
•However,apuregeometricpointofviewignoresthe
electrical(bothdigitalandanalog)aspectofthe
physicaldesignproblem.

9. VLSI Design Automation
•InaVLSIcircuit,polygonsandlineshaveinter-
relatedelectricalproperties,whichexhibita
verycomplexbehavioranddependonahost
ofvariables.
•Therefore,itisnecessarytokeeptheelectrical
aspectsofthegeometricobjectsin
perspectivewhiledevelopingalgorithmsfor
VLSIphysicaldesignautomation.

10. VLSI Design Automation
•WiththeintroductionofVeryDeepSub-
Micron(VDSM),whichprovidesverysmall
featuresandallowsdramaticincreasesinthe
clockfrequency,theeffectofelectrical
parametersonphysicaldesignwillplayamore
dominantroleinthedesignanddevelopment
ofnewalgorithms.

11. VLSI Design Cycle
•TheVLSIdesigncyclestartswithaformal
specificationofaVLSIchip,followsaseriesof
steps,andeventuallyproducesapackaged
chip.
•Emphasisisgivenonthephysicaldesignstep
oftheVLSIdesigncycle.

13. VLSI Design Cycle
•System Specification:
–Thefirststepofanydesignprocessistolaydown
thespecificationsofthesystem.System
specificationisahighlevelrepresentationofthe
system.Thefactorstobeconsideredinthis
processinclude:performance,functionality,and
physicaldimensions(sizeofthedie(chip)).

14. VLSI Design Cycle
•System Specification:
–Thefabricationtechnologyanddesigntechniques
arealsoconsidered.Thespecificationofasystem
isacompromisebetweenmarketrequirements,
technologyandeconomicalviability.Theend
resultsarespecificationsforthesize,speed,
power,andfunctionalityoftheVLSIsystem.

15. VLSI Design Cycle
•Architectural Design
–Thebasicarchitectureofthesystemisdesignedin
thisstep.Thisincludes,suchdecisionsasRISC
(ReducedInstructionSetComputer)versusCISC
(ComplexInstructionSetComputer),numberof
ALUs,FloatingPointunits,numberandstructure
ofpipelines,andsizeofcachesamongothers.

16. VLSI Design Cycle
•Behavioral or Functional Design
–Inthisstep,mainfunctionalunitsofthesystem
areidentified.Thisalsoidentifiestheinterconnect
requirementsbetweentheunits.Thearea,power,
andotherparametersofeachunitareestimated.
Thebehavioralaspectsofthesystemare
consideredwithoutimplementationspecific
information.

17. VLSI Design Cycle
•Logic Design:
–Inthisstepthecontrolflow,wordwidths,register
allocation,arithmeticoperations,andlogic
operationsofthedesignthatrepresentthe
functionaldesignarederivedandtested.This
descriptioniscalledRegisterTransferLevel(RTL)
description.RTLisexpressedinaHardware
DescriptionLanguage(HDL),suchasVHDLor
Verilog.

18. VLSI Design Cycle
•Circuit Design:
–Thepurposeofcircuitdesignistodevelopa
circuitrepresentationbasedonthelogicdesign.
TheBooleanexpressionsareconvertedintoa
circuitrepresentationbytakingintoconsideration
thespeedandpowerrequirementsoftheoriginal
design.CircuitSimulationisusedtoverifythe
correctnessandtimingofeachcomponent.

19. VLSI Design Cycle
•Circuit Design:
–Thecircuitdesignisusuallyexpressedinadetailed
circuitdiagram.Thisdiagramshowsthecircuit
elements(cells,macros,gates,transistors)and
interconnectionbetweentheseelements.This
representationisalsocalledanetlist.
–Toolsusedtomanuallyentersuchdescriptionare
calledschematiccapturetools.Inmanycases,a
netlistcanbecreatedautomaticallyfromlogic
(RTL)descriptionbyusinglogicsynthesistools.

20. VLSI Design Cycle
•Physical Design:
–Inthisstepthecircuitrepresentation(ornetlist)is
convertedintoageometricrepresentation.As
statedearlier,thisgeometricrepresentationofa
circuitiscalledalayout.
–Layoutiscreatedbyconvertingeachlogic
component(cells,macros,gates,transistors)into
ageometricrepresentation(specificshapesin
multiplelayers),whichperformtheintendedlogic
functionofthecorrespondingcomponent.

21. VLSI Design Cycle
•Physical Design:
–Connectionsbetweendifferentcomponentsare
alsoexpressedasgeometricpatternstypically
linesinmultiplelayers.
–Theexactdetailsofthelayoutalsodependon
designrules,whichareguidelinesbasedonthe
limitationsofthefabricationprocessandthe
electricalpropertiesofthefabricationmaterials.

22. VLSI Design Cycle
•Physical Design:
–Physicaldesignisaverycomplexprocessand
thereforeitisusuallybrokendownintovarious
sub-steps.
–Variousverificationandvalidationchecksare
performedonthelayoutduringphysicaldesign.
–Inmanycases,physicaldesigncanbecompletely
orpartiallyautomatedandlayoutcanbe
generateddirectlyfromnetlistbyLayoutSynthesis
tools.

23. VLSI Design Cycle
•Physical Design:
–Mostofthelayoutofahighperformancedesign
(suchasamicroprocessor)maybedoneusing
manualdesign,whilemanylowtomedium
performancedesignordesignswhichneedfaster
time-to-marketmaybedoneautomatically.
–Layoutsynthesistools,whilefast,dohaveanarea
andperformancepenalty,whichlimittheiruseto
somedesigns.Manuallayout,whileslowand
manuallyintensive,doeshavebetterareaand
performanceascomparedtosynthesizedlayout.

24. VLSI Design Cycle
•Fabrication
–Afterlayoutandverification,thedesignisready
forfabrication.Sincelayoutdataistypicallysent
tofabricationonatape,theeventofreleaseof
dataiscalledTapeOut.
–Layoutdataisconverted(orfractured)intophoto-
lithographicmasks,oneforeachlayer.Masks
identifyspacesonthewafer,wherecertain
materialsneedtobedeposited,diffusedoreven
removed.

25. VLSI Design Cycle
•Fabrication:
–Siliconcrystalsaregrownandslicedtoproduce
wafers.ExtremelysmalldimensionsofVLSI
devicesrequirethatthewafersbepolishedto
nearperfection.
–Thefabricationprocessconsistsofseveralsteps
involvingdeposition,anddiffusionofvarious
materialsonthewafer.Duringeachsteponemask
isused.Severaldozenmasksmaybeusedto
completethefabricationprocess.

26. VLSI Design Cycle
•Fabrication
–A large wafer is 20 cm (8 inch) in diameter and can
be used to produce hundreds of chips, depending
of the size of the chip.
–Beforethechipismassproduced,aprototypeis
madeandtested.Industryisrapidlymoving
towardsa30cm(12inch)waferallowingeven
morechipsperwaferleadingtolowercostper
chip.

27. VLSI Design Cycle
•Packaging, Testing and Debugging:
–Finally,thewaferisfabricatedanddicedinto
individualchipsinafabricationfacility.Eachchipis
thenpackagedandtestedtoensurethatitmeetsall
thedesignspecificationsandthatitfunctions
properly.
–ChipsusedinPrintedCircuitBoards(PCBs)are
packagedinDualIn-linePackage(DIP),PinGridArray
(PGA),BallGridArray(BGA),andQuadFlatPackage
(QFP).
–ChipsusedinMulti-ChipModules(MCM)arenot
packaged,sinceMCMsusebareornakedchips.

28. VLSI Design Cycle
•Itisimportanttonotethatdesignofa
complexVLSIchipisacomplexhumanpower
managementprojectaswell.
•Severalhundredengineersmayworkona
largedesignprojectfortwotothreeyears.
•Thisincludesarchitecturedesigners,circuit
designers,physicaldesignspecialists,and
designautomationengineers.

29. VLSI Design Cycle
•Asaresult,designisusuallypartitionedalong
functionality,anddifferentunitsaredesignedby
differentteams.
•Atanygiventime,eachunitmaynotbeatthe
samelevelofdesign.Whileoneunitmaybein
logicdesignphase,anotherunitmaybe
completingitsphysicaldesignphase.
•Thisimposesaseriousproblemforchiplevel
designtools,sincethesetoolsmustworkwith
partialdataatthechiplevel.

30. VLSI Design Cycle
•TheVLSIdesigncycleinvolvesiterations,both
withinastepandbetweendifferentsteps.
•Theentiredesigncyclemaybeviewedas
transformationsofrepresentationsinvarious
steps.
•Ineachstep,anewrepresentationofthe
systemiscreatedandanalyzed.The
representationisiterativelyimprovedtomeet
systemspecifications.

31. VLSI Design Cycle
•Forexample,alayoutisiterativelyimproved,so
thatitmeetsthetimingspecificationsofthe
system.
•Anotherexamplemaybedetectionofdesignrule
violationsduringdesignverification.Ifsuch
violationsaredetected,thephysicaldesignstep
needstoberepeatedtocorrecttheerror.
•TheobjectivesofVLSICADtoolsaretominimize
thetimeforeachiterationandthetotalnumber
ofiterations,thusreducingtime-to-market.

32. New Trends in VLSI Design Cycle
•Increasing interconnect delay
•Increasing interconnect area
•Increasing number of metal layers
•Increasing planning requirements
•Synthesis
–Logic Synthesis
–High Level Synthesis

33. Increasing interconnect delay
•Asthefabricationprocessimproves,the
interconnectisnotscalingatthesamerateas
thedevices.
•Devicesarebecomingsmallerandfaster,and
interconnecthasnotkeptupwiththatpace.
•60%ofapathdelaymaybedueto
interconnect.
•Repeatersarenownecessaryformostchip
levelnets.

34. Increasing interconnect area
•Amicroprocessordiehasonly60%-70%ofits
areacoveredwithactivedevices.
•Therestoftheareaisneededto
accommodatetheinterconnect.
•Thisareaalsoleadstoperformance
degradation.
•In early ICs, a few hundred transistors were
interconnected using one layer of metal.

35. Increasing Interconnect Area
•Asthenumberoftransistorsgrew,the
interconnectareaincreased.
•However,withtheintroductionofasecondmetal
layer,theinterconnectareadecreased.
•Thishasbeenthetrendbetweendesign
complexityandthenumberofmetallayers.
•Incurrentdesigns,withapproximatelytenmillion
transistorsandfourtosixlayersofmetal,one
findsabout40%ofthechipsrealestatededicated
toitsinterconnect.

36. Increasing number of metal layers
•Tomeettheincreasingneedsofinterconnect,
thenumberofmetallayersavailablefor
interconnectisincreasing.
•Currently,athreelayerprocessiscommonly
usedformostdesigns,whilefourlayerand
fivelayerprocessesareusedmainlyfor
microprocessors.
•3D view of the interconnect is necessary.

37. Increasing planning requirements
•Themostimportantimplicationofincreasing
interconnectdelay,areaofthediededicated
tointerconnect,andalargenumberofmetal
layersisthattherelativelocationofdevicesis
veryimportant.
•Physicaldesignconsiderationshavetoenter
intodesignatamuchearlierphase.
•Infact,functionaldesignshouldincludechip
planning.

38. Increasing planning requirements
•Twonewkeysteps:BlockplanningandSignal
planning.
•Blockplanningassignsshapesandlocationsto
mainfunctionalblocks.
•Signalplanningreferstoassignmentofthe3D
regionsthroughwhichmajorbussesand
signalsrouted.
•Timingshouldbeestimatedtoverifythe
validityofthechipplan.

39. Synthesis
•Thetimerequiredtodesignanyblockcanbe
reducediflayoutcanbedirectlygeneratedor
synthesizedfromahigherleveldescription.
•Thisnotonlyreducesdesigntime,italso
eliminateshumanerrors.
•Thebiggestdisadvantageistheareausedby
synthesizedblocks.
•Suchblockstakelargerareasthanhand
craftedblocks.

40. Logic Synthesis
•ThisprocessconvertsanHDLdescriptionofa
blockintoschematics(circuitdescription)and
thenproducesitslayout.
•Logicsynthesisisanestablishedtechnology
forblocksinachipdesign,andforcomplete
ApplicationSpecificIntegratedCircuits(ASICs).

41. Logic Synthesis
•Logicsynthesisisnotapplicableforlarge
regularblocks,suchasRAMs,ROMs,PLAsand
Datapaths,andcompletemicroprocessor
chipsfortworeasons:speedandarea.
•Logicsynthesistoolsaretooslowandtoo
area,inefficienttodealwithsuchblocks.

42. High Level Synthesis
•Thisprocessconvertsafunctionalormicro-
architecturaldescriptionintoalayoutorRTL
description.
•Inhighlevelsynthesis,inputisadescription
whichcapturesonlythebehavioralaspectsofthe
system.
•DigitalSignalProcessing(DSP)architectureshave
beensuccessfullysynthesizedbySilicon
Compilers.
•ModuleGenerators,whichworkonsmallersize
problems.

43. High Level Synthesis
•Thebasicideaistosimplifythesynthesistask,
eitherbyrestrictingthearchitectureorrestricting
thesizeoftheproblem.
•Highlevelsynthesisisanareaofcurrentresearch
andisnotusedinactualchipdevelopment.
•Highlevelsynthesissystemsprovideverygood
implementationsforspecializedclassesof
systems,andtheywillcontinuetogain
acceptanceastheybecomemoregeneralized.

44. New Trends in VLSI Design Cycle
•Duetoincreasinginterconnectdelay,thephysical
designstartsveryearlyinthedesigncycletoget
improvedestimatesoftheperformanceofthechip.
•Theearlyfloorphysicaldesignactivitiesleadto
increasinglyimprovedchiplayoutaseachblockis
refined.
•Thisalsoallowsbetterutilizationofthechipareato
distributetheinterconnectinthreedimensions.
•Thisdistributionhelpsinreducingthediesize,
improvingyieldandreducingcost.

46. Physical Design Cycle
•Theinputtothephysicaldesigncycleisthe
circuitandtheoutputisthelayoutofthe
circuit.
•Thisisaccomplishedinseveralstagessuchas
partitioning,floorplanning,placement,
routing,andcompaction.

48. Partitioning
•Achipmaycontainseveralmilliontransistors.
•Duetothelimitationsofmemoryspaceand
computationpoweravailableitmaynotbe
possibletolayouttheentirechip(orlarge
circuit)inthesamestep.
•Therefore,thechip(circuit)isnormally
partitionedintosub-chips(sub-circuits).These
sub-partitionsarecalledblocks.

49. Partitioning
•Theactualpartitioningprocessconsidersmany
factorssuchasthesizeoftheblocks,numberof
blocks,andnumberofinterconnectionsbetween
theblocks.
•Theoutputofpartitioningisasetofblocksand
theinterconnectionsrequiredbetweenblocks.
•Inlargecircuits,thepartitioningprocessis
hierarchicalandatthetopmostlevelachipmay
have5to25blocks.
•Eachblockisthenpartitionedrecursivelyinto
smallerblocks.

50. Floorplanning
•Thisstepisconcernedwithselectinggood
layoutalternativesforeachblock,aswellas
theentirechip.
•Theareaofeachblockcanbeestimatedafter
partitioningandisbasedapproximatelyonthe
numberandthetypeofcomponentsinthat
block.
•Inaddition,interconnectarearequiredwithin
theblockmustbeconsidered.

51. Floorplanning
•Floorplanningisacriticalstep,asitsetsupthe
groundworkforagoodlayout.
•However,itiscomputationallyquitehard.
Veryoftenthetaskoffloorplanningisdoneby
adesignengineer,ratherthanaCADtool.
•Thisisduetothefactthatahumanisbetter
at‘visualizing’theentirefloorplanandtaking
intoaccounttheinformationflow.

52. Floorplanning
•Manualfloorplanningissometimesnecessary
asthemajorcomponentsofanICneedtobe
placedinaccordancewiththesignalflowof
thechip.
•Inaddition,certaincomponentsareoften
requiredtobelocatedatspecificpositionson
thechip.

53. Placement
•Duringplacement,theblocksareexactly
positionedonthechip.
•Thegoalofplacementistofindaminimumarea
arrangementfortheblocksthatallows
completionofinterconnectionsbetweenthe
blocks,whilemeetingtheperformance
constraints.
•Thatis,wewanttoavoidaplacementwhichis
routablebutdoesnotallowcertainnetstomeet
theirtiminggoals.

54. Placement
•Placementistypicallydoneintwophases.
•Inthefirstphaseaninitialplacementis
created.
•Inthesecondphase,theinitialplacementis
evaluatedanditerativeimprovementsare
madeuntilthelayouthasminimumareaor
bestperformanceandconformstodesign
specifications.

55. Placement
•Somespacebetweentheblocksisintentionally
leftemptytoallowinterconnectionsbetween
blocks.
•Thequalityoftheplacementwillnotbeevident
untiltheroutingphasehasbeencompleted.
•Placementmayleadtoanunroutabledesign,i.e.,
routingmaynotbepossibleinthespace
provided.
•Inthatcase,anotheriterationofplacementis
necessary.

56. Placement
•Tolimitthenumberofiterationsoftheplacement
algorithm,anestimateoftherequiredroutingspace
isusedduringtheplacementphase.
•Goodroutingandcircuitperformancedepend
heavilyonagoodplacementalgorithm.
•Thisisduetothefactthatoncethepositionofeach
blockisfixed,verylittlecanbedonetoimprovethe
routingandtheoverallcircuitperformance.
•Lateplacementchangesleadtoincreaseddiesize
andlowerqualitydesigns.

57. Routing
•Theobjectiveoftheroutingphaseisto
completetheinterconnectionsbetween
blocksaccordingtothespecifiednetlist.
•First,thespacenotoccupiedbytheblocks
(calledtheroutingspace)ispartitionedinto
rectangularregionscalledchannelsand
switchboxes.
•Thisincludesthespacebetweentheblocksas
welltheasthespaceontopoftheblocks.

58. Routing
•Thegoalofarouteristocompleteallcircuit
connectionsusingtheshortestpossiblewire
lengthandusingonlythechannelandswitch
boxes.
•Thisisusuallydoneintwophases,referredtoas
theGlobalRoutingandDetailedRoutingphases.
•Inglobalrouting,connectionsarecompleted
betweentheproperblocksofthecircuit
disregardingtheexactgeometricdetailsofeach
wireandpin.

59. Routing
•For each wire, the global router finds a list of channels
and switchboxes which are to be used as a passageway
for that wire.
•Inotherwords,globalroutingspecifiesthedifferent
regionsintheroutingspacethroughwhichawire
shouldberouted.
•Globalroutingisfollowedbydetailedroutingwhich
completespoint-to-pointconnectionsbetweenpinson
theblocks.
•Globalroutingisconvertedintoexactroutingby
specifyinggeometricinformationsuchasthelocation
andspacingofwiresandtheirlayerassignments.

60. Routing
•Detailedroutingincludeschannelroutingand
switchboxrouting,andisdoneforeach
channelandswitchbox.
•Routingisaverywellstudiedproblem,and
severalhundredarticleshavebeenpublished
aboutallitsaspects.
•Sincealmostallproblemsinroutingare
computationallyhard,theresearchershave
focusedonheuristicalgorithms.

61. Routing
•Experimentalevaluationhasbecomeanintegral
partofallalgorithmsandseveralbenchmarks
havebeenstandardized.
•Duetotheverynatureoftheroutingalgorithms,
completeroutingofalltheconnectionscannotbe
guaranteedinmanycases.
•Asaresult,atechniquecalledrip-upandre-route
isused,whichbasicallyremovestroublesome
connectionsandreroutestheminadifferent
order.

62. Compaction
•Compactionissimplythetaskofcompressing
thelayoutinalldirectionssuchthatthetotal
areaisreduced.
•Bymakingthechipsmaller,wirelengthsare
reduced,whichinturnreducesthesignal
delaybetweencomponentsofthecircuit.
•Atthesametime,asmallerareamayimply
morechipscanbeproducedonawafer,which
inturnreducesthecostofmanufacturing.

63. Compaction
•However,theexpenseofcomputingtime
mandatesthatextensivecompactionisused
onlyforlargevolumeapplications,suchas
microprocessors.
•Compactionmustensurethatnorules
regardingthedesignandfabricationprocess
areviolatedduringtheprocess.

64. Extraction and Verification
•DesignRuleChecking(DRC)isaprocesswhich
verifiesthatallgeometricpatternsmeetthe
designrulesimposedbythefabricationprocess.
•Forexample,onetypicaldesignruleisthewire
separationrulei.e.,thefabricationprocess
requiresaspecificseparation(inmicrons)
betweentwoadjacentwires.
•DRCmustchecksuchseparationformillionsof
wiresonthechip.

65. Extraction and Verification
•Theremaybeseveraldozendesignrules,
someofthemarequitecomplicatedtocheck.
•Aftercheckingthelayoutfordesignrule
violationsandremovingthedesignrule
violations,thefunctionalityofthelayoutis
verifiedbyCircuitExtraction.
•Thisisareverseengineeringprocess,and
generatesthecircuitrepresentationfromthe
layout.

66. Extraction and Verification
•Theextracteddescriptioniscomparedwiththe
circuitdescriptiontoverifyitscorrectness.
•ThisprocessiscalledLayoutVersusSchematics(LVS)
verification.
•Geometricinformationisextractedtocompute
ResistanceandCapacitance.
•Thisallowsaccuratecalculationofthetimingofeach
component,includinginterconnect.
•ThisprocessiscalledPerformanceVerification.

67. Extraction and Verification
•Theextractedinformationisalsousedto
checkthereliabilityaspectsofthelayout.
•ThisprocessiscalledReliabilityVerification
anditensuresthatlayoutwillnotfaildueto
electromigration,self-heatandothereffects.

69. Summary of Physical Design Cycle
•Physicaldesign,likeVLSIdesign,isiterativein
natureandmanysteps,suchasglobalrouting
andchannelrouting,arerepeatedseveraltimes
toobtainabetterlayout.
•Inaddition,thequalityofresultsobtainedina
stepdependsonthequalityofthesolution
obtainedinearliersteps.
•Forexample,apoorqualityplacementcannotbe
‘cured’byhighqualityrouting.Asaresult,earlier
stepshavemoreinfluenceontheoverallquality
ofthesolution.

70. Physical Design Cycle
•Inthissense,partitioning,floorplanning,and
placementproblemsplayamoreimportant
roleindeterminingtheareaandchip
performance,ascomparedtoroutingand
compaction.
•Sinceplacementmayproducean‘unroutable’
layout,thechipmightneedtobere-placedor
re-partitionedbeforeanotherroutingis
attempted.

71. Physical Design Cycle
•Ingeneral,thewholedesigncyclemaybe
repeatedseveraltimestoaccomplishthe
designobjectives.
•Thecomplexityofeachstepvaries,depending
onthedesignconstraintsaswellasthedesign
styleused.

72. New Trends in Physical Design Cycle
•Asfabricationtechnologyimprovesandprocess
entersthedeepsub-micron(DSM)range,itis
clearthatinterconnectdelayisnotbeingscaled
atthesamerateasthegatedelay.
•Therefore,interconnectdelayisamore
significantpartofoveralldelay.
•Asaresult,inhighperformancechips,
interconnectdelaymustbeconsideredfromvery
earlydesignstages.
•Inordertoreduceinterconnectdelayseveral
methodscanbeemployed.

73. Chip level signal planning
•Atthechiplevel,routingofmajorsignalsand
busesmustbeplannedfromearlydesign
stages,sothatinterconnectdistancescanbe
minimized.
•Inaddition,theseglobalsignalsmustbe
routedinthetopmetallayers,whichhavelow
delayperunitlength.

74. OTC Routing
•Over-the-Cell(OTC)routingisatermusedto
describeroutingoverblocksandactiveareas.
•Itisdifferentfromconventionalchanneland
switchboxroutingapproach.
•ThechiplevelsignalplanningisOTCrouting
ontheentirechip.
•TheOTCapproachcanalsobeusedwithina
blocktoreduceareaandimprove
performance.

75. OTC Routing
•TheOTCroutingapproachessentiallymakes
routingathreedimensionalproblem.
•AnothereffectoftheOTCroutingapproachis
thatthepinsarenotbroughttotheblock
boundariesforconnectionstootherblocks.
•Instead,pinsarebroughttothetopofthe
blockasasea-of-pins.
•ItiscalledArbitraryTerminalModel(ATM).

77. Design Styles
•Physicaldesignisanextremelycomplexprocess.
Evenafterbreakingtheentireprocessinto
severalconceptuallyeasiersteps,ithasbeen
shownthateachstepiscomputationallyvery
hard.
•However,marketrequirementsdemandquick
time-to-marketandhighyield.Asaresult,
restrictedmodelsanddesignstylesareusedin
ordertoreducethecomplexityofphysicaldesign.

78. Design Styles
•Thedesignstylescanbebroadlyclassifiedaseither
full-customorsemi-custom.
•Inafull-customlayout,differentblocksofacircuit
canbeplacedatanylocationonasiliconwaferas
longasalltheblocksarenon-overlapping.
•Ontheotherhand,insemi-customlayout,some
partsofacircuitarepredesignedandplacedon
somespecificplaceonthesiliconwafer.
•Selectionofalayoutstyledependsonmanyfactors
includingthetypeofchip,cost,andtime-to-market.

79. Design Styles
•Full-customlayoutisapreferredstyleformass
producedchips,sincethetimerequiredto
produceahighlyoptimizedlayoutcanbe
justified.
•Ontheotherhand,todesignanApplication
SpecificIntegratedCircuit(ASIC),asemi-
customlayoutstyleisusuallypreferred.
•Onalargechip,eachblockmayuseadifferent
layoutdesignstyle.

80. Full-custom Structure

81. Standard Cell
•Thedesignprocessinthestandardcelldesign
styleissomewhatsimplerthanfull-custom
designstyle.
•Standardcellarchitectureconsidersthelayout
toconsistofrectangularcellsofthesame
height.
•Initially,acircuitispartitionedintoseveral
smallerblocks,eachofwhichisequivalentto
somepredefinedsub-circuit(cell).

82. Standard Cell
•Thefunctionalityandtheelectricalcharacteristics
ofeachpredefinedcellaretested,analyzed,and
specified.
•Acollectionofthesecellsiscalledacelllibrary.
•Usuallyacelllibraryconsistsof500-1200cells.
•Terminalsoncellsmaybelocatedeitheronthe
boundaryordistributedthroughoutthecellarea.
•Cellsareplacedinrowsandthespacebetween
tworowsiscalledachannel.

83. Standard Cell
•Thesechannelsandthespaceaboveandbetweencells
isusedtoperforminterconnectionsbetweencells.
•Iftwocellstobeinterconnectedlieinthesamerowor
inadjacentrows,thenthechannelbetweentherowsis
usedforinterconnection.
•However,iftwocellstobeconnectedlieintwonon-
adjacentrows,thentheirinterconnectionwirepasses
throughemptyspacebetweenanytwocellsorpasses
ontopofthecells.
•Thisemptyspacebetweencellsinarowiscalleda
feedthrough.

85. Gate Arrays
•Allthecellsingatearrayareidentical.
•Eachchipisanarrayofidenticalgatesorcells.
•Thesecellsareseparatedbybothverticaland
horizontalspacescalledverticalandhorizontal
channels.
•Thecircuitdesignismodifiedsuchthatitcanbe
partitionedintoanumberofidenticalblocks.
•Eachblockmustbelogicallyequivalenttoacell
onthegatearray.

86. Gate Arrays
•Thename‘gatearray’signifiesthefactthateachcell
maysimplybeagate,suchasathreeinputNAND
gate.
•Thenumberofpartitionedblocksmustbelessthan
orequaltothetotalnumberofcellsonthechip.
•Oncethecircuitispartitionedintoidenticalblocks,
thetaskistomaketheinterconnectionsbetweenthe
prefabricatedcellsonthechipusinghorizontaland
verticalchannelstoformtheactualcircuit.
•Thegatearraywaferistakenintoafabricationfacility
androutinglayersarefabricatedontopofthewafer.

87. Gate Arrays

88. Gate Arrays

89. Field Programmable Gate Arrays
•TheFieldProgrammableGateArray(FPGA)isa
newapproachtoASICdesignthatcan
dramaticallyreducemanufacturingturn-around
timeandcostforlowvolumemanufacturing.
•InFPGAs,cellsandinterconnectare
prefabricated.
•Theusersimply‘programs’theinterconnect.
•FPGAdesignsprovidelargescaleintegrationand
userprogrammability.

90. Field Programmable Gate Arrays
•AFPGAconsistsofhorizontalrowsof
programmablelogicblockswhichcanbe
interconnectedbyaprogrammablerouting
network.
•FPGAcellsaremorecomplexthanstandardcells.
However,almostallthecellshavethesame
layout.
•Alogicblockissimplyamemoryblockwhichcan
beprogrammedtorememberthelogictableofa
function.

91. Field Programmable Gate Arrays
•Connectionbetweenhorizontalsegmentsis
providedthroughantifuses,whereasthe
connectionbetweenahorizontalsegmentand
averticalsegmentisprovidedthroughacross
fuse.

92. FPGA

93. FPGA

94. FPGA
•Thecrossfusesareshownascircles,while
antifusesareshownasrectangles.
•OnedisadvantageoffusebasedFPGAsisthat
theyarenotreprogrammable.
•ThereareothertypesofFPGAswhichallow
re-programming,andusepassgatesrather
thanprogrammablefuses.

95. Data Structures and Basic
Algorithms
•PhysicaldesignCADtoolsrequirehighly
specializedalgorithmsanddatastructuresto
effectivelymanageandmanipulatelayout
information.
•Thesetoolsfallinthreecategories.
•Thefirsttypeoftoolshelpahumandesigner
tomanipulatealayout.
–Forexample,alayouteditorallowsdesignersto
addtransistorsornetstoalayout.

96. Data Structures and Basic
Algorithms
•Thesecondtypeoftoolsaredesignedto
performsometaskonthelayout
automatically.
–Exampleofsuchtoolsincludechannelroutersand
placementtools.
–Itisalsopossibletoinvokeatoolofsecondtype
fromthelayouteditor.

97. Data Structures and Basic
Algorithms
•Thethirdtypeoftoolsareusedforchecking
andverification.
–Exampleofsuchtoolsinclude;DRC(designrule
checker)andLVSverifier(layoutversusschematics
verifier).
•Mostoftheresearchofphysicaldesign
automationhasfocusedontoolsofthelast
twotypeswhereasmostattentionisgivento
the2
nd
type.

98. Data Structures and Basic
Algorithms
•Themajorfocushasbeenondevelopmenton
designandanalysisofheuristicalgorithmsfor
partitioning,placement,routingand
compaction.
•Manyofthesealgorithmsarebasedongraph
theoryandcomputationalgeometry.

99. Basic Terminology
•A graph is a pair of sets G = (V, E), where V is a
set of vertices, and E is a set of pairs of distinct
vertices called edges.
•V(G) and E(G) refer to the vertex and edge set
of a graph G.
•A vertex uis adjacent to a vertex v, if is an
edge i.e.
•The set of vertices adjacent to is Evu, vu, v vAdj

100. Basic Terminology
•Anedge isincidentonthevertices
andwhicharetheendsofe.
•Thedegreeofavertexisthenumberof
edgesincidentwiththevertex.
•Acompletegraphonverticesisagraphin
whicheachvertexisadjacenttoeveryother
vertex.
•isusedtodenotethegraph.vue, u v v u n nK

101. Basic Terminology
•AgraphHiscalledthecomplementofgraphG
=(V,E),ifH=(V,F),where, .EKEF
v


102. Complexity Issues and NP-hardness
•Severalgeneralalgorithmsandmathematical
techniquesarefrequentlyusedtodevelop
algorithmsforphysicaldesign.
–Greedy Algorithms
–Divide and Conquer Algorithms
–Dynamic Programming Algorithms
–Network Flow Algorithms
–Linear/Integer Programming Techniques

103. Complexity Issues and NP-hardness
•Theclassofsolvableproblemscanbe
partitionedintotwogeneralclasses,PandNP.
•TheclassPconsistsofallproblemsthatcanbe
solvedbyadeterministicturingmachinein
polynomialtime.
•Aconventionalcomputermaybeviewedas
suchamachine.Minimumcostspanningtree,
singlesourceshortestpath,andgraph
matchingproblemsbelongtoclassP.

104. Complexity Issues and NP-hardness
•TheotherclasscalledNP,consistsofproblems
thatcanbesolvedinpolynomialtimebya
nondeterministicturingmachine.
•Thistypeofturingmachinemaybeviewedas
aparallelcomputerwithasmanyprocessors
aswemayneed.
•IfeveryprobleminclassNPcanbereducedto
aproblemP,thenproblemPisinclassNP-
complete.

105. Complexity Issues and NP-hardness
•Severalthousandproblemsincomputer
science,graphtheory,combinatorics,
operationsresearch,andcomputational
geometryhavebeenproventobeNP
complete.
•TheoptimizationversionofaproblemP,is
calledNP-hard,ifthedecisionversionofthe
problemPisNP-complete.

106. Algorithms for NP-hard Problems
•Most optimization problems in physical design
are NP-hard.
•IfaproblemisknowntobeNP-completeor
NP-hard,thenitisunlikelythatapolynomial
timealgorithmexistsforthatproblem.

107. Exponential Algorithms
•Ifthesizeoftheinputissmall,thenalgorithms
withexponentialtimecomplexitymaybe
feasible.
•Inmanycases,thesolutionofacertainproblem
becriticaltotheperformanceofthechipand
thereforeitispracticaltospendextraresources
tosolvethatproblemoptimally.
•Onesuchexponentialmethodisinteger
programming,whichhasbeenverysuccessfully
usedtosolvemanyphysicaldesignproblems.

108. Graph Search Algorithms
•Since many problems in physical design are
modeled using graphs.
•Itisimportanttounderstandefficient
methodsforsearchinggraphs.
–Depth-FirstSearch
–Breadth-FirstSearch
–TopologicalSearch

109. Depth-First Search
•In this graph search strategy, graph is searched
‘as deeply as possible’.
•InDepth-FirstSearch(DFS),anedgeis
selectedforfurtherexplorationfromthemost
recentlyvisitedvertex.
•Whenalltheedgesofhavebeenexplored,the
algorithmbacktrackstothepreviousvertex,
whichmayhaveanunexplorededge.

110. Depth-First Search
•ThealgorithmusesanarrayMARKED(n)
whichisinitializedtozerobeforecallingthe
algorithmtokeeptrackofallthevisited
vertices.
•Itiseasytoseethatthetimecomplexityof
depth-firstsearchisO(|V|+|E|).

111. Graph Search Algorithms
•Depth-First Search:

112. Breadth-First Search
•ThebasicideaofBreadth-FirstSearch(BFS)isto
exploreallverticesadjacenttoavertexbefore
exploringanyothervertex.
•Startingwithasourcevertex,theBFSfirst
exploresalledgesof,putsthereachablevertices
inaqueue,andmarksthevertexasvisited.
•Ifavertexisalreadymarkedvisitedthenitisnot
enqueued.Thisprocessisrepeatedforeach
vertexinthequeue.

113. Breadth-First Search
•ThisprocessofvisitingedgesproducesaBFS
tree.
•TheBFSalgorithmcanbeusedtosearchboth
directedandundirectedgraphs.
•themaindifferencebetweentheDFSandthe
BFSisthattheDFSusesastack(recursionis
implementedusingstacks),whiletheBFSuses
aqueueasitsdatastructure.

114. Breadth-First Search
•Thetimecomplexityofbreadthfirstsearchis
alsoO(|V|+|E|).

115. Algorithms for NP-hard Problems