摘要
软硬件划分是软硬件协同设计的关键环节,它决定系统中哪些组件由软件实现,哪些由硬件实现。软硬件划分问题已被证明是NP完全问题。将一类软硬件划分问题看作变异的0-1背包问题,在求解背包问题的算法基础上构造出软硬件划分问题的优质启发解。此外,采用禁忌搜索(Tabu Search)算法对求得的启发解进行改进,在软件开销和通信开销满足一定约束的条件下,使得硬件开销尽可能小。实验结果证明,所提算法对当前最新算法的改进最大可达到28%。
Hardware/software（HW/SW） partitioning is one of the crucial steps in HW/SW co-design.It determines which componented of the system are implemented on hardware and which ones on software.It has been proved that the HW/SW partitioning problem is NP-hard.This paper presented an heuristic algorithm for the HW/SW partitioning problem,which has been treated as an extended 0-1 knapsack problem.Tabu search was used to further the solution obtained through the proposed heuristic algorithm,in order to minimize the hardware cost with the constraints of the software cost and the communication cost.Experimental results show that the algorithms proposed in the paper can produce better solution than the latest work,and the improvement is up to 28%.
出处
《计算机科学》
CSCD
北大核心
2012年第1期290-294,共5页
Computer Science
基金
国家自然科学基金(60970016)资助
关键词
软硬件划分
启发式算法
0-1背包问题
禁忌搜索
Hardware/Software partitioning
Heuristic algorithm
0-1 knapsack problem
Tabu search
