Research Of Hardware And Software Partitioning Methodology Based On Genetic Algorithm And Simulated Annealing

Integrated circuit enters into the era of system on chip(SoC) as the rapid development of embedded system. With the design complexity's increasing, traditional design methodology is unable to satisfy the needs of embedded system due to its difficulty of location fault and updating products, long development cycle and high cost. So the hardware and software co-design methodology becomes a necessity. During the co-design the hardware and software partitioning is one of the important techniques. Researching on the hardware and software partitioning design, structuring a reasonable system description model, putting forward an efficient partitioning algorithm possess very important value in theory and in application.The algorithm of hardware and software partitioning is an very important technology during the whole process of the co-design.How to consider the system's performance and its cost simultaneously and obtain the optimal combination of the hardware and software, is the mainly purpose of the hardware and software partitioning.But as an NP-hard problem the hardware and software partitioning now can only be approximately settled through some kinds of optimal solution.The main research of this thesis is to find the optimal solution of hardware and software partitioning during embedded system design.This thesis introduces the research field of hardware and software co-design and its domestic and abroad developing situation, further studies in constructing mathematical model in the process of dealing with the hardware and software partitioning problem and also analyzes the problems we usually encounter existed in the partitioning technology. Based on the comparison of the advantages and disadvantages of genetic algorithm (GA) and simulated annealing (SA), aimed at the hardware and software partitioning problem in embedded system, a hybrid algorithm is proposed based on genetic algorithm and simulated annealing, namely GASA, where the main frame of the global search is provided by GA and the function of generating random state and the Metropolis criteria in SA are used for updating the populations produced by GA. Directed acyclic graph generated by TGFF tool is adopted in hardware and software bi-partitioning as the mathematical model.At the end of this paper, GA, SA and GASA are respectively programmed and verified using the real data generated by TGFF tool. The verification results indicate that GASA is able to overcome the poor local search ability of GA and the insufficient understanding of SA to the global search space, which gives a better and more accurate partitioning result.