The Application of Computerized Algorithms in the Design Method of Software-hardware Dual-track Partitioning in an Embedded System Abstract

摘要

It has been proved that the hardware/software partitioning problem is NP-hard. Currently we have tried a varietyof computerized algorithms to resolve it, which can be divided into two major categories: accurate algorithms and heuristicalgorithms. This paper will discuss accurate algorithms and heuristic algorithms respectively. Accurate algorithmstake the example of a greedy algorithm. It abstracts the hardware/software partitioning problem into 01 knapsack modeland obtains the exact optimal solution by the greedy algorithm, while heuristic algorithms use a genetic algorithm as anexample. It converts the hardware/software partitioning problem into a multi-constraint 0-1 knapsack problem and solvesit by employing the genetic algorithm therein. By steps like "variation” and "crossover", this algorithm makes an offspringsolution quickly approach an optimal solution, thereby constructing a near-optimal heuristic solution of the HW/SW partitioningproblem. Experimental results demonstrate that the algorithm proposed in this paper can effectively resolve thehardware/software partitioning problem, have a good global searching capability, and the heuristic algorithm performsfaster than the traditional accurate algorithm, but the heuristic algorithm only acquires a near-optimal solution, which isnot perfect.