DOC

THERMAL_0

By Brenda Willis,2014-07-24 03:35
9 views 0
THERMAL_0THERMA

    THERMAL

V_01.25No.6JOURNAL0FELECTRONICSfCHINANovember2008

    ;FLOORPLANNING

    ;METHOD

    ;USINGGAUSS.SEIDEL

    ;XuNingJiangZhonghua

    ;(Schoolo/ComputerSciencesandTechnology,WuhanUniversityolTechnology,Wuhan430070,China)

    ;AbstractTheGauss-Seidelmethodiseffectivetosolvethetraditionalsparselinearsystem.Inthe

    ;paper.wedefineaclassofsparselinearsystemsiniterativealgorithm.Theiterativemethodfor1inear

    ;systemcallbeextendedtothedummysparselinearsystem.WleapplytheGauss-Seidelmethod.which

    ;isoneoftheiterativemethodsforlinearsystern,tothethermalmodeloffloorplanofVLSIphysical

    ;design.TheexperimentalresultsofdummysparselinearsystemarecomputedbyusingGaussSeide1

    ;methodthathaveshownourtheoryanalysisandextendibility.Theiterativetimeofourincremental

    ;thermalmodelis5timesfasterthanthaltoftheinvertingmatrixmethod. ;KeywordsThermal;Floorplanning;Gauss-Seidelmethod

    ;CLCindexTP301.16

    ;DOI10.1007/s11767-00800258

    ;I.Introduction

    ;0vertheyears,thestate-of-the-arttechnologies

    ;havecontinuedtopushtheVLSIchipstohigher

    ;clockfrequencyandpackingdensity.Thespeed

    ;requirementcauseslargepowerconsumption,while

    ;higherpackingdensityresultsinlargerpower

    ;density.Asprocesstechnologyscalesintothe

    ;nanometer,theexponentialincreaseofpowerden-

    ;sityacrossprocessgenerationsresultsinhigher

    ;die’stemperatureandevenhighertemperatureOil

    ;thewayoftoday’smicrOprOcessOrchips.

    ;Temperaturehasmanysignificantlyimpactson

    ;microelectronicdesign.Firstly,transistorspeedis

    ;slowerathighertemperatureduetothedegrada-

    ;tionofcarriermobility.Aback-of-the-envelope

    ;calculationSHOWSthatasingleinverterisabout

