Journal of Applied Mathematics
Volume 2013 (2013), Article ID 138037, 8 pages
http://dx.doi.org/10.1155/2013/138037
Research Article

An Effective Heuristic-Based Approach for Partitioning

Xibin Zhao,1 Hehua Zhang,1 Yu Jiang,1,2 Songzheng Song,3 Xun Jiao,4 and Ming Gu1

1School of Software, Tsinghua University, TNLIST, KLISS, Beijing 100084, China
2School of Computer Science and Technology, Tsinghua University, Beijing 100084, China
3School for Integrative Sciences and Engineering, National Univerisity of Singapore, Kent, Singapore 119077
4International school, Beijing university of post and telecommunication, Beijing 100876, China

Received 7 March 2013; Accepted 22 March 2013

Academic Editor: Xiaoyu Song

Copyright © 2013 Xibin Zhao et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Abstract

As being one of the most crucial steps in the design of embedded systems, hardware/software partitioning has received more concern than ever. The performance of a system design will strongly depend on the efficiency of the partitioning. In this paper, we construct a communication graph for embedded system and describe the delay-related constraints and the cost-related objective based on the graph structure. Then, we propose a heuristic based on genetic algorithm and simulated annealing to solve the problem near optimally. We note that the genetic algorithm has a strong global search capability, while the simulated annealing algorithm will fail in a local optimal solution easily. Hence, we can incorporate simulated annealing algorithm in genetic algorithm. The combined algorithm will provide more accurate near-optimal solution with faster speed. Experiment results show that the proposed algorithm produce more accurate partitions than the original genetic algorithm.