applying a vlsi cad heuristic to a prolog compiler problem

《applying a vlsi cad heuristic to a prolog compiler problem》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、ApplyingaVLSICADHeuristictoaPrologCompilerProblemTR-96-002OwenKaserDept.ofMSCSUNBSJSaintJohn,N.B.E2L4L5e-mail:owen@unbsj.caAugust19,19961IntroductionIn[DRR95,DRR96]anecientmethodofconstructingjumptablesisexamined.ItassumeswearegivenanitesetofsymbolsS,corresponding

2、tothepredicatesinaPrologprogram.Thepaperconsiderstheoptimizationofcertainnitestateautomatausedinindexingtheprogram;anautomatonmakestransitionsaccordingtosymbolsinSpresentedtoit.Typically,thereareasmallnumberofvalidtransitionsleavingeachstate.Lett;:::;tdenotethestat

3、esofthe1mautomaton,andletJ=fs2Sjslabelsavalidtransitionfromstatetg,for1im,iiAtime-ecientbutspace-inecientrepresentationforsuchanautomatoncanbeobtainedbynumberingstatess2Sarbitrarilyfrom1:::jSj.Letf:S!f1;:::;jSjgdenotethenumberingbijection.Then,thetransitionsleav

4、ingeachstatecouldbeimplementedasasajump(dispatch)tablewithjSjentries;ifsymbolsispresentedtotheautomaton,thenextstateisdeterminedithfromthef(s)entryinthecurrentstate'stable.iWecandobetter.Ifthevalidtransitionsareintherange[min:::max],theentiretableneednotbestored.Ins

5、tead,westoremin,max,andthemax?min+1tableentriesthatfallwithintherange;asexplainedin[DRR95],thisissucient.Anaturaloptimizationproblemarises;ratherthanchoosingthenumberingfunctionfarbi-trarily,ndfs.t.thetotalsizeofalltablesisminimized.Notethatthetotalsizeofalltables

6、ismX(maxff(s)g?minff(s)g+1):s2Js2Jiii=1Clearly,thisvalueisminimizedwhenevermX(maxff(s)g?minff(s)g)s2Js2Jiii=1isminimized.HoweverifjJj=2;1im,theproblemisessentiallytheOPTIMALLINEARiARRANGEMENTproblem[GJ79,page200],andanNP-completenessproofiseasilyobtainedfortheasso

7、ciateddecisionproblem[DRR95].Whatisapparentlyoverlookedisthat,withouttherestrictionthatjJj=2,wehavetheOP-iTIMALLINEARHYPERGRAPHARRANGEMENTproblem.TheSNMheuristicin[DRR95,DRR96]actuallysolvesthisproblem.ThisreportanswersthequestionHowwelldoesSNMperform,whencomparedt

8、ootherheuristicsfortheproblem?"2LinearArrangementsonHypergraphsHypergraphsareimportanttoCADofVLSI[Len90],astheymodelelectricalconnectivity