;35%slowerat110?thanat60?.Secondly,the

    ;temperaturedependantofleakagepowerissig- ;nificant.LeakagepowerCallbeorderedofmagni

    ;tudegreaterathighertemperature1J.Thirdly,in-

    ;terconnectmetalresistanceisalsodependenton ;temperature.

    ;Tocopewiththeincreasingdesigncomplexity, ;hierarchicaldesignandIPcoresarewidelyused. ;Manuscriptreceiveddate:March18,2008;reviseddate: ;May4.2oo8.

    ;Communicationauthor:XuNing,bornin1968,male, ;Ph.D.,AssociateProfessor.LuoshiRoad122,Schoolof ;ComputerSciencesandTechnology,WuhanUniversityof ;Technology,Wluhan430070China.

    ;Email:xuning~whut.edu.cn.

    ;Thistrendmakesblockfloorplanning/placement ;muchmorecriticaltothequalityofadesign.The ;hierarchicalfloorplanningisemployedtocopewith ;mixedsizefloorplanand3DICdesign.Floorplan-

    ;ningalgorithmssufferfrommuchenlargingthe ;solutionspaceduetothe3DICdesignandpush ;thenumberofobjectsovermorethanthousandsof ;mixed-sizefloorplaning,whichaffectruntime,so- ;lutionqualityandconvergencespeedt.Multilevel ;clustering[a,4andmincut[5,6technologyareem-

    ;ployedtoenhancescalabilityoffloorplanalgorithm. ;Sofloorplanningdevelopsfromflattohierarchical ;design.

    ;W_eproposeanincrementaliterativemethodto ;solvethethermalmodelofhierarchicalfloorplan- ;ning.Thehierarchicalmodelcanavoidhotspotsin ;thedesignofchip.Weemploythesparsesystem ;methodtocopewithscalingthelargecomputation ;ofthefioorplan.Thecontributionsofthispaper ;include:wedefineagenusdummysystem.Itcanbe ;usedintheiterativelinearsystem.TheGauss- ;Seidelrelaxationiterativemethodisimportedin ;hierarchicalthermalmode1.whichisaneffcient ;algorithmthatvailreducetheruntimebyspeeding ;uptheconvergencewithaccurateestimation.Es- ;pecially.theGaUSS.Seideliterationissuitablefor ;incrementaltemperatureupdating.Comparedwith ;invertingmat,rixmethod.ourmethodcanbe5 ;timesfaster.

    ;Theremalnderofthisletterisorganizedasfo1. ;1ows.SectionIIintroducesthehierarchicalfloor

    ;JOURNALOFELECTRONICS(CHINA),Vo1.25No.6,November2008

    ;planningflow.dummysparselinearsystemsand ;hierarchicalthermalmodelaregiveninSectionIII ;andSectionIV,respectively.SectionVshowsthe ;experimentalresults,andconclusionsandfuture ;worksaregiveninSectionVI.

    ;II.

    ;1n

    ;OverviewofHierarchicalFloorplan

    ;VLSIPhysicalDesign

    ;1.FloorplanofVLSIphysicaldesign

    ;Floorplanistoplacethecircuitblockswit}ut ;overlappinginthesilicondieundersomecostof ;metrics.Floorplandefinition:LetB={61,52,…,

    ;}beasetofrectangularblocks,and,hi,

    ;abethewidth,heightandareaofb,1in,

    ;respectively.Theaspectratioofb{isgivenby ;/,let.minand1”beminimumandmaximum

    rmi,rm畎】.AplacementP= ;aspectratios,.e.,?

    ;{(,)I1i)isanassignmentoftherectan

    ;gularblockswithcoordinates(,sothatnotwo ;blocksoverlap[T].Usually,

    ;thetraditionalatgoalof

    ;placement/floorplanningistominimizethearea ;andwirelengthinducedbytheassignmentofb/s, ;thethermalgoalisanewhardone.

    ;2.Hierarchialfloorplanalgorithm.ofVLSI ;physicaldesign

    ;Hierarchicaldesignisbecomingincreasingly ;attractiveasawaytomanagedesigncomplexity. ;Parquetlclusteredtheblockstothetoplevel

    ;blocksbyheavyconnectivity,thenaddedthe ;whitespacetothetopqevelblocks.Atthebeginning, ;thetop..1evelclustersareplacedbyfree..outline ;floorplan,oncethetoplevelfloorplanisfinished, ;thehigh-levelblocksandtheirshapesimposea ;fixed-outlineconstraintonthe1ower1evelsofdesign. ;hierarchicalfloorplanningflowemploysthe ;fixedoutlinefloorplannertoplacethesubblocksof ;toplevelclusters.MBtree[4Jadoptsatwo-stage ;techniqueforthelarge-scalebuildingblocks,clus

    ;teringfollowedbydeclustering.Theclustering

    ;stageiterativelygroupsasetofblocksbasedona ;costmetricguidedbyareautilizationandblock ;connectivity.AcorrespondingB*-treehasbeen ;constructed.Thedeclusteringstageiteratively ;ungroupsasetofthepreviouslyclusteredblocks ;(i.e.,performtreeexpansion)andthenrefinesthe ;floorplanningsolutionbyusingasimulatedan

    ;nealingscheme.

    ;III.DummySparse

    ;IterativeAlgorithm.

    ;LinearSystemsin

    ;Sparselinearsystemsaremoregeneralnonzero ;patterns,whichrequiremoresophisticatedalgo- ;rithmsanddatastructuresinordertoavoidstoring ;oroperatingonthezerosinthematrix.

    ;1.Sparselinearsystemsandmatrixcomputations ;Amatrixwhichis×mwithknonzeroentries

    ;issparse(if<<xm).Itmaybefastertorep-

    ;resentthematrixcompactlyasalistofthenon- ;zeroindexesandassociatedentries,asalistof ;entries(one1istforeachrOW1,coordinateformat ;(thevaluesandtheirrow/columnpositions),orby ;asinglepointofaccessmethodN.

    ;SparsematrixdefinitionAmatrixthathas ;relativelyfewnon—zero(or”interesting”)entries.It

    ;mayberepresentedinmuchlessthannxmspace. ;SpecialtypesoflinearsystemsWehaveas

    ;sumedthatthelinearsystemhasageneralmatrix ;anditisadenselyone,meaningthatessentiallyall ;ofthematrixentriesarenonzero.Ifthematrixhas ;somespecialproperties,workandstoragecanoften ;besavedinsolvingthelinearsystem.SomeeX’

    ;amplesofspecialpropertiesthatcanbeexploited ;includesymmetric,positivedefinite,band,sparse. ;Mostentriesofamatrixarezerothatisasparse ;matrix[9.

    ;Techniquesforhandlingsymmetricandband ;systemsarerelativelystraightforwardvariations ;onGaussianeliminationfordensesystems.Sparse ;linearsystemsarewithmoregeneralnonzeropat

    ;terns.Ontheotherhand,theyrequiremoreso- ;phisticatedalgorithmsanddatastructuresinorder ;toavoidstoringoroperatingonthezerosinthe ;matrixig].

    ;Iterativemethodsfor1inearsystemsAz=b ;Gaussianeliminationisanexampleofadirect ;methodforsolvinglinearsystems,i…eonethat

    ;producestheexactsolution(assumingexact ;arithmetic)toalinearsysterninainfinitenumber ;ofsteps.Iterativemethodsforsolvinglinearsys

    ;ternsbeginwithaninitialestimateforthesolution ;andsuccessivelyimproveituntnthesolutionisas ;accurateasdesired.Intheory.aninfinitenumberof ;iterationsmightberequiredtoconvergetothe ;exactsolution.Butinpractice.theiterationis ;terminatedaftertheresidualljbAxJJ,orsome

    ;

    ;1.ThermalAwareFloorplanningUsingGaussSeidelMethod847 ;othermeasureoferror,whichisassmallasdesired. ;Forsometypesofproblems,iterativemethodsmay ;havesignificantadvantagesoverthedirectmethods. ;Thesparse1inearsystemsareoftensolvedbyit

    ;erativemethods[9j.

    ;Manyiterativemethodshavebeendeveloped ;forsolvinglargesparselinearsystemsincurrent ;stateof-the-art.Theterm’’iterativemethod’’refers

    ;toawiderangeoftechniquesthatusesuccessive ;approximationstoobtainmoreaccuratesolutions ;toalinearsystemateachstep.Therearetwotypes ;ofiterativemethods.Stationarymethodsareolder. ;simplertounderstandandimplement.butusually ;notaseffective.Nonstationarymethodsarea

    ;relativelyrecentdevelopment.Theiranalysisis ;usuallyhardertounderstand,buttheycanbe ;highlyeffective.Thenon-stationarymethodsthat ;wepresentherearebasedontheideaofsequences ;oforthogonalvectorsI.

    ;2.Dlm~mysparselinearsystemsiniterativeal- ;gorithm

    ;DummysparsematrixdefinitionIfthema- ;trix(AB)thathasrelativelyfewnonzero(1arge

    ;number)entries,thematrixAisadummysparse ;matrixcomparativetomatrixB.

    ;Assumingthattherearetwo1inearsystems ;Ax=b,Bx=borsolvinginsequence,solving ;=bafterAz=bhasbeensolved.Intheit

    ;erativealgorithm,e.g.,simulatedannealing,it ;repetitiouslysolvesinalinearsystemwithdif-

;ferentmatrixfromAtoB.

    ;AssumingBisadummysparsematrixcom

    ;parativeA,Bhasrelativelyfew”interesting’’ca-

    ;triescompareswithA.

    ;Inthiscaseofsequencedummysparsematrix, ;wecanusetheiterativemethodstosolvethe ;dummysparselinearsystemforspeedingupthe ;convergence.Thedetailedoperationisdescribing ;asfollowing:atfirstwesolvethelinearsystem ;Ax=btrivially,theXAandthesolutionof ;A=bcanbegotten;thenwesolvethelinear ;systemBx=binsequence.

    ;Originaliterativemethodsforsolvinglinear ;systemsbeginwithaninitialestimationforthe ;solutionandsuccessivelyimproveituntiltheso- ;lutionisasaccurateasdesired.Theoriginalinitial ;valuecanbegivenbymanymethods.Wecanset ;thisinitialestimatewithzeroorbyexperience. ;Inthiseaseofsequencedummysparsematrix,if ;wesettheinitialestimate=%intheBx:b, ;whichisthesolutionofAx=b,itcanspeedup ;theconvergenceofiterativemethod.Thereasonis ;thatthechangesofthematrixfromAtoBislittle. ;eventhoughthematrixAandBarefu?andnot

    ;sparse.However,thematrixAisdummysparse ;matrixcomparingtomatrixB,matrixAhas ;relativelyfewinterestingentriesaswel1. ;Incomputerscience,wecallthissequence ;dummysparsematrixastheincrementaloperation. ;Wecanalsocallthisdummysparselinearsystems ;computationastheincrementalsolutionupdating ;indetails.Intheiterativealgorithm.theprevious ;iterativesolutionresultpreserveasintermediate ;solution,theinitialsolutionissetforcurrentit

    ;erativetosolvethelinearsystem.

    ;Therearemanydummysparsesystemsinuni. ;versa1iterativealgorithms.TheGaussSeidelisa

    ;kindofsimplyiterativemethodtosolvelinear ;systern.

    ;IV.DummySparseLinearSystems

    ;Instance:ThermalModelinSimulated

    ;AnneallngAlgorithm.ofFloorplan

    ;1.0verviewofthethermalmodel

    ;InthefloorplanofVLSIphysicaldesign,the

    ;circuitblocksarerandomlyplacedinthedieusing ;SA.WhenSAgeneratesafloorplanofcircuit.We ;calculatethecostmetricofdieaTea,wirelength ;amongcircuitblocksandthemaximumtempera- ;tureofcircuitblocksbythethermalmode1. ;F.1Thermalconductinhierarchicalfloorplan

     ;JOURNALOFELECTRONICS(CHINA),Vo1.25No.6INovember

    ;2008

    ;TheSAisaniterativeoptimizingalgorithm. ;ThethermalmodelisincorporatedintotheSA. ;Thethermalconductinthedieiscomplex[n,which

    ;cabeabstractedthermalresistantmodel[. ;R×=PT:RxP(1)

    ;whereTistemperaturevector,Pispowercon

    ;sumptionvector,andRisthermalresistancema- ;trix.Pisconstantvectorofthecircuitblocks,Ris ;determinedbyadetailedfloorplan,andthetherma1 ;resistancematrixamongcircuitblocksisafull ;symmetricmatrix.Itisnotasparsematrix,butit ;isadummysparsematrixintheSAiteration. ;WeuseB*-treeastherepresentationinour ;floorplannerbasedSA.TheperturbationofSA ;algorithmonlychangesalittlefromafloorplanto ;anotherone,e.g.,swapstwoblocks,onlychanges ;twocircuitblocksinfloorplan.Thethermalresis

    ;tanceamongblocksandtemperatureofmost ;blocksdoesnotchangeverymuch.Evenifthenew ;thermalresistancematrixisafuUmatrix,butithas ;relativelyfew”interesting”entries.(R+l)isa

    ;dummysparsematrix.W_eobtainthenewmatrix, ;whichisadummysparsematrixcomparativetothe ;oldoneofthermalresistancematrix.

    ;2.Hierarchicalthermalmodelforfloorp]anning ;Inhierarchicalfloorplanning,theflattenther

    ;realmode1mustbemodifiedtosuitablethehier

    ;archica1floorplanning.Iftwoclustersareplaced ;abuttingtoeachotherandtwohottestblocksin ;differentclustersareplacedattheboundarynearby ;eachother,itmaycausehotspotatboundaryof ;clusters.?reneedtoconsiderthehotterandnearest ;blocksoutofthecurrentclusterwhileplacingthe ;subblocksofit.Thushierarchicalthermalmodel ;mustbemodifiedtoavoidboundaryhotspot.In ;hierarchicalclusteringflooplan,theclustersare

    ;placedsequentially.Whenthesubblocksofcluster ;arebeingpacked,atthistime,thesubblocksof ;cluster(.<havebeenplaced.Usingtheir

    ;fina1coordinatesinthermalmodel,thesubblocksof ;cluster0<arepreparedtobeplacedfollowing ;clusterG.Thesubblocksofclusterhavethe ;samecoordinatesas.Thedetailedpacking ;shouldbedoneatthestageofthetoplevelclusters ;thermalfloorplan.Thenumberofblocksinthermal ;modelismanymorethanthatofplacingthetop ;levelcluster,whichequalstothewholecircuit’s

    ;number.Itisalargenumberthatrequiresmuch ;timetocalculate.

    ;Tospeedupthehierarchicalthermalmodeland ;avoidhotspotatboundary.Whenthefloorplaneris ;placingthesubbloeksofcluster,weonlyconsider ;thehotterandnearerblocksinsteadofthewhole ;blockswhichhavebeenplacedinpreviousfloor? ;plan.

    ;WhentheSAstartsperturbation,atfirsttime ;wecalculatetheblocks’temperaturebyiterative

    ;methodtriviallywiththeinitialestimatewithzero ;vector.Initia1estimateinheritsfromtheprevious ;solutionof1inearsystem.Asthesubsequently ;thermalresistancematrixRn+1isdummysparse ;matrixofR.Invertingmatt.?’siterativetimesis,

    ;whileiterativetimesofmultiplicationmatrixis, ;itstimecomplexityis

    ;numberofblocks.

    ;D()+D()D(),isthe

    ;Assumingthatthecircuit’sblocksaredivided

    ;intokclusters,andthenumberofblocksinthe/-th ;clusteris

    ;=,i=1,2,…,(2)

    ;AssumingthattheSAalgorithmperturbs ;timeswhenblocksof/-thclusterarefloorplaning, ;theoveralliterativetimesofinvertingmatrix ;methodis

    ;invertM=?+.(3)i=1

    ;wherebistheperturbationtimesinplacingthe ;globalclusters,isthenumberoftheglobalclus- ;ters.

    ;3.Gauss-Seidelrelaxationiteration

    ;TheGauss-Seidelmethodisatechniquefor

    ;solvingtheequationsofthelinearsystemofequa- ;tionsAx:boneatatimeinsequence.anduses ;previouslycomputedresultsassoonastheyare ;availableI.GaussSeideliterativeformularyis: ;+1)=

    ;i-1

    ;i=1,2,…,

    ?,:i+l ;n巧一

    ;.

    ;1,J

    ;(4)

    ;Initializingthesolution.theapproximately ;solutioncanbeobtainedbyiterativeformulary. ;??

    ;XUeta1.ThermalAwareFloorplanningUsingGauss-SeidelMethod

    ;Assumingthatthenumberofiterationsiscwhich ;dependsonthenumberofblocksandtheconver. ;gencespeed,whichisnormallylessthanthe ;numberofblocks.Sotheiterativetimesusing ;Gauss-Seideliterativealgorithmislessthan. ;(1)TheconvergenceofGaussSeideliterative

    ;solver

    ;IfthematrixAisdiagonaldominate,

    ;Gauss-Seideliterativesolverisconvergent.The ;thermalresistancematrixAisdiagonaldominate ;toguaranteetheconvergence.

    ;willbrieflyprooftheconvergenceof ;Gauss-Seideliterativesolverinthethermalmode1. ;AccordingtoFourierTheory,onedimension ;steadythermalconductsatisfiestotheequation[14

    ;asfollows:

    ;Q:kAd!

    ;,d

    ;(5)

    ;whereQisthermalconductvelocity(w),Ais ;conductarea(m),distemperaturegrads

    ;(K/m),kisconductparameter(W/m?K).The ;steadystateon-chiptemperaturesatisfiesthefol- ;lowingequation[:

    ;k(x,Y,z)VT(x,,)+g(x,Y,)=0

    ;wherek(x,y,isthethermalconductivity.Tisthe ;temperature,Tistemperaturegrads,g(x,Y,is

    ;thepowerdensityoftheheatsource(s).Thereare

    ;equationsofthel?

Report this document

For any questions or suggestions please email
cust-service@docsford.com