多选择软硬件划分问题的启发式算法比较

HEURISTIC ALGORITHMS COMPARISONS FOR MULTIPLE-CHOICE HARDWARE/SOFTWARE PARTITIONING

软硬件协同设计作为嵌入式系统开发的重要技术,随着嵌入式系统的广泛应用变得越来越重要。软硬件划分是软硬件协同设计的关键环节,是经典的组合优化问题,已被证明是NP完全问题。对于一个给定的任务而言,由于在硬件实现中存在并行执行的潜力,具有不同面积的硬件可以提供不同的执行速度。这样,一个任务根据可利用的硬件面积可以有多种硬件实现方式。现有的软硬件划分方法通常仅仅考虑单一的硬件实现方式,却忽略了多种选择的硬件实现方式。对于多选择的软硬件划分问题,分别使用模拟退火算法和遗传算法,提出了可行性的解决方案。并与禁忌搜索算法进行比较,寻找多选择软硬件划分问题的相对较好的启发式算法。实验结果表明,在求得的解的质量方面,禁忌搜索算法相比于其他两种算法而言是最好的;在获得较好解的速度方面,模拟退火算法和遗传算法要比禁忌搜索算法快得多。

As the important technique of embedded system development, hardware/software （HW/SW） co-design is becoming increasingly important along with the widespread applications of embedded systems. Hardware/software partitioning is the crucial step in HW/ SW co-design, and is a classic combinatorial optimisation problem as well, has been proven to be the NP-complete. For a given task, hardware with different areas may provide different execution speeds due to the potential of parallel execution in its implementation. Thus, one task may have multiple-choice in hardware implementation according to the available hardware areas. Existing HW/SW partitioning approaches usually only consider a single hardware implementation manner, but overlook the implementation means with multiple-choice. For the HW/SW partitioning problem with multiple-choice, in this paper we present the solutions with feasibility by using simulated annealing algorithm and genetic algorithm respectively. Moreover, they are compared with tabu search algorithm to find the heuristic algorithm method relatively better for multiple-choice HW/SW partitioning problem. Experimental results show that tabu search is the best algorithm in comparison with other two in terms of the quality of the solution, but the simulated annealing algorithm and genetic algorithm are much faster than tabu search algorithm in the speed of obtaining a better solution.