An Effective Heuristic-Based Approach for Partitioning

[摘要] As being one of the most crucial steps in the design ofembedded systems, hardware/software partitioning has receivedmore concern than ever. The performance of a system designwill strongly depend on the efficiency of the partitioning. Inthis paper, we construct a communication graph for embeddedsystem and describe the delay-related constraints and thecost-related objective based on the graph structure. Then, wepropose a heuristic based on genetic algorithm and simulatedannealing to solve the problem near optimally. We note that thegenetic algorithm has a strong global search capability, whilethe simulated annealing algorithm will fail in a local optimalsolution easily. Hence, we can incorporate simulated annealingalgorithm in genetic algorithm. The combined algorithm willprovide more accurate near-optimal solution with faster speed. Experiment results show that the proposed algorithm producemore accurate partitions than the original genetic algorithm.

[学科分类] 应用数学