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

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

作　　者：赵全伟[1] 吴强[1] 刘杰[1] 

机构地区：[1]湖南大学信息科学与工程学院,长沙410082

出　　处：《计算机应用研究》2011年第10期3687-3689,共3页Application Research of Computers

基　　金：国家"863"高技术研究发展计划资助项目(2007AA01Z104);湖南省自然基金资助项目(07JJ6136);中央高校基本科研业务费资助项目

摘　　要：软硬件划分已被证明是NP完全问题,大多数研究主要集中在寻找各种快速的近似算法,常见的有爬山法、遗传算法、模拟退火、禁忌搜索等。这些算法大多只能处理小规模问题,而且是单纯从算法角度来研究软硬件划分问题,并没有考虑系统成本。以软硬件协同函数库为统一抽象模型,将系统执行时间、系统成本以及硬件面积等因素融入到0-1动态规划算法中,并根据实际情况分析改进0-1动态规划算法的求解过程,得到划分方案。最后通过实验验证了该算法的正确性和有效性。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.

关 键 词：软硬件划分 0-1动态规划 现场可编程门阵列 

分 类 号：TP302[自动化与计算机技术—计算机系统结构]