efficient retiming under a general delay model

《efficient retiming under a general delay model》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、EcientRetimingunderaGeneralDelayModelKumarN.LalgudiandMariosC.PapaefthymiouDepartmentofElectricalEngineeringYaleUniversityNewHaven,CT06520AbstractThepolynomial-timeretimingalgorithmsthatweredevelopedintheeightiesassumedsimpledelaymodelsthatneglectedseveraltimingissuesthata

2、riseinlogicdesign.Recentretimingalgorithmsformorecomprehensivedelaymodelsrelyonnon-linearformulationsandruninworst-caseexponentialtimeusingbranch-and-boundtechniques.Inthispaper,weinvestigatetheretimingproblemforedge-triggeredcircuitsunderageneraldelaymodelthathandlesload-d

3、ependentgatedelays,registerdelays,interconnectdelays,andclockskew.WeshowthatinthismodeltheretimingproblemcanbeexpressedasasetofintegerlinearprogrammingconstraintsthatcanbesolvedusinggeneralILPtechniques.Forthespecialcasewhereclockskewismonotonicandallregistershaveequalpropa

4、gationdelays,wegiveanintegermonotonicprogrammingformulationoftheretimingproblem,andwepresentanecientalgorithmforsolvingit.Ouralgorithmretimesanygivenedge-3triggeredcircuittoachieveaspeciedclockperiodinO(VF)steps,whereVisthenumberoflogicgatesinthecircuitandFisboundedbythen

5、umberofregistersinthecircuit.Astraightforwardextensionofouralgorithmdeterminesaminimumclockperiodretimingin3O(VFlgV)steps.1IntroductionTheretimingtransformationoptimizessynchronouscircuitsbyrelocatingtheirstorageelementswithoutaectingtheirfunctionality.Foredge-triggeredcir

6、cuits,researchershavepresentedpolynomial-timeretimingalgorithmsthatassumerelativelysimpledelaymodels[4,5,11].Althoughthesedelaymodelsaregoodenoughforsystem-leveltimingoptimiza-tion,theyareinaccuratewhenappliedatthegatelevel,becausetheydonottakeintoaccountthetimingeectsofse

7、veralfactorssuchasvaryinggateloads,registerdelays,andclockskew.Recently,retimingalgorithmshavebeenproposedforacomprehensivedelaymodelwhichincludesvariableregisterdelaysandsetuptimes,clockskew,andinterconnectdelays[14,15].Inthatwork,retiminghasbeenformulatedasanon-linearprob

8、lemthatissolvedusingbranch-and-boundtechniqueswhichruninworst-caseexponentialtime.