嵌入式系統(tǒng)寄存器分配-啟發(fā)式與進化算法.pdf

1、在信息和網(wǎng)絡(luò)技術(shù)高速發(fā)展的后PC時代，嵌入式系統(tǒng)已經(jīng)滲透到科學研究、工程設(shè)計等各個領(lǐng)域中。由于嵌入式系統(tǒng)更看重于應用，所以要求在嵌入式系統(tǒng)中經(jīng)過編譯后能得到高質(zhì)量的代碼。在嵌入式系統(tǒng)編譯優(yōu)化的過程中，最重要的部分是對嵌入式系統(tǒng)寄存器分配的優(yōu)化，讓盡可能多的中間變量保存在寄存器中有助于我們獲得高質(zhì)量的代碼。本文在對嵌入式系統(tǒng)寄存器分配算法進行充分的研究的基礎(chǔ)上，提出了基于最大團的嵌入式系統(tǒng)寄存器分配算法、基于分割圖的嵌入式系統(tǒng)寄存器分配算

2、法和基于Memetic算法的嵌入式系統(tǒng)寄存器分配方法。
　　 (1)提出了基于最大團的嵌入式系統(tǒng)寄存器分配算法。該算法引入補圖思想，將中間變量相互干擾圖取補圖后，巧妙的使用尋找最大團操作，得到了一種很好的啟發(fā)式算法，實驗部分通過與經(jīng)典的啟發(fā)式算法進行對比，證實了基于最大團的嵌入式系統(tǒng)寄存器分配算法確實能得到更好的寄存器分配方案。
　　 (2)提出了基于分割圖的嵌入式系統(tǒng)寄存器分配算法。在前一個創(chuàng)新點的基礎(chǔ)上，引入分割圖概

3、念，細化尋找最大團的過程，充分的利用節(jié)點的溢出代價，并且引入局部搜索算子對寄存器分配的初步結(jié)果進行優(yōu)化。實驗部分通過與經(jīng)典啟發(fā)式算法以及兩種進化算法對比，證實了基于分割圖的嵌入式系統(tǒng)寄存器分配算法能夠在較短的時間內(nèi)得到非常好的寄存器分配方案，性能接近進化算法。
　　 (3)基于Memetic算法的嵌入式系統(tǒng)寄存器分配。通過對原有混合進化算法的交叉算子和評價函數(shù)的改進，得到了基于Memetic算法的嵌入式系統(tǒng)寄存器分配方法。在交叉