基于嵌入式系統(tǒng)內(nèi)存規(guī)劃方法的研究

　　2 規(guī)劃算法

　　使系統(tǒng)內(nèi)存訪問延遲最小的內(nèi)存規(guī)劃應(yīng)該從變量和要申請(qǐng)的內(nèi)存塊在內(nèi)存中存儲(chǔ)的相對(duì)位置的角度來尋找。其前提條件是變量和內(nèi)存塊的訪問順序已知，申請(qǐng)的塊的信息也可以得到。根據(jù)嵌入式系統(tǒng)應(yīng)用的特點(diǎn)，例如圖像處理系統(tǒng)，經(jīng)過對(duì)程序的預(yù)處理，這個(gè)條件可以滿足。處理過程可分為二步：第一步進(jìn)行塊間的規(guī)劃；第二步對(duì)塊內(nèi)變量進(jìn)行規(guī)劃。問題的描述如下。

　　在嵌入式系統(tǒng)中，設(shè)內(nèi)存塊大小為S，某段時(shí)間內(nèi)內(nèi)存塊個(gè)數(shù)為T，塊中每頁(yè)的大小為p*q*w，其中p為行數(shù)，q為列數(shù)，w為每個(gè)字的位數(shù)。在某個(gè)應(yīng)用中有N個(gè)變量{ni，i=1，……，N}，已知變量被訪問的次序?yàn)閚jnknl……nm，則首先尋找塊存儲(chǔ)的相對(duì)位置，使得內(nèi)存訪問延遲函數(shù) Latency1最小(假設(shè)兩個(gè)塊相鄰，訪問需要1個(gè)時(shí)鐘周期；相隔1個(gè)塊，訪問需要2個(gè)時(shí)鐘周期；第i個(gè)塊和第j個(gè)塊間訪問需要i－j個(gè)時(shí)鐘訪問延遲)：

　　Latency1={Sum|∑z*（i－j）/z，z=1....m} (1)

　　其中：z是訪問順序表中內(nèi)存塊的位置，如第3個(gè)位置（z＝3）訪問的是bi，下一個(gè)位置存放的是bj，i和j是內(nèi)存塊訪問順序中相鄰塊標(biāo)號(hào)，是塊在內(nèi)存中存儲(chǔ)的相對(duì)位置，m是訪問內(nèi)存塊的順序排列長(zhǎng)度。其次尋找N個(gè)變量在內(nèi)存塊內(nèi)的存儲(chǔ)相對(duì)位置的一種規(guī)劃{nxnynz……nt}，使得內(nèi)存訪問延遲函數(shù)Latency2最小，塊內(nèi)規(guī)劃目標(biāo)函數(shù)為：

　　Min：Latency2=5*#P+3*#R+#C (2)

　　其中：＃P是規(guī)劃中訪問的頁(yè)間轉(zhuǎn)換的次數(shù)，＃R是行間轉(zhuǎn)換的次數(shù)，＃C是列間轉(zhuǎn)換的次數(shù)。N個(gè)變量的排列方法的數(shù)目共有N!種，要在如此多的情況下尋找某種最優(yōu)的排列，這是NP問題。解決這類優(yōu)化問題有很多方法，如模擬退火算法、演化算法等一些啟發(fā)算法，也可以用曲線圖劃分問題（graph partitioning problem）的方法來解決此問題。本文采用了最近幾年發(fā)展很快的遺傳算法來解決此規(guī)劃問題。遺傳算法是解決NP問題的有效方法。本文的研究目的在于內(nèi)存規(guī)劃的意義，而不是遺傳算法，所以采用經(jīng)典遺傳算法[8]，以此來驗(yàn)證內(nèi)存規(guī)劃的有效性。本文的算法可記為L(zhǎng)BP（LBP-Layout of Block and Page）。

　　2.1 算法的前提條件

　　在解決問題之前，要給出解決問題的前提。

　　(1)對(duì)塊內(nèi)訪問時(shí)，通常是先尋找頁(yè)，再找到行，最后找列，則對(duì)頁(yè)訪問的耗時(shí)（一般稱為內(nèi)存訪問延遲）大于對(duì)同頁(yè)中的行，行訪問耗時(shí)大于同行中的列。同時(shí)在相距較遠(yuǎn)的塊間訪問耗時(shí)大于相鄰塊間訪問。

　　(2)減少內(nèi)存訪問中塊和頁(yè)的轉(zhuǎn)換次數(shù)，可以減少延遲和節(jié)省能量。

