高效软硬件划分算法及其提升技术

作者：王璞; 武继刚

来源：计算机科学, 2012, (01): 290-294.

• 软硬件划分
• 启发式算法
• 0-1背包问题
• 禁忌搜索 Hardware/Software partitioning
• Heuristic algorithm
• 0-1 knapsack problem
• Tabu search

软硬件划分是软硬件协同设计的关键环节,它决定系统中哪些组件由软件实现,哪些由硬件实现。软硬件划分问题已被证明是NP完全问题。将一类软硬件划分问题看作变异的0-1背包问题,在求解背包问题的算法基础上构造出软硬件划分问题的优质启发解。此外,采用禁忌搜索(Tabu Search)算法对求得的启发解进行改进,在软件开销和通信开销满足一定约束的条件下,使得硬件开销尽可能小。实验结果证明,所提算法对当前最新算法的改进最大可达到28%。

• 单位
  天津工业大学; 计算机科学国家重点实验室; 中国科学院软件研究所