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

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

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

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