??? 摘? 要： 內(nèi)存訪問延遲是嵌入式系統(tǒng)性能提高的瓶頸,。本文以數(shù)據(jù)在內(nèi)存的存儲(chǔ)方式為出發(fā)點(diǎn)來解決內(nèi)存訪問延遲的問題，并用遺傳算法實(shí)現(xiàn)了優(yōu)化算法,。
??? 關(guān)鍵詞： 內(nèi)存規(guī)劃? 嵌入式系統(tǒng)? DRAM訪問模式? 存儲(chǔ)分配? 遺傳算法
?
??? 針對(duì)有內(nèi)存管理單元（MMU）的處理器設(shè)計(jì)的一些桌面操作系統(tǒng)(如Windows,、Linux)都使用了虛擬存儲(chǔ)器的概念，虛擬內(nèi)存地址被送到MMU,。在這里,，虛擬地址被映射為物理地址，實(shí)際存儲(chǔ)器被分割為相同大小的頁面,，采用分頁的方式載入進(jìn)程,。一個(gè)程序在運(yùn)行之前，沒有必要全部裝入內(nèi)存,，而是僅將那些當(dāng)前要運(yùn)行的部分頁面裝入內(nèi)存運(yùn)行,。大多數(shù)嵌入式系統(tǒng)是針對(duì)沒有MMU的處理器設(shè)計(jì)的，因此不能使用處理器的虛擬內(nèi)存管理技術(shù),，而采用實(shí)存儲(chǔ)管理策略,，從而對(duì)內(nèi)存的訪問是直接的。它對(duì)地址的訪問不需要經(jīng)過MMU,，而是直接送到地址線上輸出,，所有程序中訪問的地址都是實(shí)際的物理地址。而且,，大多數(shù)嵌入式操作系統(tǒng)對(duì)內(nèi)存沒有保護(hù),，各個(gè)進(jìn)程實(shí)際上共享一個(gè)運(yùn)行空間。一個(gè)進(jìn)程在執(zhí)行前,，系統(tǒng)必須為它分配足夠的連續(xù)地址空間,，然后全部載入主存儲(chǔ)的連續(xù)空間。從編譯內(nèi)核開始,，開發(fā)人員必須告訴系統(tǒng),，這塊開發(fā)板到底擁有多少內(nèi)存,；在開發(fā)程序時(shí),，必須考慮內(nèi)存的分配情況并關(guān)注應(yīng)用程序需要運(yùn)行空間的大小,。另外，由于采用實(shí)存儲(chǔ)器管理策略,，用戶程序同內(nèi)核以及其他用戶程序在一個(gè)地址空間,，程序開發(fā)時(shí)要保證不侵犯其他應(yīng)用程序的地址空間，不破壞系統(tǒng)的正常工作,，使程序正常運(yùn)行,。因而對(duì)內(nèi)存操作要格外小心。由此可見,，開發(fā)者不得不參與系統(tǒng)的內(nèi)存管理,，否則系統(tǒng)的效率和性能都不能令人滿意,。開發(fā)者可以用一個(gè)內(nèi)存管理器來幫助管理內(nèi)存，可以借鑒流行操作系統(tǒng)對(duì)內(nèi)存池（pool）中塊（block）進(jìn)行管理的思想,。訪問時(shí)先尋找對(duì)應(yīng)的塊,，然后對(duì)物理地址進(jìn)行頁的解碼，進(jìn)而是行解碼,，最后是列解碼和根據(jù)圖像處理系統(tǒng)處理大量數(shù)據(jù)的特點(diǎn),，對(duì)數(shù)據(jù)在內(nèi)存中的布局進(jìn)行規(guī)劃。即同一塊中使連續(xù)訪問的數(shù)據(jù)在同一頁,；在同一頁的數(shù)據(jù),，盡量安排在同一行，減小內(nèi)存訪問延遲,，以便對(duì)性能進(jìn)行改善,。同時(shí)，內(nèi)存塊間相對(duì)位置也用同樣的方法進(jìn)行規(guī)劃,，使得塊間的轉(zhuǎn)換也盡快完成,。本文采用遺傳算法，同時(shí)對(duì)內(nèi)存數(shù)據(jù)存儲(chǔ)進(jìn)行頁,、行,、列的規(guī)劃，對(duì)塊間相對(duì)位置也進(jìn)行了規(guī)劃,。
1? 內(nèi)存規(guī)劃
??? 流行的操作系統(tǒng)對(duì)內(nèi)存訪問的基本方式是支持快速緩存,，執(zhí)行的過程是把要訪問的地址整行拷貝到緩存區(qū),，先進(jìn)行頁解碼和行解碼,，然后進(jìn)行列解碼并根據(jù)讀寫信號(hào)進(jìn)行選擇。目前嵌入式系統(tǒng)中使用的DRAMs都支持高效內(nèi)存訪問模式,，還特別支持流行的頁(page)訪問模式和區(qū)間(burst)訪問模式（相當(dāng)于以列為主的訪問）,。這種訪問模式消耗的能量低于隨機(jī)訪問方式，例如,，IBM′s Cu-11 Embedded DRAM macro支持的隨機(jī)訪問時(shí)間是10ns,，而塊中頁訪問的時(shí)間是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)存存放的次序,，可以計(jì)算出訪問延遲的時(shí)間,。如果頁間訪問延遲時(shí)間是5個(gè)時(shí)鐘周期，記為Delay(P)=5cycles,，則在同頁中行間訪問延遲Delay(R)=3cycles,，同行中列間訪問延遲Delay(C)=1cycles。根據(jù)圖1(a)和圖1(b)中兩種存儲(chǔ)模式,，可以分別計(jì)算出如圖2所示的兩種內(nèi)存存儲(chǔ)方式下內(nèi)存訪問延遲時(shí)間：Latency(a)=47cycles,，Latency（b）=29cycles。
?
?
??? 同樣,，將相互訪問頻率較高的內(nèi)存塊,，如三個(gè)數(shù)組A、B,、C分別存放在不同的內(nèi)存塊,，數(shù)組A和數(shù)組C是經(jīng)常要進(jìn)行元素間計(jì)算的，則把分別存儲(chǔ)A和C的塊放在相鄰的位置上,，這樣,，既可以減小地址總線的負(fù)擔(dān)，也可以提高訪問時(shí)間和減少訪問次數(shù),。
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,，塊中每頁的大小為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ī)劃中訪問的頁間轉(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í),，通常是先尋找頁，再找到行,，最后找列,，則對(duì)頁訪問的耗時(shí)（一般稱為內(nèi)存訪問延遲）大于對(duì)同頁中的行，行訪問耗時(shí)大于同行中的列,。同時(shí)在相距較遠(yuǎn)的塊間訪問耗時(shí)大于相鄰塊間訪問,。
??? (2)減少內(nèi)存訪問中塊和頁的轉(zhuǎn)換次數(shù)，可以減少延遲和節(jié)省能量,。
??? (3)在頁/行/列之間轉(zhuǎn)換沒有優(yōu)先級(jí),，也就是從1～3頁和從1～2頁耗時(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è),，如果頁訪問模式延遲時(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）所示。
?
??? 文獻(xiàn)[1]中的算法是對(duì)頁進(jìn)行規(guī)劃時(shí),，尋找頁訪問次數(shù)最大,，對(duì)列進(jìn)行規(guī)劃時(shí)，尋找列訪問次數(shù)最大,。在具體應(yīng)用中,，只能用一種方法。而本文同時(shí)對(duì)內(nèi)存中頁和行進(jìn)行規(guī)劃,，所以對(duì)系統(tǒng)性能的提高更有效,。圖3（b）是與文獻(xiàn)[1]算法的結(jié)果比較（僅給出能量消耗圖）,前者平均能量提高了大約10％。
?
??? 把本文的算法應(yīng)用于自行開發(fā)的嵌入式圖像處理系統(tǒng)中,，獲得了良好的系統(tǒng)性能,。
3? 結(jié)論和展望
??? 本文提出了一個(gè)通過減少對(duì)內(nèi)存訪問時(shí)塊間和塊內(nèi)頁間交換的次數(shù)和行間轉(zhuǎn)換的次數(shù)，使嵌入式系統(tǒng)內(nèi)存和能量資源能夠有效利用的方法,。該方法可以直接應(yīng)用到嵌入式系統(tǒng)的內(nèi)存管理器中,。因?yàn)殡S著用戶需求和功能的增加，越來越多的嵌入式系統(tǒng)需要處理大量的數(shù)據(jù),，所以對(duì)嵌入式系統(tǒng)的內(nèi)存采取管理是必要的,。尤其對(duì)一些不帶MMU單元的操作系統(tǒng)來說，應(yīng)用中加入內(nèi)存管理程序?qū)ο到y(tǒng)性能的提高起到很大的作用,。本文給出的內(nèi)存規(guī)劃策略能有效地減輕嵌入式系統(tǒng)負(fù)擔(dān),。本文是針對(duì)非數(shù)組的變量來討論的，但是也可以應(yīng)用到數(shù)組變量中,。盡管使用的算法有可能沒有找到系統(tǒng)的最優(yōu)解,，但使用這個(gè)算法，一定可以提高系統(tǒng)的性能,。
??? 本文提出的算法不但可以應(yīng)用到嵌入式系統(tǒng)中的DRAMs,，也可以應(yīng)用到其他支持行和列內(nèi)存訪問的存儲(chǔ)設(shè)備上，如flash存儲(chǔ)器,。雖然目前一些多組SRAM的系統(tǒng)還不支持此算法,，但是在將來的基于功耗設(shè)計(jì)的系統(tǒng)中，這種訪問模式是會(huì)被支持的,。
??? 本文方法同流行操作系統(tǒng)內(nèi)存管理相比更簡(jiǎn)單,，更加適合嵌入式系統(tǒng)，同時(shí)彌補(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