Font Size: a A A

Register Allocation Problem For Embedded Systems:Heuristic And Evolutionary Algorithm

Posted on:2013-11-10Degree:MasterType:Thesis
Country:ChinaCandidate:Z Y ChangFull Text:PDF
GTID:2248330395957305Subject:Circuits and Systems
Abstract/Summary:PDF Full Text Request
The embedded system has pervaded into every fields such as the scientific research and the engineering design since the rapid development of the information and network technology of the post-pc era. Since the application is much more focused on, code of high-quality are required to be compiled in the embedded system. In the process of the embedded system compiling optimization, the most important part should be the optimizing of the embedded system register allocation, letting maximum number of the intermediate variable be stored in the registers and helping us to gain the high-quality code. Based on the ample studies on the embedded system register allocation algorithm, this thesis has improved the evolutionary algorithm of it and proposed the embedded system register allocation algorithm on the basis of the maximum clique and the segmentation graph.(1)Proposed the embedded system registers allocation algorithm based on the maximum clique.The "complement" is introduced into this algorithm, and a heuristic approach is developed after the complementing of the interference figure of the intermediate variable and an intelligent use of maximum clique searching. Compared with the classical heuristic approach, better register allocation plan is proved to be got by the embedded system register allocation algorithm based on the maximum clique in the experimental section.(2) Proposed the embedded system registers allocation algorithm based on the segmentation graph. The concept of the segmentation graph is introduced on the basis of the previous innovation points. The process of the searching of the maximum clique has been detailed and the spill cost of each node has been fully utilized. And also, local search phase is also introduced to give a majorization of the preliminary result of the register allocation. In the experimental section, compared with the classical heuristic approach and the two kinds of evolutionary algorithm, the embedded system register allocation algorithm based on the segmentation graph is proved to get very good register allocation plan in very short time and the performance is approximate to the evolutionary algorithm.(3) Proposed the embedded system registers allocation algorithm based on the memetic algorithm. The embedded system registers allocation algorithm based on the memetic algorithm is obtained through the improving of the crossover operator of the primary hybrid evolutionary algorithm and the evaluation function. The effect and the influence of the intermediate variable spill cost is fully considered in the crossover operator and a new fitness function is introduced to judge the relative merits and enhance the evolution direction of the individual. Compared with the primary evolutionary algorithm, an obvious improvement of the evolutionary algorithm has been proved in the experimental section.
Keywords/Search Tags:embedded system, register allocation, heuristic algorithm, thecomplement, the segmentation graph, the maximum clique
PDF Full Text Request
Related items