基于嵌入式系統內存規劃方法的研究

　　2 規劃算法

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

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

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

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

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

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

　　2.1 算法的前提條件

　　在解決問(wèn)題之前，要給出解決問(wèn)題的前提。

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

　　(2)減少內存訪(fǎng)問(wèn)中塊和頁(yè)的轉換次數，可以減少延遲和節省能量。

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

　　(4)內存單元陣列是矩形，p和q代表內存塊單元的行數和列數，w代表內存字的長(cháng)度，則p*q*w代表了內存的大小。

　　(5)數據訪(fǎng)問(wèn)順序是已知的。

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

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

2.2 遺傳算法

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

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

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

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

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

　　2.3 實(shí)驗結果

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

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