【正文】 algorithm for graph coloring register allocation 3 problem for embedded systems based on a new crossover operator and a new local search function. Graph coloring abstracts the problem of assigning registers to live ranges in a program into the problem of assigning colors to nodes in an interference graph. The register allocator attempts to “color” the graph with a finite number of machine registers, with one constraint that any two nodes connected by an interference edge must be colored with different registers. To model register allocation as a graph coloring problem, the piler first constructs an interference graph G. The nodes in G correspond to live ranges, and the edges represent interferences. Thus, there is an edge in G from node i to node j if live range of i interferes with live range of j, that is, if they are simultaneously live at some point and cannot occupy the same register. To find an allocation from G, the piler looks for a kcoloring of G, that is, an assignment of k colors to the nodes of G such that adjacent nodes always have distinct colors. If we choose k to match the number of machine registers, then we can map a kcoloring of G into a feasible register assignment for the underlying code. Because graph coloring is NPplete, the piler uses a heuristic method to search for a coloring。 it is not guaranteed to find a kcoloring for all kcolorable graphs. If a kcoloring is not discovered, some values are spilled。 other parts of the framework are not changed. We have used x86architecture with its limited register file and register usage constraint. Our machine is a Ghz Pentium 4 with 1 GB of RAM. We applied the algorithms to 6 embedded and real time applications. For each application, the population size is set to 20 and LS iterations are all set from 500 to 2021. For each application, we run the allocator five times and average the results. Performance evaluation was done with respect to the following parameters : number of memory accesses required , spill loads, spill costs, the pile time needed by the allocator, the execution time of the generated code, including the number of load/store generated , size of allocator itself. Figure 1. Number of memory accesses TABLE I SPILL COST OF INSTRUCTION 10 TABLE II RATIO OF THE SPILL LOADS PRODUCED Comparison of number of memory accesses is the parison of total static number of load and store instructions inserted by each register allocator. Figure 1. pares the number of load/store instructions in the assembly code. The HEA inserts fewer memory access instruction than ORA, % fewer memory access instruction than IRC and % fewer memory access instruction than GPX. Table I give the spill costs of all the algorithms. For lowest population size the spill cost is less. For each benchmark given, the spill cost of each variable is set to the number of occurrences of the variables. The spill costs of the variables are the average values. The IRC algorithm gives the highest total spill cost. The HEA algorithm produce less spill cost than the maximum in four tests and it outperforms the IRC and GPX algorithms in all tests. Geic operator systematically eliminates lowquality solutions from the population, preserve diversity between solutions, and provide better input for local search. A small amount of spill cost is due to function callers and callees saving many contents of registers in order to preserve correct program semantics. Spill loads refers to additional number of loads incurred by the allocation algorithm. Spill loads give an indication of how well the allocator is able to perform the task. The number of spill loads is highly correlated with application running time. We calculate the dynamic number of spill loads added to each module of the program by multiplying the number of spill loads added to each block by the number of times that block is executed. Then we sum the number of dynamic spill loads added to each block. We obtain the dynamic number of spill loads for the entire program by summing the number of dynamic spill loads added to each module. Table II shows the spill loads for each allocator as a ratio to spill loads generated by IRC allocator (considered as base allocator for parison). The numbers are given as geometric mean. We see improvements of HEA over other allocator. Table III gives results in terms of pile time and run time. We observe that in most of the cases, the performance of different allocators were almost similar in terms of pile 11 times。相比內存，訪問寄存器的速度要快得多，但它們是稀缺資源，可以非常有效地利用。它的目標是找到一種方法來映射到物理內存中的位置（不論是主存儲器或機器寄存器）在程序中使用的臨時變量。通常情況下，這降低了運行時的性能，并增加了功耗。嵌入式處理器的編譯器必須應對這些建筑的優(yōu)化，并能夠 14 利用它們。 模型寄存器分配圖著色問題，編譯器首先構造一個干擾圖 G G 中對應的節(jié)點的生活范圍，和邊緣的干擾。由于圖著色是 NP完全的，編譯器采用了啟發(fā)式搜索著色的方法，它不能保證找到所有的 k染色圖的 k著色 。在嵌入式處理器的上下文中，圖著色的方法的最重要的限制是，它是基于這樣的假設的均勻的寄存器集。雖然文獻 [13]提出了一種采用整數(shù)規(guī)劃支持不規(guī)則的寄存器組，這種方法需要注冊不等式約束建模，使其難以在工業(yè)編譯器實現(xiàn)。喬治和蘋果 [11]提出迭代凝聚他們積極凝聚完全消除。 [17]提出了一種泛化的程度 K測試，稱為 P, Q，檢驗，處理不規(guī)則的寄存器設置和注冊類。 一些研究人員嘗試使用非圖形著色方法。馬哈詹 [16]提出一種新的混合進化算法（ HGR）嵌入式系統(tǒng)作為一個高度專業(yè)化的，特定領域的交叉和本地搜索功能的最有效的算法對圖的著色寄存器分配問題。遺傳算法是一種經典方法，在這個類別。進化算法相結合，與專業(yè)運營商來產生復雜的混合動力系統(tǒng)稱為混合遺傳算法，混合進化算法，遺傳局部搜索算法和模因算法。 我們提出了一個混合進化算法對圖的著色寄存器分配問題，也是一個新的本地搜索功能的基礎上一個新的交叉算子。一般的算法，如下所示： Input : Interference graph , IG = ( V,E ) 。 LS運營商適用，提高 p 為固定數(shù)目 L 的迭代（ local_search）。對于兩種配置 p1 和p2， p1 和 p2 之間的距離是要變換 p1 的 p2 的初等變換的最小數(shù)目。 R2K}，部分配置將集合 {R1， R2， ...。在寄存器分 配的問題，無論是泄漏的成本和被認為是在一個給定的干擾圖的節(jié)點的程度。節(jié)點進行排序在溢油度遞減順序。鑒于兩個父配置P1 ={R11， R12， .... R1K}和 p2= {R21， R22， ...。重復這一過程，直到所有的節(jié)點（即，其相應的變量）被映射到了寄存器類別之一。一個節(jié)點的泄漏程度，我可以由下面給出的三個方程之一定義 SDegree1(i) = SCost(i) x Degree(i) SDegree2(i) = SCost(i) x Degree2(i) SDegree3(i) = SCost(i) (1) 這些表達式， SCost 的（ i）為漏油成本和學位（ I）是節(jié)點 i的邊數(shù)事件。 （節(jié)點 i 和 j干擾圖中被說成是無沖突的時候，有沒有連接它們的邊緣） 17 B. 初始人口代 一般來說使用的 D