??? 摘? 要： 內存訪問延遲是嵌入式系統性能提高的瓶頸。本文以數據在內存的存儲方式為出發點來解決內存訪問延遲的問題，并用遺傳算法實現了優化算法。
??? 關鍵詞： 內存規劃? 嵌入式系統? DRAM訪問模式? 存儲分配? 遺傳算法
?
??? 針對有內存管理單元（MMU）的處理器設計的一些桌面操作系統(如Windows、Linux)都使用了虛擬存儲器的概念，虛擬內存地址被送到MMU。在這里，虛擬地址被映射為物理地址，實際存儲器被分割為相同大小的頁面，采用分頁的方式載入進程。一個程序在運行之前，沒有必要全部裝入內存，而是僅將那些當前要運行的部分頁面裝入內存運行。大多數嵌入式系統是針對沒有MMU的處理器設計的，因此不能使用處理器的虛擬內存管理技術，而采用實存儲管理策略，從而對內存的訪問是直接的。它對地址的訪問不需要經過MMU，而是直接送到地址線上輸出，所有程序中訪問的地址都是實際的物理地址。而且，大多數嵌入式操作系統對內存沒有保護，各個進程實際上共享一個運行空間。一個進程在執行前，系統必須為它分配足夠的連續地址空間，然后全部載入主存儲的連續空間。從編譯內核開始，開發人員必須告訴系統，這塊開發板到底擁有多少內存；在開發程序時，必須考慮內存的分配情況并關注應用程序需要運行空間的大小。另外，由于采用實存儲器管理策略，用戶程序同內核以及其他用戶程序在一個地址空間，程序開發時要保證不侵犯其他應用程序的地址空間，不破壞系統的正常工作，使程序正常運行。因而對內存操作要格外小心。由此可見，開發者不得不參與系統的內存管理，否則系統的效率和性能都不能令人滿意。開發者可以用一個內存管理器來幫助管理內存，可以借鑒流行操作系統對內存池（pool）中塊（block）進行管理的思想。訪問時先尋找對應的塊，然后對物理地址進行頁的解碼，進而是行解碼，最后是列解碼和根據圖像處理系統處理大量數據的特點，對數據在內存中的布局進行規劃。即同一塊中使連續訪問的數據在同一頁；在同一頁的數據，盡量安排在同一行，減小內存訪問延遲，以便對性能進行改善。同時，內存塊間相對位置也用同樣的方法進行規劃，使得塊間的轉換也盡快完成。本文采用遺傳算法，同時對內存數據存儲進行頁、行、列的規劃，對塊間相對位置也進行了規劃。
1? 內存規劃
??? 流行的操作系統對內存訪問的基本方式是支持快速緩存，執行的過程是把要訪問的地址整行拷貝到緩存區，先進行頁解碼和行解碼，然后進行列解碼并根據讀寫信號進行選擇。目前嵌入式系統中使用的DRAMs都支持高效內存訪問模式，還特別支持流行的頁(page)訪問模式和區間(burst)訪問模式（相當于以列為主的訪問）。這種訪問模式消耗的能量低于隨機訪問方式，例如，IBM′s Cu-11 Embedded DRAM macro支持的隨機訪問時間是10ns，而塊中頁訪問的時間是5ns，電流分別是60mA/MB和13mA/MB。所以，充分利用內存訪問模式的特點可以改變嵌入式系統的性能。
??? 為了說明本文的規劃思想，假設內存中有如圖1所示的變量a，b，c，d，e，f，g，h。若要訪問內存中變量的次序為acacebdbefgfdah，則根據圖1中內存存放的次序，可以計算出訪問延遲的時間。如果頁間訪問延遲時間是5個時鐘周期，記為Delay(P)=5cycles，則在同頁中行間訪問延遲Delay(R)=3cycles，同行中列間訪問延遲Delay(C)=1cycles。根據圖1(a)和圖1(b)中兩種存儲模式，可以分別計算出如圖2所示的兩種內存存儲方式下內存訪問延遲時間：Latency(a)=47cycles，Latency（b）=29cycles。
?
?
??? 同樣，將相互訪問頻率較高的內存塊，如三個數組A、B、C分別存放在不同的內存塊，數組A和數組C是經常要進行元素間計算的，則把分別存儲A和C的塊放在相鄰的位置上，這樣，既可以減小地址總線的負擔，也可以提高訪問時間和減少訪問次數。
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）所示。
?
??? 文獻[1]中的算法是對頁進行規劃時，尋找頁訪問次數最大，對列進行規劃時，尋找列訪問次數最大。在具體應用中，只能用一種方法。而本文同時對內存中頁和行進行規劃，所以對系統性能的提高更有效。圖3（b）是與文獻[1]算法的結果比較（僅給出能量消耗圖）,前者平均能量提高了大約10％。
?
??? 把本文的算法應用于自行開發的嵌入式圖像處理系統中，獲得了良好的系統性能。
3? 結論和展望
??? 本文提出了一個通過減少對內存訪問時塊間和塊內頁間交換的次數和行間轉換的次數，使嵌入式系統內存和能量資源能夠有效利用的方法。該方法可以直接應用到嵌入式系統的內存管理器中。因為隨著用戶需求和功能的增加，越來越多的嵌入式系統需要處理大量的數據，所以對嵌入式系統的內存采取管理是必要的。尤其對一些不帶MMU單元的操作系統來說，應用中加入內存管理程序對系統性能的提高起到很大的作用。本文給出的內存規劃策略能有效地減輕嵌入式系統負擔。本文是針對非數組的變量來討論的，但是也可以應用到數組變量中。盡管使用的算法有可能沒有找到系統的最優解，但使用這個算法，一定可以提高系統的性能。
??? 本文提出的算法不但可以應用到嵌入式系統中的DRAMs，也可以應用到其他支持行和列內存訪問的存儲設備上，如flash存儲器。雖然目前一些多組SRAM的系統還不支持此算法，但是在將來的基于功耗設計的系統中，這種訪問模式是會被支持的。
??? 本文方法同流行操作系統內存管理相比更簡單，更加適合嵌入式系統，同時彌補了現用嵌入式操作系統?滋CLinux等在內存管理方面的不足。
參考文獻
1?? Choi Y，Kim T，Han H.Memory Layout Techniques for Variables Utilizing Efficient DRAM Access Modes in Embedded System Design.IEEE Transactions on Computer Aided?Design of Integrated Circuits and Systems，2005；24(2)
2?? Hettiaratchi S，Cheung P，Clarke T.Energy efficient?address assignment through minimized memory row?switching.In：Proc.Int.Conf：Computer-Aided Design，2002
3?? Atienza D，Mamagkakis S，Catthoor F et al.Reducing memory accesses with a system-level design methodology in?customized dynamic memory management.Embedded Systems for Real-Time Multimedia，2004
4?? Panda P R，Dutt N.Low power memory memory mapping?through reducing address bus activity.Technical Report?95-32 University of California，Irvine，1995，11
5?? Zivojnovic V，Velarde J，Schiager C.Desstone：A DSP-oriented benchmarking methodology.In：Proc.Int.Conf：Signal?Process，Applicat Technol，1994