计算机辅助设计与图形学学报
計算機輔助設計與圖形學學報
계산궤보조설계여도형학학보
JOURNAL OF COMPUTER-AIDED DESIGN & COMPUTER GRAPHICS
2015年
4期
754-763
,共10页
可重构计算%时域划分%通信成本%资源约束%硬件碎片利用
可重構計算%時域劃分%通信成本%資源約束%硬件碎片利用
가중구계산%시역화분%통신성본%자원약속%경건쇄편이용
reconfigurable computing%temporal partitioning%communication cost%resource restraint%hard-ware-fragment utilization
针对面积约束下的可重构硬件任务划分问题,提出一种通信成本和硬件碎片利用的簇划分算法。根据簇划分算法的思想,在某一硬件面积的约束下,从待调度的就绪队列中节点依次划入到当前块,在划分过程中,若遇到不满足要求的节点就跳过,并继续搜索可划入到当前块且没有增加块间边数的节点。每划入一个节点就更新其后继的入度,如果入度为0且满足要求,将其直接划入;否则动态考查其前驱,如果前驱所需的面积满足规定的阈值,则将该节点后继和前驱一并划入到当前块。通过充分考虑节点权值、节点间的依赖度、层次小的节点优先划入等因素构造响应比函数,以动态地调整就绪列表节点的调度次序。实验结果表明,与簇划分算法和簇层次敏感划分算法相比,文中算法在划分块间非原始I/O次数、划分块数等方面均获得了较好的改进;在减少块间通信成本方面,该算法具有合理性和可行性。
針對麵積約束下的可重構硬件任務劃分問題,提齣一種通信成本和硬件碎片利用的簇劃分算法。根據簇劃分算法的思想,在某一硬件麵積的約束下,從待調度的就緒隊列中節點依次劃入到噹前塊,在劃分過程中,若遇到不滿足要求的節點就跳過,併繼續搜索可劃入到噹前塊且沒有增加塊間邊數的節點。每劃入一箇節點就更新其後繼的入度,如果入度為0且滿足要求,將其直接劃入;否則動態攷查其前驅,如果前驅所需的麵積滿足規定的閾值,則將該節點後繼和前驅一併劃入到噹前塊。通過充分攷慮節點權值、節點間的依賴度、層次小的節點優先劃入等因素構造響應比函數,以動態地調整就緒列錶節點的調度次序。實驗結果錶明,與簇劃分算法和簇層次敏感劃分算法相比,文中算法在劃分塊間非原始I/O次數、劃分塊數等方麵均穫得瞭較好的改進;在減少塊間通信成本方麵,該算法具有閤理性和可行性。
침대면적약속하적가중구경건임무화분문제,제출일충통신성본화경건쇄편이용적족화분산법。근거족화분산법적사상,재모일경건면적적약속하,종대조도적취서대렬중절점의차화입도당전괴,재화분과정중,약우도불만족요구적절점취도과,병계속수색가화입도당전괴차몰유증가괴간변수적절점。매화입일개절점취경신기후계적입도,여과입도위0차만족요구,장기직접화입;부칙동태고사기전구,여과전구소수적면적만족규정적역치,칙장해절점후계화전구일병화입도당전괴。통과충분고필절점권치、절점간적의뢰도、층차소적절점우선화입등인소구조향응비함수,이동태지조정취서렬표절점적조도차서。실험결과표명,여족화분산법화족층차민감화분산법상비,문중산법재화분괴간비원시I/O차수、화분괴수등방면균획득료교호적개진;재감소괴간통신성본방면,해산법구유합이성화가행성。
To cope with the problem of reconfigurable hardware task partitioning under area constraints, this pa-per presents a Communication-cost and Hardware-fragment Utilization Cluster Partitioning (CHUCP) algorithm. According to the idea of cluster based partitioning (CBP) algorithm, the nodes from the ready queue to be sched-uled are partitioned sequentially to the current modules under the constraints of a hardware area. In the process of partitionings, the nodes, which do not meet the requirements, are overlooked, and the nodes, which do not in-crease in the number of edges between the two partitionings, are found and partitioned to the current partitionings. As a node is partitioned, the indegrees of its successors will be updated. If the indegrees of its successors are zero and meet the requirements, its successors will be partitioned; if the indegrees of its successors are not zero, its precursors will be examined dynamically. The areas of its precursors meet the specified thresholds, then its suc-cessors and precursors will be partitioned to the current modules. In order to adjust dynamically the lists of node scheduling order, the response ratio function is constructed with the guideline of making good use of the node weights, the dependence between two nodes, the priority of low level nodes, etc. In comparison with cluster based partitioning (CBP) and level sensitive cluster based partitioning (LSCBP) algorithm, the experimental results show that, the proposed algorithm can get better improvements in times of non-input and non-output, the number of mod-ules. As for decreasing the communication cost of modules, the proposed algorithm has rationality and feasibility.