Architectures] Domain-specific architectures General Terms Algorithms

DistributedEmbeddedSystems

InstituteforTechnical

Informatics

GrazUniversityofTechnology

A-8010Graz,Austria

AllanTengg

tengg@iti.tugraz.at

InstituteforTechnical

Informatics

GrazUniversityofTechnology

A-8010Graz,Austria

AndreasKlausner

klausner@iti.tugraz.at

b.rinner@computer.org

InstituteofNetworkedandEmbeddedSystemsKlagenfurtUniversityA-9020Klagenfurt,Austria

BernhardRinner

CategoriesandSubjectDescriptors:D.2.11[SoftwareArchitectures]:Domain-specificarchitecturesGeneralTerms:Algorithms

Keywords:Geneticalgorithms,taskallocationproblem

1.SUMMARY

ThemainideaofourI-SENSEresearchproject[1]istoprovideagenericarchitecturewhichsupportsonlinedatafusiononadistributedembeddedsystem.Toaccomplishhighflexibility,wedecidedthatthefunctionaldescriptionofadatafusionsystem,thesocalledfusionmodel,shouldbedefinedindependentlyofthepresenthardwareconfigu-ration,thesocalledhardwaremodel.Itistheobjective,toautomaticallyfindavalidmappingofthefusionmodeltothishardwaremodel.CurrentlynotmanypublicationscanbefoundthatreportthesuccessfulutilizationofGPtosolvesuchtaskallocationproblems.Herewepresentourtaskal-locationmethodthatutilizesGPtofindasuitablesolutioninanadequatetimeforthisoptimizationproblemknowntobeNP-complete.Toimprovetheperformanceofthealgo-rithmsignificantlyforourproblemdomain,weaddedafewheuristicswhichareoutlinedinthefollowing.

Thefusionmodelconsistsbasicallyofasetofcommu-nicatingtaskswhichmayberepresentedasataskgraphG=(N,E).Itisassumedtobeaweighteddirectedacyclicgraph,consistingofnodesN=(n1,n2,...,nm)whichrepre-sentthefusiontasksandtheedgesE=(e12,e13,...,enm)thedataflowbetweenthosetasks.Eachnodehassomeproper-ties,describingthehardwarerequirementsofatask.Everyedgeindicatestherequiredcommunicationbandwidthbe-tweentwotasks.

Thehardwaremodeldescribestheheterogenousdistributedembeddedsystem,consistingofdifferentprocessorswithdifferentpropertiessuchascoretype,clockfrequencyandavailablememory,wherethefusionapplicationshouldrunon.EachhardwarenodehasatleastonegeneralpurposeCPUandoptionallysomedigitalsignalprocessors(DSPs)coupledstronglyviaPCIandI/Oportstoconnectsensors.Ethernetisusedtointerconnectthehardwarenodes.

Thetraditionalgeneticalgorithmsuffersamajordraw-backifitisappliedtoourproblem:Thepercentageofvalidcombinationsisusuallyverysmallcomparedtoallpossible

Copyrightisheldbytheauthor/owner(s).

GECCO’07,July7–11,2007,London,England,UnitedKingdom.ACM978-1-59593-697-4/07/0007.

taskallocations.Whencreatingapurerandominitialpopu-lation,itishighlylikelythatthereisnotasinglevalidchro-mosomeinthepopulation.AsproposedbyJensGottlieb[2],apenaltyinthefitnessscoreforinvalidchromosomeshasproventobeagoodapproachforsuchsituations.

Wefoundfurther,thatthestraightforwardimplementa-tionoftheGAwithpenaltiesperformsworsewithincreas-ingproblemsize,ifthereisnocorrespondenceofthegenesandgeneticoperationsintherealworldproblem.Withoutprecautionneithertheorderofthegenes,northepointofintersectioninthecrossoveroperatorhasameaninginthetaskallocationproblem.Thisleadstoaunrestrictedsearchintheentiresolutionspacewiththedisadvantagethatmanyinvalidallocationshavetobecheckedandruledout.

Wepropose,thattightlycoupledtasksshouldbemappedonadjacentgenesinthechromosome.Nowthegeneticcrossoveroperatorhasarealworldmeaning:Ratherthanindividualtaskswithoutrelationamongeachother,entirecoupledclustersoftasksareexchangedbythecrossoverop-eratorwhichleadstoabetterperformance.Iftheclusteringideaisintroducedtotheinitialpopulationaswell,afurtherenhancementcanbeaccomplished.Insteadofplacingthetasksintheordertheyappearinthefusionmodel,taskswithhighcommunicationrequirementareplacedfirstatarandomprocessortogetherwiththeirheavycoupledtasks.Thisresultsinarelativelyfitinitialpopulationandthereforefastersearch,comparedtoapurerandominitialpopulation(cp.table1).

TasksCPUsComplexityNormalEnhanced156easy2.831.842610medium13.936.792014hard81.2024.002614hard58.4038.932012veryhard203.8625.79Table1:Iterationstofindaoptimalconfiguration

2.REFERENCES

[1]A.Klausner,B.Rinner,andA.Tengg.I-SENSE:Intelligent

embeddedmulti-sensorfusion.InProceedingsofthe4thIEEEInternationalWorkshoponIntelligentSolutionsinEmbeddedSystems(WISES),Austria,June2006.

[2]J.Gottlieb.Onthefeasibilityproblemofpenalty-based

evolutionaryalgorithmsforknapsackproblems.InE.J.W.Boers,S.Cagnoni,J.Gottlieb,E.Hart,P.L.Lanzi,G.R.Raidl,R.E.Smith,andH.Tijink,editors,ApplicationsofevolutionaryComputing:Proc.EvoWorkshops2001,Berlin,2001.