TetsuyaIizuka†,andKunihiroAsada†‡
†Dept.ofElectronicsEngineering,UniversityofTokyo‡VLSIDesignandEducationCenter,UniversityofTokyo
7-3-1Hongo,Bunkyo-ku,Tokyo113-8656,Japan
{iizuka,asada}@silicon.u-tokyo.ac.jp
ABSTRACT
Inthispaper,weproposeanexactalgorithmforpracticalroutingproblemsinautomatedcellgeneration.Weassumegrid-based,manhattantwolayermodel.Experimentalre-sultsshowthattheproposedmethodcangeneratebetterso-lutionsthancommercialtoolswithrespecttothewirelengthandthenumberofvias.OuralgorithmtakesaccountofthecharacteristicsofVLSIlayouts,suchassilicidesandVDD/GNDlines.Thisenablesustogenerateallpossibleroutingpatternsforrealcelllayouts.Ourmethodgeneratesallpossibleroutingpatternsundersomerestrictions,sowecanpickupoptimalpatternsbyvariouscostmetrics.
1.INTRODUCTION
Thecell-basedASICisoneofthemajormethodologiesfordesigningVLSI.DuetotherecentimprovementofVLSItechnology,onechiphasalargenumberofstandardcells.Therefore,thequalityofthefinaldesignheavilydependsonthequalityofthestandardcells.Butthedeep-submicrontechnologyleadssomenewproblemssuchassignalintegrity.ThiskindofproblemsbecomesmoredifficultinSoCcom-posedofdigitalcellsandanalogcells.Therefore,thesolu-tionsgeneratedbytheconventionalcellgenerationheuristicsarenotalwaysgoodfortherecentdeep-submicrontechnol-ogy.
Inthispaper,anexactroutingalgorithmispresented.Bygeneratingallpossibleroutingpatterns,wecanobtainex-actoptimalpatternsbyvariouscostmetrics.Exactrout-ingalgorithmswereproposedbyDevadas[1],Schmiedle[2],andSulimma[3].Amongthem,Schmiedle’smethodcangenerateallpatternsexactlybutcan’tsolvelargerproblemsthan4×4grids.Ontheotherhand,themethodsofDevadasandSulimmacansolvelargerproblems,butthismethodhas
SchmiedleProposedDevadas,SulimmaSearch SpaceFig.1Comparisonwithpreviousstudies
Second Layer MetalNetPortTerminal
1First Layer Metal321TrackColumnFig.2Definitionsoftheterminology
somerestrictionsandthesearchspaceofthismethodistoosmallforgeneralcellgeneration.Weproposeanewexactroutingalgorithmthatcansolveproblemswhichislargeenoughtogeneratestandardcellroutingpatterns,anditssearchspaceismuchlargerthanthatofSulimma’smethodbyusingmorepracticalrestrictions.
Fig.1conceptuallycomparesthesearchspaceofourmethodwiththatofthesealgorithms.Fig.2definesterminologiesinthispaper.Someofthemareexplainedasbelow.Column:averticalrowofthegridbasedmodelTrack:ahorizontalrowofthegridbasedmodel
Port:anedgeofthenetwhichextendstothenextcolumnTerminal:apointofacontactholetodiffusionofgate-polysiliconlayer
InSection2,theproposedalgorithmisdescribed.Experi-mentalresultsarepresentedinSection3,followedbycon-clusionsinSection4.
2.ALGORITHM
Inourapproach,wetakethefollowingcharacteristicsofstandardcelllayoutsintoconsideration.
Cellheight:Theheightofeachstandardcellmustbecon-stant.
Portsplacement:Theportsofstandardcellsmustbeonthe
predeterminedgrids.
Silicide:IfthesilicidesareontheP/Ndiffusion,itisenough
toplaceacontactholeononegridforeachdiffusion.VDD/GNDlines:TheVDD/GNDlinesarenormallyrunon
thetop/bottomofindividualcells.Amongthesefourcharacteristics,theformertwoareauto-maticallytakenintoconsiderationbythegrid-based,fixed
Sulimma's methodProposed method1111111111111111121can not generate221211any patterns111Fig.3Differencesofroutingrestrictions
regionmodel.
TheVDD/GNDcharacteristicsarehandledasfollows.WedefinethattheterminalsNo.1areconnectedtotheVDDline,andtheterminalsNo.2areconnectedtotheGNDline.TheterminalstobeconnectedtotheVDDwillbeconnectedtothetopoftheroutingregion,andterminalstobecon-nectedtotheGNDwillbeconnectedtothebottom.
Asforthesilicideweexplainitwiththepatterngenerationinsideeachfunction
Inshortourmethodissummarizedasfollows:1.agridbasedmodel
2.amanhattantwolayermodel
3.obstaclesofarbitraryshapesinanylayers4.silicidesofarbitraryshapes5.
placementsofVDD/GNDlines
Here,weintroducemorepracticalrestrictionofroutingmod-elsthanthatofthepreviousexactroutingalgorithms[1,3].Themainrestrictionofpreviousexactroutingalgorithmsisthatiftherearesplitnetswhichbelongtothesameterminalinonecolumn,theymustbeconnectedinsidethecolumnwhichthesenetsarecontainedin.Thismeansthateachsig-nalcrosseseachverticalcolumnoftheroutingproblematmostonce.Becauseofthisrestriction,thesemethodcannot
Grid model problemFor each columnRoutingAll columnssolutionsare finishedFor each pattern of All patternsprevious columnare finishedDetermine the pattern to be Check if each pattern is validrouted in current columnor not at the next columnFind split ports and insertGenerate all possible portspossible 2nd layer metalspatterns to the next columnGenerate all possible 2ndDetermine the ports to be layer metal patternsextended to the next columnFig.4Ouralgorithmflow
This pattern is passed Column No.x-2x-1xx+1x+2from the column No. x-1
to the column No.x.63335
44144
41366662541
506Track No.: Silicide(a)(b)Fig.5Example
routemostofpracticalprobleminstances.Inordertoexpandthesearchspace,weusetherestrictionasbelow.
•Ifthesplitnetsarenotconnectedinsideacolumn,eachsplitportionofthenetextendstothenextcolumn.Thesearchspacebecomesmuchlargerbyintroducingtheaboverestriction.Fig.3illustratesthedifferencesbetweentheserestrictions.
Fig.4illustratestheflowofouralgorithm.Ourmethodstartsfromleftedgetoright,columnbycolumn.Insideeachcol-umn,allpossiblepatternsaregeneratedforeachpatternofthepreviouscolumnbygoingthroughtheproceduresillus-tratedinFig.4.Eachprocedureisimplementedasafunc-tion.WedescribeeachfunctionbyuseoftheexampleinFig.5.TheexampleinFig.5(a)indicatesaproblemtogen-eratethenextpatternsincolumnNo.x.TheportspatternpassedfromthecolumnNo.x-1tothecolumnNo.xisillustratedinFig.5(b).
Function“decideColumnPattern”:Atfirst,thepatternofprobleminthecurrentcolumnisdetermined.Inthisfunc-tion,wecheckthecurrentandpreviouscolumns.Iftheter-minalsinthecurrentcolumnareonthesilicide,whichisalreadyconnectedinsidethepreviousorthecurrentcolumn,weneednottoconsidertheseterminals.Therefore,suchter-minalsareremoved.Inthisexample,theterminalsNo.3andNo.4areremovedasillustratedinFig.6,becausetheterminalNo.3isalreadyconnectedinthecolumnNo.x-2andtheterminalNo.4isalreadyconnectedinthecurrentcolumn.
3444444666665555555556666(a)(b)Fig.6“decide-ColumnPattern”
Fig.7“connectSplitPort”
Function“connectSplitPort”:Inthisfunctionwefindthesplitports(i.e.theportswhicharenotconnected)fromthepatterngivenbythepreviousfunction.Afterfindingthesplit
44444464666665555555666(a)(b)(c)Fig.8Allsecondlayermetalpatternsgeneratedinthefunction“generateExactLayer2”
ports,wepermutetheseportsandmakeallthepatternsoforder.Weinsertthesecondlayermetalsintothepossibleplaceineachorder.Finally,weremovetheduplicatedpat-ternsfromgeneratedpatterns.Inthecaseofthisexample,theportswhoseNo.is5and6aresplitports.Weper-mutethesenumbersandcanalignthem(5,6),and(6,5).Fig.7illustratespatternswhichismadefromthisfunctionafterinsertingthepossiblesecondlayermetalsineachorder.Fig7(a)isfromtheorderof(5,6),and(b)isfromthatof(6,5).Inthecaseofthisexample,wecannotconnectboththeNo.5netsandtheNo.6netsinthiscolumn.Therefore,Sulimma’smethodfailsinthissituation.
Function“generateExactLayer2”:Wegenerateallthepos-siblesecondlayermetalpatternsfromeachpatterngener-atedbefore.Allpatternsgeneratedinthisfunctionareillus-tratedinFig.8.Fig8(a),(b)isgeneratedfromthepatternofFig.7(a),andFig.8(a),(c)isgeneratedfromthatofFig.7(b).Theduplicatedpatternsareremoved.Then,wecheckthesilicideinthecurrentcolumn.Weremovetheter-minalwhichisalreadyconnectedinthecurrentcolumnbymeansofsilicidelikeasin“decideColumnPattern”.Function“removeRightEdge”:Inthisfunction,wefindthenetswhicharealreadyconnectedandnoterminalswhichbelongtothesamenumberappearsinthefollowingcolumns.Itisnotnecessarytoextendportsfromsuchnetstothenextcolumn.Eventhoughtherearesuchterminalsinthefollow-ingcolumn,wehavenoneedtoextendportstothesetermi-nalsiftheyarealreadyconnectedbymeansofsilicidesinthepreviouscolumns.Forexample,thepatternofFig.8(a),itisnotconnectedtoallNo.5netsyet,sothesenetsmustbeextendedtothenextcolumn.Ontheotherhand,No.4netisalreadyconnectedbutthereisNo.4terminalinthefollowingcolumn(Fig.5(a)),sowemustextendaporttothenextcolumn.InthecaseofFig.8(b),allNo.5netsarealreadyconnected,weneednotextendportstothenextcolumnbecausethereisnoterminalswhichbelongtoNo.5inthefollowingcolumns.InthecaseofFig.8(c),allNo.6netsarealreadyconnectedandthereareNo.6terminalsinthefollowingcolumns,butweneednottoextendNo.6portstonextcolumnbecausethefollowingterminalsarealreadyconnectedbymeansofsilicidesintheNo.xcolumn.Function“generateNextPattern”:Inthisprocedure,weconsidertheseportswhicharedeterminedtobeextendedtothenextcolumnbythepreviousfunction“removeRight-Edge”.Wechangetheplacementofportswhichextendtothenextcolumnbyinsertingthepossiblesecondlayermetals.
6555666(b-1)
(b-2)
(b-3)
446466555666(b-4)
(b-5)
(b-6)
Fig.9AllpatternsgeneratedfromthepatterninFig.8(b)
Fig.9illustratesallthepatternsgeneratedfromFig.8(b).Function“addLeftEdge”:Inthisfunction,wecheckiftheplacementoftheportsandthatofterminalsforeachgener-atedpatterngivenfromthepreviousfunctionisvalidornot.Iftheportgoesintotheterminalwhichhasdifferentnumberfromthatoftheport,itisclearthispatternisimpossible.Butweallowthepatternwhoseportsgoesintotheterminalswhichhavethedifferentnumberifthoseterminalsareonthesilicideandothergridsonthesamesilicidearefreei.e.noportsareonthesegrids.InFig.9,(b-1),(b-3),(b-4),(b-5),and(b-6)haveportswhichcovertheterminalsofdifferentnumberinthenextcolumn.Butonlythepatternof(b-4)isremovedbecauseonlythispatterncoversalltheNo.1ter-minalswhichareconnectedtoeachotherbymeansofthesilicide.Finally,(b-1),(b-2),(b-3),(b-5),and(b-6)inFig.9remainaspossiblepatternsfromFig.8(b)atthiscolumnandarepassedtothenextcolumn.
3.EXPERIMENTALRESULTS
WehaveimplementedtheproposedalgorithminC.Atfirst,wepresenttheresultsoftheproblemmodelswhichhavenosilicidesandVDD/GNDlines.Weevaluateditsperformanceusingseveralexamples.Hereweused8tracksforthesam-pleproblemsbecauseitispracticalenoughtogeneratetheexistingstandardcells.Forexample,wepresentoneoftheresultsgeneratedbyouralgorithminFig.10.
Wecompareditwithareferencemethodcommerciallyavail-ableroutingproblembaseonrip-upmazeroutingalgorithm.Inthiscase,weappliedthemanhattantwolayermodeltothereference.InTable1,thecomparisonsofCPUtimesandthenumberofthesolutionsaregiven.“Obstacles”inthetablemeanstheseexampleshaveobstaclesonsomegrids.FromTable1,ourmethodspentmuchmoreCPUtimethantheref-erence,becauseourmethodgeneratesallpossiblepatternswhereasthereferencegeneratesonlyonenearoptimalsolu-tion.Table1showsthatSulimma’smethodcannotgenerateanypatternsfortheseexamples.Thisdemonstratesthatthe
Table1CPUtimesandthenumberofthesolutions
Example
Reference
Sulimma
Proposed#Tracks×#Columns8×15CPUTime(s)
9
275#Solutions
1Nosolution1118×15CPUTime(s)61634obstacles#Solutions1Nosolution1068×20CPUTime(s)
8902#Solutions
1Nosolution8958×20CPUTime(s)102621obstacles#Solutions
1
Nosolution
39585
241477
64912746133
1
64544556
6115
57
5
5
5
82
3
69248
8879
5
7
1
19
: Metal 1
: Metal 2
: Contact
: Via
Fig.10Oneoftheresultsofthe8×20problemsearchspaceofourmethodislargerthanthatofSulimma.Table2comparesoursolutionswiththatroutedbytherefer-ence.Thewirelengthiscalculatedassuming3µmpergrid.Table2showsthatourmethodcangeneratebettersolutionsthanthatofreferenceintermsofthenumberofviasandwirelength.TheseresultsshowthatouralgorithmcangeneratebettersolutionsthanthatofsomeheuristicsandcansolveproblemsofpracticalsizeinlargersearchspacethanthatofSulimma.
Second,wepresenttheresultsoftheproblemswhichhavesilicidesandVDD/GNDlines.Fig.11(a)illustratesthereallayoutofasamplecell.WetransformedthislayoutintoagridbasedproblempresentedinFig.11(b).FromFig.11,thisproblemhavesilicideonsomegrids.Therefore,theref-erenceandSulimma’smethodcannotgeneratesolutionsforthissampleproblem.Ourmethodgenerated29205solutionsin3917secondsCPUtimeforFig.11(b).Twooftheso-lutionsareillustratedinFig.12.Fig.12(a)isanoptimalpatternintermsofwirelength,andFig.12(b)isanoptimalpatternintermsofthenumberofthecrosspointsbetweenthefirstandthesecondlayermetals.Theseresultsshowthatwecanobtainoptimalpatternsbyvariouscostmetricsforroutingproblemsofreallayoutpattern,bygeneratingallpossibleroutingpatternsundersomerestrictions.
4.CONCLUSIONS
Inthispaper,weshowedthatbyusingmorepracticalrestric-tionsthanthatofSulimma’s,ourmethodcansolveprob-lemslargeenoughtoapplytorealcelllayoutroutingprob-lemsandhavemuchlargersearchspace.Thisenablesustosolvemuchmorepracticalroutingproblemswhichcan-notbesolvedbySulimma’smethod.Weshowthatwecanobtainoptimalsolutions,whichtheconventionalheuristicscan’tgenerate,bygeneratingallpossibleroutingpatternswithourmethod.Wealsoshowedthatourmethodcangen-
Table2Characteristicsofgeneratedsolutions
Example
Reference
ProposedProposed#Tracks×#Columnsviamin
wiremin
8×15#vias
464646wire(µm)
3963963968×15#vias454445obstacleswire(µm)3633663578×20#vias
616060wire(µm)
5615525528×20#vias626163obstacleswire(µm)
474
474
465
3515351535154367: Silicide
467323232323232(a)
(b)
Fig.11Asampleproblem:(a)isareallayoutpattern.(b)isagridbasedmodeltransformedfrom(a).
VDDVDD
5
5
: Metal 1
355
3436
7436
746
7
46
7
: Metal 2
3
33
3: Silicide
GND
GND
GNDGND
(a)(b)
Fig.12Patternsroutedbyproposedmethoderateallpossibleroutingpatternsofrealstandardcelllay-outs,sowecanobtainoptimalpatternsbyvariouscostmet-rics.
REFERENCES
[1]SrinivasDevadas,“OptimalLayoutViaBoolean
Satisfiability,”inProc.IEEEInt.Conf.onComputerAidedDesign,pp.294-297,1989.[2]F.Schmiedle,R.Drechsler,andB.Becker,“Exact
ChannelRoutingUsingSymbolicRepresentation,”inProc.IEEEInt.Symp.onCircuitsandSystems,pp.394-397,1999.[3]KoljaSulimma,andWolfgangKunz,“AnExact
AlgorithmForSolvingDifficultDetailedRoutingProblems,”inProc.ACMInt.Symp.onPhysicalDesign,pp.198-203,2001.
因篇幅问题不能全部显示，请点此查看更多更全内容