摘要
对于可重构计算中面积约束条件下的任务划分问题,提出一种基于簇的、层次敏感的划分LSCBP算法.该算法按照依赖优先、最早最先和碎片利用三原则构造了新的启发函数ASLevel,能够跟踪节点分配过程并进行动态调整;它克服了CBP算法机械选取节点进行划分的缺点,同时算法复杂度也增大到O{|V|2+|E|}.对随机生成的任务图(节点数小于250)的划分实验表明:对于相同的DAG,LSCBP算法能够比CBP算法获得更少的任务簇(可重构资源需求量)和簇间有向边(通信代价).
This paper presents a DAG （directed acyclic graph） partitioning algorithm for reconfigurable computing, called LSCBP （Level Sensitive cluster based Partitioning） algorithm, which partitions the whole task graph into small segments and keep task precedence relations under area constraints. The proposed heuristic function AS_Level can denote allocation priorities of the ready list and will be adjusted during the partitioning process. The heuristic function is constructed with the guideline of ＂dependence first＂, ＂earliest time first＂ and ＂fragment reuse＂. The proposed algorithm can overcome the drawback of CBP algorithm and its time complexity increases to O {｜ V｜^2 ＋ ｜E｜}. For the same DAGs, the experimental results on random DAGs show that LSCBP algorithm can get less task-clusters （meaning less requirements for reconfigurable devices） and inter-cluster edges （meaning less communication costs） than CBP algorithm.
出处
《计算机辅助设计与图形学学报》
EI
CSCD
北大核心
2006年第5期667-673,共7页
Journal of Computer-Aided Design & Computer Graphics
基金
国防预研项目基金
关键词
可重构系统
有向无环图
图划分
任务簇
FPGA
reconfigurable computing system
directed acyclic graph
graph partitioning
task cluster
FPGA
