A Level Sensitive Cluster Based Partitioning Algorithms for Reconfigurable Systems

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|²+|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.