计算机应用
計算機應用
계산궤응용
COMPUTER APPLICATION
2012年
1期
158-162
,共5页
可重构计算%时域划分%深度优先贪婪搜索%通信成本%资源约束%硬件碎片
可重構計算%時域劃分%深度優先貪婪搜索%通信成本%資源約束%硬件碎片
가중구계산%시역화분%심도우선탐람수색%통신성본%자원약속%경건쇄편
针对可重构计算硬件任务划分通信成本较小化的问题,提出了一种基于深度优先贪婪搜索划分(DFGSP)算法.首先,从待调度的就绪队列中取出队首任务,在某一硬件面积约束下,按深度优先搜索(DFS)方式扫描一个计算密集型任务转换来的有向无环图(DAG),逐个划入满足要求的节点；然后,一遇到不满足面积要求的任务节点时,就计算当前划分模块间输出边数(可量化为通信成本)；最后,跳过当前不满足要求的任务节点,继续搜索该点之后处于就绪状态的节点,当搜索到满足要求的点时,按加入该点后不增加当前划分块间输出边数和尽可能填满可重构运算阵列的原则进行.实验结果表明,与现有的簇划分(CBP)、簇层次敏感两种划分算法相比,提出的算法获得了最小划分模块数和平均跨模块间I/O边数最小的均值,通过实际验证,算法显著地改善了硬件任务的划分效果,而且运行开销没有明显增加.
針對可重構計算硬件任務劃分通信成本較小化的問題,提齣瞭一種基于深度優先貪婪搜索劃分(DFGSP)算法.首先,從待調度的就緒隊列中取齣隊首任務,在某一硬件麵積約束下,按深度優先搜索(DFS)方式掃描一箇計算密集型任務轉換來的有嚮無環圖(DAG),逐箇劃入滿足要求的節點；然後,一遇到不滿足麵積要求的任務節點時,就計算噹前劃分模塊間輸齣邊數(可量化為通信成本)；最後,跳過噹前不滿足要求的任務節點,繼續搜索該點之後處于就緒狀態的節點,噹搜索到滿足要求的點時,按加入該點後不增加噹前劃分塊間輸齣邊數和儘可能填滿可重構運算陣列的原則進行.實驗結果錶明,與現有的簇劃分(CBP)、簇層次敏感兩種劃分算法相比,提齣的算法穫得瞭最小劃分模塊數和平均跨模塊間I/O邊數最小的均值,通過實際驗證,算法顯著地改善瞭硬件任務的劃分效果,而且運行開銷沒有明顯增加.
침대가중구계산경건임무화분통신성본교소화적문제,제출료일충기우심도우선탐람수색화분(DFGSP)산법.수선,종대조도적취서대렬중취출대수임무,재모일경건면적약속하,안심도우선수색(DFS)방식소묘일개계산밀집형임무전환래적유향무배도(DAG),축개화입만족요구적절점；연후,일우도불만족면적요구적임무절점시,취계산당전화분모괴간수출변수(가양화위통신성본)；최후,도과당전불만족요구적임무절점,계속수색해점지후처우취서상태적절점,당수색도만족요구적점시,안가입해점후불증가당전화분괴간수출변수화진가능전만가중구운산진렬적원칙진행.실험결과표명,여현유적족화분(CBP)、족층차민감량충화분산법상비,제출적산법획득료최소화분모괴수화평균과모괴간I/O변수최소적균치,통과실제험증,산법현저지개선료경건임무적화분효과,이차운행개소몰유명현증가.
