NodeRank:一种高效软硬件划分算法

NodeRank:An Efficient Algorithm for Hardware/Software Partitioning

软硬件协同设计是现代嵌入式系统开发的核心技术,如何将系统功能划分到软件和硬件部分上是软硬件协同设计的关键环节.文中将软硬件划分问题看作带有动态通信代价的变异0-1背包问题,提出一种基于迭代排序思想的NodeRank算法.该算法通过迭代排序计算结点通信代价的期望值,进而求解背包问题,构造出软硬件划分问题的优质启发解.实验结果证明,在计算-通信代价均衡,弱实时性约束条件下,NodeRank对边点比大于等于2的任务图的处理结果与目前已知效果最好的禁忌搜索方法的平均性能差距不超过1.2%,而平均时间开销可以节约95%.在通信代价较高的条件下,NodeRank与禁忌搜索相比,可提升性能达3.5%,并节约时间超过75%.

Hardware/software （HW/SW） co-design is a key technique for the development of modern embedded systems. HW/SW partitioning is a crucial step in HW/SW co-design that determines which components of the computer system are implemented on hardware and which ones on software. In this paper, we present an efficient algorithm for hardware/software partitio- ning： NodeRank. Formulating the HW/SW partitioning problem as a variant of 0-1 knapsack problem with dynamic communication costs, NodeRank iteratively calculates the rank of each node, updates the expectation of communication costs, and thus generates the corresponding heu- ristic solutions to the problem. Experimental results show that, when the computation cost and communication cost are roughly of equal weight and the real-time constraint is loose, NodeRank is inferior to the state-of-the-art Tabu Search method at most by 1.2% for task graphs with edge to node ratio equal or greater than 2, but saves more than 95% running time on average. For communication-intensive cases, NodeRank outperforms Tabu Search by up to 3.5% and saves runtime over 75 %.