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

ABSTRACT

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

Keywords:

Hardware/software partitioning, Computerized algorithm, Accurate algorithm, Heuristic algorithm, Dynamic programming, Genetic algorithm.