基于改进0-1动态规划的软硬件划分算法研究*

软硬件划分已被证明是NP完全问题,大多数研究主要集中在寻找各种快速的近似算法,常见的有爬山法、遗传算法、模拟退火、禁忌搜索等.这些算法大多只能处理小规模问题,而且是单纯从算法角度来研究软硬件划分问题,并没有考虑系统成本.以软硬件协同函数库为统一抽象模型,将系统执行时间、系统成本以及硬件面积等因素融入到0-1动态规划算法...

SW/HW partition algorithm research based on improved 0-1 dynamic programming

SW/HW partition has been proved to be NP-completeness. Most studies concentrate on the seeking for various rapid approximate algorithms, among which are common include: hill-climbing method, genetic algorithm, simulated annealing(SA), etc. However, most of these algorithms can only solve problems with small-scale, and which study the problem of SW/HW partition solely on algorithmic aspect, without considering the system cost. Based on the uniform abstract model of SW/HW co-function-library, this paper incorporated some factors into 0-1 dynamic programming algorithm, which included system execution time, system cost and hardware area. Then, obtained the partition plan by improving the computing method of 0-1 dynamic programming algorithms according to practical situation. At last, experiments validate the correctness and effectiveness.