??? 摘? 要: 內(nèi)存訪問延遲是嵌入式系統(tǒng)性能提高的瓶頸。本文以數(shù)據(jù)在內(nèi)存的存儲方式為出發(fā)點來解決內(nèi)存訪問延遲的問題,并用遺傳算法實現(xiàn)了優(yōu)化算法。
??? 關(guān)鍵詞: 內(nèi)存規(guī)劃? 嵌入式系統(tǒng)? DRAM訪問模式? 存儲分配? 遺傳算法
?
??? 針對有內(nèi)存管理單元(MMU)的處理器設(shè)計的一些桌面操作系統(tǒng)(如Windows、Linux)都使用了虛擬存儲器的概念,虛擬內(nèi)存地址被送到MMU。在這里,虛擬地址被映射為物理地址,實際存儲器被分割為相同大小的頁面,采用分頁的方式載入進(jìn)程。一個程序在運(yùn)行之前,沒有必要全部裝入內(nèi)存,而是僅將那些當(dāng)前要運(yùn)行的部分頁面裝入內(nèi)存運(yùn)行。大多數(shù)嵌入式系統(tǒng)是針對沒有MMU的處理器設(shè)計的,因此不能使用處理器的虛擬內(nèi)存管理技術(shù),而采用實存儲管理策略,從而對內(nèi)存的訪問是直接的。它對地址的訪問不需要經(jīng)過MMU,而是直接送到地址線上輸出,所有程序中訪問的地址都是實際的物理地址。而且,大多數(shù)嵌入式操作系統(tǒng)對內(nèi)存沒有保護(hù),各個進(jìn)程實際上共享一個運(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)行空間的大小。另外,由于采用實存儲器管理策略,用戶程序同內(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ù)的特點,對數(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)存訪問模式的特點可以改變嵌入式系統(tǒng)的性能。
??? 為了說明本文的規(guī)劃思想,假設(shè)內(nèi)存中有如圖1所示的變量a,b,c,d,e,f,g,h。若要訪問內(nèi)存中變量的次序為acacebdbefgfdah,則根據(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)用的特點,例如圖像處理系統(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},已知變量被訪問的次序為njnknl……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],以此來驗證內(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ù)都分配給獨立的內(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 實驗結(jié)果
??? 圖像處理系統(tǒng)的處理對象是象素,處理過程中使用大量的內(nèi)存,造成了嵌入式系統(tǒng)圖像處理應(yīng)用中的瓶頸。經(jīng)過近幾十年的發(fā)展,圖像處理算法也有很多成熟的算法??梢园堰@些算法經(jīng)過改造,使之適應(yīng)嵌入式系統(tǒng)體積小、容量小的特點。本文算法的提出是針對使用大量內(nèi)存,同時處理步驟相對簡單的系統(tǒng)設(shè)計的。本文采用一些標(biāo)準(zhǔn)(benchmark)系統(tǒng),提高嵌入式系統(tǒng)有限的內(nèi)存資源的利用率?;趦?nèi)存的規(guī)劃算法,用幾個內(nèi)存訪問序列驗證內(nèi)存規(guī)劃對嵌入式系統(tǒng)性能的改變。實驗中使用IFA(Image Flip Algorithm)、GSR(Gauss-Seidel formula)、CA(Compress Algorithm)、BIQUAD(Biquad_one_section)和FIR。后兩個例子是為了驗證非圖像處理的系統(tǒng)使用本算法的情況,說明算法的應(yīng)用具有一定的普遍意義。
??? 表1和表2是用隨機(jī)訪問方法和本文的訪問方法進(jìn)行實驗的結(jié)果。從表中可以看出,規(guī)劃后的延遲時間都縮短了,另外還驗證了規(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)存管理器中。因為隨著用戶需求和功能的增加,越來越多的嵌入式系統(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