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

　　2 規劃算法

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

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

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

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

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

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

　　2.1 算法的前提條件

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

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

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

　　(3)在頁/行/列之間轉換沒有優先級，也就是從1～3頁和從1～2頁耗時是相同的。

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

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

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

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

2.2 遺傳算法

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

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

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

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

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

　　2.3 實驗結果

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

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