??? 摘? 要： 內(nèi)存訪問延遲是嵌入式系統(tǒng)性能提高的瓶頸。本文以數(shù)據(jù)在內(nèi)存的存儲方式為出發(fā)點(diǎn)來解決內(nèi)存訪問延遲的問題，并用遺傳算法實(shí)現(xiàn)了優(yōu)化算法。
??? 關(guān)鍵詞： 內(nèi)存規(guī)劃? 嵌入式系統(tǒng)? DRAM訪問模式? 存儲分配? 遺傳算法
?
??? 針對有內(nèi)存管理單元（MMU）的處理器設(shè)計的一些桌面操作系統(tǒng)(如Windows、Linux)都使用了虛擬存儲器的概念，虛擬內(nèi)存地址被送到MMU。在這里，虛擬地址被映射為物理地址，實(shí)際存儲器被分割為相同大小的頁面，采用分頁的方式載入進(jìn)程。一個程序在運(yùn)行之前，沒有必要全部裝入內(nèi)存，而是僅將那些當(dāng)前要運(yùn)行的部分頁面裝入內(nèi)存運(yùn)行。大多數(shù)嵌入式系統(tǒng)是針對沒有MMU的處理器設(shè)計的，因此不能使用處理器的虛擬內(nèi)存管理技術(shù)，而采用實(shí)存儲管理策略，從而對內(nèi)存的訪問是直接的。它對地址的訪問不需要經(jīng)過MMU，而是直接送到地址線上輸出，所有程序中訪問的地址都是實(shí)際的物理地址。而且，大多數(shù)嵌入式操作系統(tǒng)對內(nèi)存沒有保護(hù)，各個進(jìn)程實(shí)際上共享一個運(yùn)行空間。一個進(jìn)程在執(zhí)行前，系統(tǒng)必須為它分配足夠的連續(xù)地址空間，然后全部載入主存儲的連續(xù)空間。從編譯內(nèi)核開始，開發(fā)人員必須告訴系統(tǒng)，這塊開發(fā)板到底擁有多少內(nèi)存；在開發(fā)程序時，必須考慮內(nèi)存的分配情況并關(guān)注應(yīng)用程序需要運(yùn)行空間的大小。另外，由于采用實(shí)存儲器管理策略，用戶程序同內(nèi)核以及其他用戶程序在一個地址空間，程序開發(fā)時要保證不侵犯其他應(yīng)用程序的地址空間，不破壞系統(tǒng)的正常工作，使程序正常運(yùn)行。因而對內(nèi)存操作要格外小心。由此可見，開發(fā)者不得不參與系統(tǒng)的內(nèi)存管理，否則系統(tǒng)的效率和性能都不能令人滿意。開發(fā)者可以用一個內(nèi)存管理器來幫助管理內(nèi)存，可以借鑒流行操作系統(tǒng)對內(nèi)存池（pool）中塊（block）進(jìn)行管理的思想。訪問時先尋找對應(yīng)的塊，然后對物理地址進(jìn)行頁的解碼，進(jìn)而是行解碼，最后是列解碼和根據(jù)圖像處理系統(tǒng)處理大量數(shù)據(jù)的特點(diǎn)，對數(shù)據(jù)在內(nèi)存中的布局進(jìn)行規(guī)劃。即同一塊中使連續(xù)訪問的數(shù)據(jù)在同一頁；在同一頁的數(shù)據(jù)，盡量安排在同一行，減小內(nèi)存訪問延遲，以便對性能進(jìn)行改善。同時，內(nèi)存塊間相對位置也用同樣的方法進(jìn)行規(guī)劃，使得塊間的轉(zhuǎn)換也盡快完成。本文采用遺傳算法，同時對內(nèi)存數(shù)據(jù)存儲進(jìn)行頁、行、列的規(guī)劃，對塊間相對位置也進(jìn)行了規(guī)劃。
1? 內(nèi)存規(guī)劃
??? 流行的操作系統(tǒng)對內(nèi)存訪問的基本方式是支持快速緩存，執(zhí)行的過程是把要訪問的地址整行拷貝到緩存區(qū)，先進(jìn)行頁解碼和行解碼，然后進(jìn)行列解碼并根據(jù)讀寫信號進(jìn)行選擇。目前嵌入式系統(tǒng)中使用的DRAMs都支持高效內(nèi)存訪問模式，還特別支持流行的頁(page)訪問模式和區(qū)間(burst)訪問模式（相當(dāng)于以列為主的訪問）。這種訪問模式消耗的能量低于隨機(jī)訪問方式，例如，IBM′s Cu-11 Embedded DRAM macro支持的隨機(jī)訪問時間是10ns，而塊中頁訪問的時間是5ns，電流分別是60mA/MB和13mA/MB。所以，充分利用內(nèi)存訪問模式的特點(diǎn)可以改變嵌入式系統(tǒng)的性能。
??? 為了說明本文的規(guī)劃思想，假設(shè)內(nèi)存中有如圖1所示的變量a，b，c，d，e，f，g，h。若要訪問內(nèi)存中變量的次序?yàn)閍cacebdbefgfdah，則根據(jù)圖1中內(nèi)存存放的次序，可以計算出訪問延遲的時間。如果頁間訪問延遲時間是5個時鐘周期，記為Delay(P)=5cycles，則在同頁中行間訪問延遲Delay(R)=3cycles，同行中列間訪問延遲Delay(C)=1cycles。根據(jù)圖1(a)和圖1(b)中兩種存儲模式，可以分別計算出如圖2所示的兩種內(nèi)存存儲方式下內(nèi)存訪問延遲時間：Latency(a)=47cycles，Latency（b）=29cycles。
?
?
??? 同樣，將相互訪問頻率較高的內(nèi)存塊，如三個數(shù)組A、B、C分別存放在不同的內(nèi)存塊，數(shù)組A和數(shù)組C是經(jīng)常要進(jìn)行元素間計算的，則把分別存儲A和C的塊放在相鄰的位置上，這樣，既可以減小地址總線的負(fù)擔(dān)，也可以提高訪問時間和減少訪問次數(shù)。
2? 規(guī)劃算法
??? 使系統(tǒng)內(nèi)存訪問延遲最小的內(nèi)存規(guī)劃應(yīng)該從變量和要申請的內(nèi)存塊在內(nèi)存中存儲的相對位置的角度來尋找。其前提條件是變量和內(nèi)存塊的訪問順序已知，申請的塊的信息也可以得到。根據(jù)嵌入式系統(tǒng)應(yīng)用的特點(diǎn)，例如圖像處理系統(tǒng)，經(jīng)過對程序的預(yù)處理，這個條件可以滿足。處理過程可分為二步：第一步進(jìn)行塊間的規(guī)劃；第二步對塊內(nèi)變量進(jìn)行規(guī)劃。問題的描述如下。
??? 在嵌入式系統(tǒng)中，設(shè)內(nèi)存塊大小為S，某段時間內(nèi)內(nèi)存塊個數(shù)為T，塊中每頁的大小為p*q*w，其中p為行數(shù)，q為列數(shù)，w為每個字的位數(shù)。在某個應(yīng)用中有N個變量{ni，i=1，……，N}，已知變量被訪問的次序?yàn)閚jnknl……nm，則首先尋找塊存儲的相對位置，使得內(nèi)存訪問延遲函數(shù)Latency1最小(假設(shè)兩個塊相鄰，訪問需要1個時鐘周期；相隔1個塊，訪問需要2個時鐘周期；第i個塊和第j個塊間訪問需要i－j個時鐘訪問延遲)：
??? Latency1={Sum|∑z*（i－j）/z，z=1....m}?????????????? (1)
??? 其中：z是訪問順序表中內(nèi)存塊的位置，如第3個位置（z＝3）訪問的是bi，下一個位置存放的是bj，i和j是內(nèi)存塊訪問順序中相鄰塊標(biāo)號，是塊在內(nèi)存中存儲的相對位置，m是訪問內(nèi)存塊的順序排列長度。其次尋找N個變量在內(nèi)存塊內(nèi)的存儲相對位置的一種規(guī)劃{nxnynz……nt}，使得內(nèi)存訪問延遲函數(shù)Latency2最小，塊內(nèi)規(guī)劃目標(biāo)函數(shù)為：
??? Min：Latency2=5*#P+3*#R+#C?????????????????????????? ?(2)
??? 其中：＃P是規(guī)劃中訪問的頁間轉(zhuǎn)換的次數(shù)，＃R是行間轉(zhuǎn)換的次數(shù)，＃C是列間轉(zhuǎn)換的次數(shù)。N個變量的排列方法的數(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ī)劃的有效性。本文的算法可記為LBP（LBP-Layout of Block and Page）。
2.1 算法的前提條件
??? 在解決問題之前，要給出解決問題的前提。
??? (1)對塊內(nèi)訪問時，通常是先尋找頁，再找到行，最后找列，則對頁訪問的耗時（一般稱為內(nèi)存訪問延遲）大于對同頁中的行，行訪問耗時大于同行中的列。同時在相距較遠(yuǎn)的塊間訪問耗時大于相鄰塊間訪問。
??? (2)減少內(nèi)存訪問中塊和頁的轉(zhuǎn)換次數(shù)，可以減少延遲和節(jié)省能量。
??? (3)在頁/行/列之間轉(zhuǎn)換沒有優(yōu)先級，也就是從1～3頁和從1～2頁耗時是相同的。
??? (4)內(nèi)存單元陣列是矩形，p和q代表內(nèi)存塊單元的行數(shù)和列數(shù)，w代表內(nèi)存字的長度，則p*q*w代表了內(nèi)存的大小。
??? (5)數(shù)據(jù)訪問順序是已知的。
??? (6)每個數(shù)據(jù)都分配給獨(dú)立的內(nèi)存單元，基本單元的大小與要分配的數(shù)據(jù)剛好匹配。
??? 前面四個假設(shè)是解決問題的必要條件，而后面兩條假設(shè)是為了簡化解決的問題。如果沒有特別的說明，這些假設(shè)在本文都是適用的。
2.2 遺傳算法
??? 遺傳算法的基本步驟是確定適應(yīng)度函數(shù)，然后對問題進(jìn)行編碼和尋找最優(yōu)解。下面給出解決塊內(nèi)規(guī)劃問題算法第二步的基本步驟。第一步與第二步相似，本文省略。
??? (1)適應(yīng)度函數(shù)是目標(biāo)函數(shù)，即Latency。依據(jù)假設(shè)，如果頁訪問模式延遲時間是5個時鐘周期，記為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)生非法個體， 所以在某代個體內(nèi)部進(jìn)行交換，可以提高算法的有效性。選取某代雜交的概率為Pc＝0.08。
??? (4)算法的終止是在某兩代適應(yīng)度函數(shù)之間相對誤差小于0.001時，程序終止，并給出最優(yōu)的內(nèi)存規(guī)劃方法。如果內(nèi)存單元數(shù)目有p*q個，則取串中每q個為一行（分為一組），間隔n*(q-1)為一列，存放在內(nèi)存中供程序使用。
2.3 實(shí)驗(yàn)結(jié)果
??? 圖像處理系統(tǒng)的處理對象是象素，處理過程中使用大量的內(nèi)存，造成了嵌入式系統(tǒng)圖像處理應(yīng)用中的瓶頸。經(jīng)過近幾十年的發(fā)展，圖像處理算法也有很多成熟的算法。可以把這些算法經(jīng)過改造，使之適應(yīng)嵌入式系統(tǒng)體積小、容量小的特點(diǎn)。本文算法的提出是針對使用大量內(nèi)存，同時處理步驟相對簡單的系統(tǒng)設(shè)計的。本文采用一些標(biāo)準(zhǔn)(benchmark)系統(tǒng)，提高嵌入式系統(tǒng)有限的內(nèi)存資源的利用率?；趦?nèi)存的規(guī)劃算法，用幾個內(nèi)存訪問序列驗(yàn)證內(nèi)存規(guī)劃對嵌入式系統(tǒng)性能的改變。實(shí)驗(yàn)中使用IFA(Image Flip Algorithm)、GSR(Gauss-Seidel formula)、CA(Compress Algorithm)、BIQUAD(Biquad_one_section)和FIR。后兩個例子是為了驗(yàn)證非圖像處理的系統(tǒng)使用本算法的情況，說明算法的應(yīng)用具有一定的普遍意義。
??? 表1和表2是用隨機(jī)訪問方法和本文的訪問方法進(jìn)行實(shí)驗(yàn)的結(jié)果。從表中可以看出，規(guī)劃后的延遲時間都縮短了，另外還驗(yàn)證了規(guī)劃內(nèi)存方法的使用減少了嵌入式系統(tǒng)能耗。能耗的計算采用文獻(xiàn)[2]中的算法，如圖3（a）所示。
?
??? 文獻(xiàn)[1]中的算法是對頁進(jìn)行規(guī)劃時，尋找頁訪問次數(shù)最大，對列進(jìn)行規(guī)劃時，尋找列訪問次數(shù)最大。在具體應(yīng)用中，只能用一種方法。而本文同時對內(nèi)存中頁和行進(jìn)行規(guī)劃，所以對系統(tǒng)性能的提高更有效。圖3（b）是與文獻(xiàn)[1]算法的結(jié)果比較（僅給出能量消耗圖）,前者平均能量提高了大約10％。
?
??? 把本文的算法應(yīng)用于自行開發(fā)的嵌入式圖像處理系統(tǒng)中，獲得了良好的系統(tǒng)性能。
3? 結(jié)論和展望
??? 本文提出了一個通過減少對內(nèi)存訪問時塊間和塊內(nèi)頁間交換的次數(shù)和行間轉(zhuǎn)換的次數(shù)，使嵌入式系統(tǒng)內(nèi)存和能量資源能夠有效利用的方法。該方法可以直接應(yīng)用到嵌入式系統(tǒng)的內(nèi)存管理器中。因?yàn)殡S著用戶需求和功能的增加，越來越多的嵌入式系統(tǒng)需要處理大量的數(shù)據(jù)，所以對嵌入式系統(tǒng)的內(nèi)存采取管理是必要的。尤其對一些不帶MMU單元的操作系統(tǒng)來說，應(yīng)用中加入內(nèi)存管理程序?qū)ο到y(tǒng)性能的提高起到很大的作用。本文給出的內(nèi)存規(guī)劃策略能有效地減輕嵌入式系統(tǒng)負(fù)擔(dān)。本文是針對非數(shù)組的變量來討論的，但是也可以應(yīng)用到數(shù)組變量中。盡管使用的算法有可能沒有找到系統(tǒng)的最優(yōu)解，但使用這個算法，一定可以提高系統(tǒng)的性能。
??? 本文提出的算法不但可以應(yīng)用到嵌入式系統(tǒng)中的DRAMs，也可以應(yīng)用到其他支持行和列內(nèi)存訪問的存儲設(shè)備上，如flash存儲器。雖然目前一些多組SRAM的系統(tǒng)還不支持此算法，但是在將來的基于功耗設(shè)計的系統(tǒng)中，這種訪問模式是會被支持的。
??? 本文方法同流行操作系統(tǒng)內(nèi)存管理相比更簡單，更加適合嵌入式系統(tǒng)，同時彌補(bǔ)了現(xiàn)用嵌入式操作系統(tǒng)?滋CLinux等在內(nèi)存管理方面的不足。
參考文獻(xiàn)
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