KroneckerExpressions
PerLindgren
DivisionofComputerEngineeringLule˚aUniversityofTechnology
97187Lule˚aSwedenpln@sm.luth.se
RolfDrechslerBerndBecker
InstituteofComputerScienceAlbert-Ludwigs-University
79110FreiburgimBreisgau,Germanydrechsle/becker@informatik.uni-freiburg.de
Abstract
InthispaperweoutlineamethodforLook-upTable-FPGA(LUT-FPGA)synthesisfromminimizedMulti-ValuedPseudoKroneckerExpressions(MVPSDKROs).Byre-strictinglogicminimizationtoconsideronlyeasilymap-pableexpressions,aregularCellularArchitecture(CA)lay-outwithoutroutingoverheadisobtained.Inthiswayourmethodcombineslogicminimization,mappingandrouting.ThetransformationintotheMVdomainreducestheareaasthenumberofproductsinthePSDKROexpressioncanbefurtherminimized.DerivingtheexactminimumMVPS-DKROisknowntobehardorevenintractable.Weaddressthisbyapplyingpruningtechniquesbasedoncostestima-tionanddynamicmethodstofindsuitablevariableorder-ings.ResultsonasetofMCNCbenchmarksshowthead-vantagesoftheproposedminimizationmethods.
1Introduction
TheincreasingcomplexityofmodernVLSIcircuitryisonlymanageablethroughadvancedCADsystemswhichasoneimportantcomponentincludelogicsynthesistools.ProblemsencounteredinsynthesiscanoftenbeformulatedintermsofBooleanfunctions.OneinterestingdesignstyleisbasedonFPGAs[1,8].ManypowerfultoolshavebeendevelopedinthepasttominimizeBooleanfunctionsandmapthemtocommerciallyavailableFPGAtypes.Oneofthemajordrawbacksofmostmethodspresentedsofaristhattheyconsiderlogicminimization,mappingandrout-ingindependently,i.e.,duringsynthesisonly“synthesismeasures”likenumberofgateequivalentsareconsidered.Theseapproachessufferfromlargeareaoverheadincaseswherethehighlyoptimizednetlistdonotfitwellonthetar-getFPGA[14].
Recently,firstapproacheshavebeenpresentedcombin-ingminimization,mappingandrouting(seee.g.[10]).Byrestrictingthesynthesisprocesstoconsideronlyeasily
2.1Previouswork
In[10]acomprehensivesynthesismethodforCAswaspresented.TheresultingrectangularstructureimplementsaComplexMaitraLogicArray(CMLA)havinga“complex”inputplaneanda“collecting”outputplane.ThestructureissimilartothatofanAND-EXORPLA,butintheCAeach“row”canimplementabroaderclassoffunctions,hencepossiblyreducethenumberofrequired“rows”.Aforward(reverse)Maitratermisafactoredformrecursivelydefinedas;()whereisaforward(reverse)Maitraterm,isaliteraloccurringonlyonceintheex-pressionandisaBooleanfunctionoftwoarguments.
whereeachliteraloccursonlyonce
intheexpressionformsabidirectionalMaitraterm.The“complex”termsusedin[10]areforward,reverseorbidi-rectionalMaitraterms,derivedbytheuseofa“cube”basedESOPminimizer.Thisfactoredformfitsdirectlyontoa“row”inCAswhereeachcellcomputesa2-inputfunction,thusaregularstructureisobtained.Anotherapproachtode-riveMaitratermswaspresentedin[5],whereLeeadoptsanelegantDDbasedmethodsimilartothatusedforPSDKROminimization.
2.2Synthesisfrommulti-valuedPSDKROs
Theapproachesdescribedintheprevioussectionareef-ficientlyutilizingonlyCAswhereeachcellimplementsa2-inputfunction.Inthefollowingweoutlineasynthesismethodbasedonmulti-valuedPSDKROminimizationap-plicabletoavailable
--LUTFPGAarchitectures(seeFigure1).
Eachproductina-valuedPSDKROexpression,can
becomputedbyaCAof
-LUTs(analogouslytothe2-valuedcase[5])asshowninFigure2“InputPlane”.Theresultingoutputfunction(s)canbecomputedastheEXORofsuchproducts(seeFigure2“OutputPlane”).ManyavailableFPGAs(e.g.,XilinxC3000,C4000,AT&TOrcaetc.)cancompute(1)outputfunctions,undertheconstraintthatsomeinputsareshared.AsshowninFig-ure2,theinputvariables(encodingaMVvariable)arecommontoeachLUT,thusmeetingthesharingcon-straint.Besidesfortheinputvariablesallinterconnectionsareensuredtobelocal.E.g.,thislayoutallowsustoef-ficientlyutilize“directinterconnects”betweencellsand“longlines”fortheinputvariablesintheXilinxarchitec-tures.Ingeneral,synthesisfora--LUTarchitecture
isperformedbyminimizationof
-valuedPSDKROs.Anupperboundofrequiredcellsforafunctionisgiven
by
:(OutputColumns)-valuedPSDKRO()
(Rows)
Thisoutlinesafirst“naive”approachtoCAsynthesisfromMVPSDKROs.ByextendingMaitratermfactoriza-tion[5]totheMVcaseweexpecttoreducethenumber
Xx1
1xk-pk -p inout-LUTk-pppFigure1.
-
-LUTFPGAcell.
Input Plane
Output Plane
X1X2X3Xnk-pppCMLAo1opO1
O2Om
4 -1 -LUTinout311FoldingFigure2.Resultingregularlayout.
ofcells.FurthermorewecanapplyPLA-likefoldingtech-niques[10]inthe“InputPlane”,undertheconditionsthatroutingresourcesaresufficientandthatthe“OutputPlane”managestocollecttheresult.Figure2(bottom)showspos-siblefoldingfor--LUTs.Theextensiontodon'tcareassignment[6]forMVPSDKROminimizationisalsoaninterestingtopicforfutureresearch.
3PreliminariesonPseudoKroneckerEx-pressions
Inthefirstsubsectionwebrieflyreviewtheessentialdef-initionsof(2-valued)PseudoKroneckerExpressions(PSD-KROs).(Formoredetailssee[13,3].)Inthenextsubsec-tionwediscussthepropertiesofMVPSDKROexpressions,detailscanbefoundin[13].
3.12-ValuedPSDKROExpressions
Let()denotethecofactorofwithrespectto()andisdefinedas,beingtheExclu-siveORoperation.ABooleanfunctionthenberepresentedbyoneofthefollowingformulae:
can(1)(2)
(3)
Ifweapplytoafunctioneither,orwegettwosub-functions.Toeachsub-functionagain,orcanbeapplied.Thisisdoneuntilconstantfunctionsarereached.Ifwemultiplyouttheresultingexpressionwegeta2-levelAND/EXORform,calledaPSDKRO.
Thedecompositionsareappliedwithrespecttoafixedvariableordering.Notethatthechoiceofthevariableorder-inginwhichthedecompositionsareappliedandthechoiceofthedecompositionpersub-functionlargelyinfluencesthesizeoftheresultingrepresentation,andmayvaryfromlin-eartoexponential.
3.2Multi-ValuedPSDKROExpressions
Inthegeneral-valuedcaseInistheencodedfollowingbyweBooleanassume
variablesavariablewhere.Let.
denotethecofactorsofwithrespectto.ABooleanfunctionby
(correspondingisrepresented
totheMVShannonexpansion).ThenumberofpossibleEXORcombinationsofthecofactorsis4-valuedcasethe15successors.E.g.,in,,,,,,,(the,
,,,,,,),inthe16-valuedcasethe255successors
),andinthegeneralcasethe
Toderivesuccessorsthenumber().
ofPSDKROexpansions(i.e.,non-linearcombinationsofsuccessors)inthegeneral-valued
caseonewouldneedtoconsider
possiblecombina-tions.In[13]acomputerenumerationforthe4-valuedcaseshowsthat840expansionsexist,buttheproblembecomes
computationallyintractablebyenumerationfor
.Ifweapplya-valueddecompositionto,wegetsub-functions,forwhichwecanrecursivelyapply-valuedde-compositionsuntilconstantfunctionsarereached.
Asforthe2-valuedcase,thedecompositionsareappliedwithrespecttoafixedvariableorder.Boththechoiceofdecompositionsappliedandtheorderofwhichthedecom-positionsarecarriedoutwillaffectthesizeoftheresult-ingrepresentation.Iftion
variablesintoMVvariablesthewechoicestartoutwillalsooffromgroupinga2-valuedfunc-largelyinfluencethe2-valuedtheresult.
3.3PSDKROMinimization
Inthissectionwereviewpreviouslypresented(DD
based)algorithmsforminimizingthenumberofproductsforPSDKROexpressions.
In[13]amethodforexact2-valuedPSDKROminimiza-tionbasedonETDDswaspresented.Thethreesuccessors,andarestoredforeachnode.Itbeenproventhatthememorycomplexityis
similarminimizationmethodbasedonOrderedBinary.has
De-AcisionDiagrams(OBDDs)[2]hasbeenpresentedin[3],havinglowercostforeachnodeasisnotstored.In[7]thismethodwasextendedwithheuristicstrategiesfor
prune
pruneprunefafbfafbpapb
papb
max( , )papb
prune - min( , )papb
fcfc(a)
(b)
Figure3.Pruningofsearchspace
searchspacepruning,tunabletotradeoffqualityforcom-putationalresources.
IntheDDrepresentationofa1-pathrepresentsaprod-uctterm.Thebasicminimizationalgorithmrecursivelytra-versesfromthetoptowardstheterminals.AteachnodeanEXORoperationiscarriedout(orpriortominimizationintheETDDapproach)whichbytheuseofOBDDscanbeperformedinpolynomialtime[2].FromthefactthatforeachofthedecompositionformulaefromSection3.1onlytwooutofthethreepossiblesuccessors,andareneededtorepresentthefunction,wecanchoosethetwoleastcostlyinordertominimizetheresultingPSDKRO.Thiscaneasilybeformulatedbyasimplerecursivealgo-rithmonOBDDs[3].
For4-valuedPSDKROminimizationanextensionoftheETDDapproachwaspresentedin[13].All15successorsarerecursively(andexhaustively)computedandstoredinanOrderedPenta-decimalDecisionDiagram(OPDD).Outofthe840possible4-valuedexpansions,theonehavingtheleastcostischosenforeachnodeinthediagram.In[12]aheuristicmethodbasedonextendedtruthtableswaspre-sented,greedilychoosingthedecompositionthatminimizestheresultingexpression.
ThequalityoftheresultingPSDKROsdependsonthevariableorderingappliedaswellasthegroupingofinputvariablesintheMVcase.In[13]aheuristicfrom[11]wasapplied(inapreprocessingstep)togroup2-valuedvariablesinto4-valuedvariables.In[7]dynamicreorderingstrategiesareshowntodrasticallyreducethe(2-valued)PSDKROsinmanycases.
4NewPSDKROMinimizationmethods
Inthissectionwefirstintroducepruningtechniquesbasedoncostestimationfor2-valuedPSDKROminimiza-tion,andshowhowbothexactandheuristicresultscanbeobtained.InSection4.2wepresenttheextensionto4-valuedPSDKROminimizationforheuristicresults,andfinallywegiveamethodforheuristic-valuedPSDKROminimizationinSection4.3.
4.12-valuedPSDKROMinimization
Totheoriginalalgorithm[13,3]wehaveaddedanum-berofnewfeatures;theuseofcostestimation,apruning
prodpsdkro(node,int)1if(==)return;
defined)return;2if(
3derivecofactors,andcompute=EXOR(,
,and4computecostestimates
5sortsuccessorsinincreasingcostorder6=psdkro(,);7(greedy)if()returnMAXINT;
=psdkro(,);8
9if(min(,))returnMAXINT;
=psdkro(,pf(,,));1011=++-max(,,);12return;
prodpsdkro);
4v(
4v(
)+psdkro)+psdkro
Figure4.Algorithmusingcostestimation.parameterandthepossibilitytoobtainheuristicresultsbyagreedyapproach(thelattertwoalsoappearsin[7]).
Wemakethefollowingobservations:TheOBDDrepre-sentationholdsaninitial(non-optimal)PSDKROsolution
)withhavingonlyShannondecompositions(
.Assumewehavecomputedtheexactcoststhecost
forand(forandrespectively),thenisapartof
max(,),i.e.,mustbelesscostlythesolutioniff
thanatleastoneothersuccessoror(seeFigure3(a)).Givenacostlimit“”,isapartofthesolutioniff
-min(,),sincethecostofsuchadecom-positionismin(,)+,whichinturnmustbelessthan
”(seeFigure3(b)).Ourhandsonexperiencesshow“
thatahighcostfororinmanycasesalsoleadstoahighcostfor.
TheseobservationsareexploitedbythealgorithmshowninFigure4.Theadditionalparameter“”givesacostlimitforthe(sub)functionunderconsideration.Thecost(i.e.,1-paths)oftheinitialOBDDrepresentationsfor,andgiveupperboundcostestimates,and(line4).Thesuccessorsareordered(line5)such
,i.e.,hasthelowestupperthat
bound,henceconsideredasthemostpromisingsuccessor(line6).Aseachdecomposition(S,pDornD)requiresatleastoneoforfurthercomputationcanbeabortedwhenmin(,)(line9).ByreturningMAXINT,thefunctionisensurednottobecomepartofthefinalresult.Thefunction“pf”(line10)combinesthetwoobservations(a)and(b)asthenewpruningvalue,i.e.,min(max(,),
-min(,)).Thisalgorithmfavorspromisingpartsofthesearchspaceandrejectspointlesscomputationsatanearlystagewithoutcompromisingthequalityoftheresult.However,fromourlastobservationabove,inspectingthemostpromisingsuccessorgivesaroughestimateofthecost.Thegreedyapproachinline7utilizesthisestimationtoheuristicallyabortunpromisingcalculations.ForeachnodetheminimalnumberofproducttermsneededfortherepresentationasaPSDKROisstoredinthevariable
.Thus,eachnodehastobeevaluatedonlyonce.Otherpruningaspects,simultaneousminimizationofliteral
prodpsdkromv(
,);
return
;
Figure6.MVPSDKROminimization.
4.4InfluenceofVariableOrdering
In[13]theeffectofDDvariableorderingwasconcludedbyenumeratingallpossibleorderingsforagivenfunctionandminimizingthecorrespondingPSDKROs.However,nomethodtoapproachtheorderingproblemwasreported.Ingeneraldynamicvariableordering[9]hasprovenusefultomanyDDproblems.In[7]dynamicreorderingstrategies(“movetotop”and“sifting”)areappliedto2-valuedPS-DKROminimization.Thefirstmethodseeksthebestbesttopvariableiterativelyuntilnofurtherimprovementisob-tained,whilethelattersiftseachvariabletothepositionthatresultsinalocalminima.Ingeneralthesiftingapproachisabletoderivebetterresultsatthecostofcomputationtime.Thesestrategiescanbeappliedtofindaheuristicor-deringbothfor2-andgeneral-valuedminimization.Inthe-valuedthediagram,2-valuedcase,theusingavariables)-valued“group”-move/siftarevariablesmoved/sifted(encodedby
method.togetherAsacostin
estimatefunctionwecanapplytheupperbound,i.e.,1-pathsinthe-valuedDDrepresentation.Tofindagroup-ingofthe2-valuedvariablesinto-valuedvariables,wecaninitiallyapply2-valuedreorderingtothediagram.
4.4.1Minimizationusing“Free”DDs
IfwerelaxthefixedorderingconstraintforPSDKROs,wecanapply“free”DDstotheminimization.InFigure7weoutlinethe“free”reorderingmethod.Thisapproachcom-binesreorderingwithminimization.Alsointhiscasewehavethechoiceofdifferentcostestimationfunctions.InSection5,weshowhow“free”minimizationgreatlycanimproveonPSDKROresults,andeveninsomecaseschal-lengesbestknownESOPs.
5ExperimentalResults
InthissectionwepresentexperimentalresultsforasetofMCNCbenchmarkfunctions.Allrun-timesaregiveninCPUsecondsonaSunUltra1workstationwith256MbRAM.AllexperimentshavebeencarriedoutontheBDDpackagefrom[15]andwesetaruntimelimitof1000CPUseconds.
prodfree
,);
return
mv(
Figure7.Freeminimization.
InafirstseriesofexperimentsgiveninTable1,wedemonstratetheeffectofpruningbytheuseofcostestima-tion.TheresultsareobtainedforthevariableorderinggivenfromthePLAbenchmarks.Toallowcomparisontoprevi-ouslyreportedbestknownresults[13,3](markedex),mul-tipleoutputfunctionsareencodedbyOutputSelection(OS)nodesplacedatthebottomofthediagram,thusensuringminimizationofalloutputssimultaneously[7].Columnsmarkedestandgreedyreporttheresultsfortheproposed2-valuedminimizer.ForcomparisoncolumnMVgivestheresultsforthegeneralMVPSDKROminimizerappliedtothe2-valuedcase.Thegreedyapproachobtainsminimalornearminimalresultswhilesavingcomputationalresources.InthenextsetofexperimentsgiveninTable2,weshowtheeffectof“free”orderingofnon-symmetricalbench-marks.IncolumnMINTthenumberofproductsforbestpreviouslyknown2-valuedESOPs[4]areshown.DuringreorderingeitherestorMVisappliedtogiveacostes-timate.WeareinmanycasesabletovastlyimproveonpreviouslyreportedPSDKROresults(Table1)andeveninsomecaseschallengebestknownESOPs,whilebeingmagnitudesfaster.InherentintheDDstructureisalsothepossibilityformulti-levelminimizationandsynthesis.Byalsoconsideringsingle-outputminimization[7]weexpecttofurtherimprovetheresults.
InthelastsetofexperimentsgiveninTable3weshowtheextensiontoMVPSDKROminimizationandreportthefirstresultsforupto16-valuedPSDKROs.“-”indicatesthattimelimitwasreached.“*”indicatesafirstexact4-valuedresult.TheinitialordersgivenbythePLAsareusedforinputgroupingandMVvariableorder.ColumnsestandMV,showtheheuristic4-VandthegeneralMVminimiza-tionresults.WhilethegreedysearchofexpansionusedinthegeneralMVminimizer(MV)consumesconsiderablylesscomputationalresources,thequalityoftheresultequalsthatoftheexhaustivesearchmethod(est).Columnsmarkedfreeshowstheresultofthe“free”reorderingmethod.NotethatthegroupingofinputvariablesintoMVvariablesre-mainsunchangedduringreordering.For8-and16-valuedminimizationthedrasticpruningofthesearchspacemaycompromisethequality,anda“grouping”approachfrome.g.2-valuedPSDKROsmaybeapplicable.
Thepresentedresultsaredirectlyapplicabletothecom-binedminimization,mappingandroutingmethodgiven
name
NumberofProducts
CPUTimeinSeconds
greedy
exgreedy5xp147
0.010.02
132132
0.110.01bc0180
5.352.22
1414
0.010.01
duke2108
25.0519.68
117137
2.310.34in742
0.170.13
3131
0.010.01intb500
0.710.80
754877
5.390.19rd5320
0.010.01
63127
0.010.01rd84107
0.010.01
4146
0.020.01t48113
0.010.01
9391247
1.820.18x6dn1045.401.78
est
est
MINT
5xp1400.0610.10add61320.51139.80bc017129.75742.17duke28490.84174.16in21176.74438.36in7352.4419.68inc310.0210.22intb3794.39774.61misex36429.8510744.99
sao2340.088.58t481130.0594.40tial6627.226779.55x6dn
99
7.88
520.81
Table2.Bestknownnumberofproducts.inSection2.2,e.g.
--LUTFPGAsaresynthesizedfrom4-valuedPSDKROs.BytheuseofcostestimationwecanprunethesearchspaceforMVPSDKROs,thusobtainresultsforpreviouslyintractableproblems.Furthermoreweproposea“free”DDbasedminimizationmethodfor2-levelexpressions,insomecaseschallengingbestknownESOPswhilebeingmagnitudesfaster.Itsapplicationtomulti-levelsynthesisisfocusofcurrentresearch.
References
[1]S.D.Brown,R.J.Francis,J.Rose,andZ.G.Vranesic.Field-ProgrammableGateArrays.KluwerAcademicPublisher,1992.[2]R.E.Bryant.Graph-basedalgorithmsforBooleanfunction
manipulation.IEEETrans.onComp.,35(8):677–691,1986.[3]R.Drechsler.PseudoKroneckerexpressionsforsymmetric
functions.InVLSIDesignConf.,pages511–513,1997.[4]T.Kozlowski,E.L.Dagless,andJ.M.Saul.Anen-hancedalgorithmfortheminimizationofexclusive-orsum-
name
16-V
ex
MV
7/10
43353212/713213213226/1116215014814/177522/29109868019/10969511026/104237367/931302915/739233535214/147476014445/3101077/32626138/436362110/443343016/199914/877654159439/5
93
89
88
因篇幅问题不能全部显示，请点此查看更多更全内容