　　(3)在頁(yè)/行/列之間轉(zhuǎn)換沒有優(yōu)先級(jí)，也就是從1～3頁(yè)和從1～2頁(yè)耗時(shí)是相同的。

　　(4)內(nèi)存單元陣列是矩形，p和q代表內(nèi)存塊單元的行數(shù)和列數(shù)，w代表內(nèi)存字的長(zhǎng)度，則p*q*w代表了內(nèi)存的大小。

　　(5)數(shù)據(jù)訪問順序是已知的。

　　(6)每個(gè)數(shù)據(jù)都分配給獨(dú)立的內(nèi)存單元，基本單元的大小與要分配的數(shù)據(jù)剛好匹配。

　　前面四個(gè)假設(shè)是解決問題的必要條件，而后面兩條假設(shè)是為了簡(jiǎn)化解決的問題。如果沒有特別的說明，這些假設(shè)在本文都是適用的。

2.2 遺傳算法

　　遺傳算法的基本步驟是確定適應(yīng)度函數(shù)，然后對(duì)問題進(jìn)行編碼和尋找最優(yōu)解。下面給出解決塊內(nèi)規(guī)劃問題算法第二步的基本步驟。第一步與第二步相似，本文省略。

　　(1)適應(yīng)度函數(shù)是目標(biāo)函數(shù)，即Latency。依據(jù)假設(shè)，如果頁(yè)訪問模式延遲時(shí)間是5個(gè)時(shí)鐘周期，記為Delay(P)=5cycles，則行延遲Delay(R)=3cycles，列延遲Delay(C)=1cycles，適應(yīng)度函數(shù)為：latency(cycles)=#P*5+#R*3 +#C*1。

　　(2)解決的問題是內(nèi)存變量的存放次序，由于字母的數(shù)目有限，所以可用十進(jìn)制編碼來表示變量(如把圖1中abcdefgh編碼為12345678）。

　　(3)雜交過程選擇同一代中的某些位進(jìn)行交換，不同代的交換容易產(chǎn)生非法個(gè)體， 所以在某代個(gè)體內(nèi)部進(jìn)行交換，可以提高算法的有效性。選取某代雜交的概率為Pc＝0.08。

　　(4)算法的終止是在某兩代適應(yīng)度函數(shù)之間相對(duì)誤差小于0.001時(shí)，程序終止，并給出最優(yōu)的內(nèi)存規(guī)劃方法。如果內(nèi)存單元數(shù)目有p*q個(gè)，則取串中每q個(gè)為一行（分為一組），間隔n*(q-1)為一列，存放在內(nèi)存中供程序使用。

　　2.3 實(shí)驗(yàn)結(jié)果

　　圖像處理系統(tǒng)的處理對(duì)象是象素，處理過程中使用大量的內(nèi)存，造成了嵌入式系統(tǒng)圖像處理應(yīng)用中的瓶頸。經(jīng)過近幾十年的發(fā)展，圖像處理算法也有很多成熟的算法?？梢园堰@些算法經(jīng)過改造，使之適應(yīng)嵌入式系統(tǒng)體積小、容量小的特點(diǎn)。本文算法的提出是針對(duì)使用大量?jī)?nèi)存，同時(shí)處理步驟相對(duì)簡(jiǎn)單的系統(tǒng)設(shè)計(jì)的。本文采用一些標(biāo)準(zhǔn)(benchmark)系統(tǒng)，提高嵌入式系統(tǒng)有限的內(nèi)存資源的利用率。基于內(nèi)存的規(guī)劃算法，用幾個(gè)內(nèi)存訪問序列驗(yàn)證內(nèi)存規(guī)劃對(duì)嵌入式系統(tǒng)性能的改變。實(shí)驗(yàn)中使用IFA(Image Flip Algorithm)、GSR(Gauss-Seidel formula)、CA(Compress Algorithm)、BIQUAD(Biquad_one_section)和FIR。后兩個(gè)例子是為了驗(yàn)證非圖像處理的系統(tǒng)使用本算法的情況，說明算法的應(yīng)用具有一定的普遍意義。

　　表1和表2是用隨機(jī)訪問方法和本文的訪問方法進(jìn)行實(shí)驗(yàn)的結(jié)果。從表中可以看出，規(guī)劃后的延遲時(shí)間都縮短了，另外還驗(yàn)證了規(guī)劃內(nèi)存方法的使用減少了嵌入式系統(tǒng)能耗。能耗的計(jì)算采用文獻(xiàn)[2]中的算法，如圖3（a）所示。