资源描述：
《基于深度优先贪婪搜索的可重构硬件任务划分算法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、基于深度优先贪婪搜索的可重构硬件任务划分算法文章编号:1001-9081(2012)01-0158-05doi:10.3724/SPJ.1087.2012.00158?摘要:针对可重构计算硬件任务划分通信成本较小化的问题，提出了一种基于深度优先贪婪搜索划分(DFGSP)算法。首先，从待调度的就绪队列中取出队首任务，在某一硬件面积约束下，按深度优先搜索(DFS)方式扫描一个计算密集型任务转换来的有向无环图(DAG),逐个划入满足要求的节点；然后，一遇到不满足面积要求的任务节点时，就计算当前划分模块间输出边数(可量化为通信成本)
2、；最后，跳过当前不满足要求的任务节点，继续搜索该点之后处于就绪状态的节点，当搜索到满足要求的点时，按加入该点后不增加当前划分块间输出边数和尽可能填满可重构运算阵列的原则进行。实验结果表明，与现有的簇划分(CBP)、簇层次敏感两种划分算法相比，提出的算法获得了最小划分模块数和平均跨模块间I/O边数最小的均值，通过在可重构任务编译器上的实际验证，算法显著地改善了硬件任务的划分效果，而且运行开销没有明显增加。?关键词:可重构计算；时域划分；深度优先贪婪搜索；通信成本；资源约束；硬件碎片?中图分类号:TP302文献标志码:A?■Ab
3、stract:Thispaperproposedahardwaretaskpartitioningalgorithmaccordingtotheproblemsofcommunicationcostminimuminreconfigurablecomputing,calledDFGSP(DepthFirstGreedySearchPartitioning).Atfirst,thefronttaskwastakenfromthereadyqueue,aDirectedAcyclicGraph(DAG),whichwastran
4、sformedfromacomputing・intensivetask,wasseannedandpartitionedbyDepthFirstSearch(DFS).Then,thenumberofoutputting-edges(quantizedtocommunicationcost)ofcurrentpartitioningmodulewascomputedwhenthetasknodedidnotmeettheareaconstraints.Finally,thereadytasknode,whichconside
5、redsufficientlypartitioningmoduleoutputting・edgeswhichwerenotincreasingandmadegooduseofreconfigurableresourceshardwarefragmentassoonaspossible,wasseannedandpartitioned,afterskippingthetasknodewhichdidnotmeettheareaconstraints.IncomparisonwiththeCluster-BasedPartiti
6、oning(CBP)algorithmandLevelSensitiveCluster-BasedPartitioning(LSCBP)algorithm,theexperimentalresultsshowthattheproposedalgorithmcanobtaintheleastnumberofparUtioningmodulesandtheleastaveragenumberofinput-outputedgescrossingmodules,andtheprac廿calresultsonreconfigurab
7、letaskcompiler,作者电话回复要求改过。indicatetheproposedalgorithmgetsaprominentimprovementinhardwaretaskpartitioningperformaneeoverpreviousalgorithms,whiletherun-timeefficiencyispreserved・Keywords:reconfigurablecomputing;temporalpartitioning;depthfirstgreedysearch;communicati
8、oncost;resourcerestraint;hardwarefragment0引言?可重构计算结构可以看成是由时间和空间构成的二维结构［1］,其具有时间域上的可编程性和空间域上可配置性。目前，可重构计算技术在音、视频的压缩［2］,嵌入式与可重构计算机系统［3-5］,图像处理［6］等方
