ggpu,zxp,joycy,qzy￥ Computer aided hardware/software partitioning is one of the key challenges in hardware/software co-design. This paper describes a new approach to hardware/software partitioning for multiple hardware-devices model. The partitioning is t

formalmodelofhardware/softwarepartitioningusingtimedautomata.SomepartitioningexperimentsareconductedinSection6.Finally,Section7isashortsummary.

2OverviewofthePartitioningApproach

Figure1.ArchitectureandPartitioningFlow

Inthispaper,wepresentanautomaticpartitioningap-proachwhichadoptsanabstractarchitecturecomposedofacoprocessorboardandmultiplehardware-devicessuchasFPGAs,ASICetc,wherethecommunicationbetweensoft-wareandhardwareissynchronizedbymeansofthesystembus.Furthermore,thefollowinggoalswillbeachieved:

Explorethehiddenconcurrency,i,e, ndtheprocesseswhichcanbeexecutedinparallelfromtheinitialse-quentialspeci cation.

Obtaintheoptimalperformanceoftheoverallprogramintermsofthelimitedresourcesinhardwareafterpar-titioning.Thecommunicationwaitingtimebetweensoftwareandhardwarecomponentsisconsideredaswell.

Severalindustrialcasestudiesareconductedusingthisapproach,whichshowsthatthemethodproposedhereiseffective.

Givenahighlevelspeci cation,systemdesignersarere-quiredtodividethespeci cationintoasetofbasicpro-cesses(blocks)whichareregardedascandidateprocessesforthepartitioningphase.Onaccountoftheparallelstruc-tureofsoftwareandhardwarecomponents,thehiddencon-currencyamongtheprocesseswillrelaxprecedencecon-ditionofthepartitioning,thatis,anoptimalsolutionwillbeobtainedfromalargersearchspace.Twoalgorithmsaredesignedtoexplorethecontrolanddata owdepen-dencyfortheinitialspeci cation.Toallocatetheprocessesintothesoftwareandhardwarecomponents,wemodelthepartitioningprocessasthenetworkoftimedautomata,andthustransformthepartitioningtoareachabilityproblemoftimedautomata[7].BymeansoftheoptimalreachabilityalgorithmimplementedinmodelcheckerUPPAAL[15],thebestpartitioningsolutioncanbeobtained.

Thepaperisorganizedasfollows.Section2presentstheoverviewofourtechnique.Section3exploresthede-pendencyrelationbetweenprocesses.Section4describesa

2

Inthissectiontheoverviewofourapproachtohard-ware/softwarepartitioningproblemispresented.Thepar-titioning owisdepictedasFigure1.

Inpro lingstage,asystemspeci cationisdividedintoasetofbasiccandidateprocesseswhichwillnotbesplitfur-ther.However,thereisatrade-offbetweenthegranularityofthecandidatesandthefeasibilityofoptimization.Ifpar-titioningisperformedata ner-grainlevel,thecostofsolv-ingthepartitioningproblemwillincreasesigni cantly.Fur-thermore, ner-graincandidateprocesseswillbringheavycommunicationcost.Ontheotherhand,coarse-granularitywillrestrictthespaceofpossibilities,therefore,mayreducetheconcurrencyandincreasethewaitingtimeforcommu-nication.Weleavethischoicetothedesignerstorepeatthepro lingprocessaslongasthepartitioningresultsarenotsatis edwithaccordingtothecurrentgranularityofcandi-dateprocess.Oncethedesignerdecidesthegranularity,theinitialspeci cationistransformedintoasequentialcompo-sitionofcandidateprocesses,thatis,,wheredenotesthethprocess.

Theanalyzingphaseexploresthecontrolanddata ow

.Thedatadependencyamongprocesses

owdependencyisasimportantasthecontrol owdepen-dency,andhelpstodecidewhetherdatatransferoccursbe-tweentwoprocesses.ThedetailsarediscussedinSection3.Ourgoalistoselectthoseprocesseswhichyieldthehighestspeedupifmovedtohardware.Moreprecisely,thetotalexecutiontimeisminimizedintermsofthelimitedresourcesinhardware.Theoverheadoftherequiredcom-municationbetweenthesoftwareandhardwareshouldbeincludedtoo.Thesynchronouswaitingtimewillbeconsid-eredintheperformanceofthepartitioningaswell.Thispartitioningisactuallyaschedulingproblemconstrainedbyprecedencerelation,synchronouscommunicationandlimitedresources.Wetransformtheschedulingproblemintoareachabilityproblemoftimedautomata(TA)[7]andobtaintheoptimalresultusinganoptimalreachabilityal-gorithm.Automaticmodelcheckingtoolsfortimedau-tomataareavailable,suchasUPPAAL[15],KRONOS[6]andHyTEch[10].WeusetheUPPAALasourmodellingtooltoconductsomepartitioningexperiments(Section7).Whenthepartitioningprocessis nished,weobtainthefollowingform:

whereprocessset

allocatedinsoftwarewiththeform,becausetheprocessorcanonlydeal