基于操作系統(tǒng)中采用遺傳算法的內(nèi)存規(guī)劃研究

針對有內(nèi)存管理單元（MMU）的處理器設(shè)計的一些桌面操作系統(tǒng)（如Windows、Linux）都使用了虛擬存儲器的概念，虛擬內(nèi)存地址被送到MMU。在這里，虛擬地址被映射為物理地址，實際存儲器被分割為相同大小的頁面，采用分頁的方式載入進程。一個程序在運行之前，沒有必要全部裝入內(nèi)存，而是僅將那些當(dāng)前要運行的部分頁面裝入內(nèi)存運行。大多數(shù)嵌入式系統(tǒng)是針對沒有MMU的處理器設(shè)計的，因此不能使用處理器的虛擬內(nèi)存管理技術(shù)，而采用實存儲管理策略，從而對內(nèi)存的訪問是直接的。它對地址的訪問不需要經(jīng)過MMU，而是直接送到地址線上輸出，所有程序中訪問的地址都是實際的物理地址。而且，大多數(shù)嵌入式操作系統(tǒng)對內(nèi)存沒有保護，各個進程實際上共享一個運行空間。一個進程在執(zhí)行前，系統(tǒng)必須為它分配足夠的連續(xù)地址空間，然后全部載入主存儲的連續(xù)空間。從編譯內(nèi)核開始，開發(fā)人員必須告訴系統(tǒng)，這塊開發(fā)板到底擁有多少內(nèi)存；在開發(fā)程序時，必須考慮內(nèi)存的分配情況并關(guān)注應(yīng)用程序需要運行空間的大小。另外，由于采用實存儲器管理策略，用戶程序同內(nèi)核以及其他用戶程序在一個地址空間，程序開發(fā)時要保證不侵犯其他應(yīng)用程序的地址空間，不破壞系統(tǒng)的正常工作，使程序正常運行。因而對內(nèi)存操作要格外小心。由此可見，開發(fā)者不得不參與系統(tǒng)的內(nèi)存管理，否則系統(tǒng)的效率和性能都不能令人滿意。開發(fā)者可以用一個內(nèi)存管理器來幫助管理內(nèi)存，可以借鑒流行操作系統(tǒng)對內(nèi)存池（pool）中塊（block）進行管理的思想。訪問時先尋找對應(yīng)的塊，然后對物理地址進行頁的解碼，進而是行解碼，最后是列解碼和根據(jù)圖像處理系統(tǒng)處理大量數(shù)據(jù)的特點，對數(shù)據(jù)在內(nèi)存中的布局進行規(guī)劃。即同一塊中使連續(xù)訪問的數(shù)據(jù)在同一頁；在同一頁的數(shù)據(jù)，盡量安排在同一行，減小內(nèi)存訪問延遲，以便對性能進行改善。同時，內(nèi)存塊間相對位置也用同樣的方法進行規(guī)劃，使得塊間的轉(zhuǎn)換也盡快完成。本文采用遺傳算法，同時對內(nèi)存數(shù)據(jù)存儲進行頁、行、列的規(guī)劃，對塊間相對位置也進行了規(guī)劃。

1 內(nèi)存規(guī)劃

流行的操作系統(tǒng)對內(nèi)存訪問的基本方式是支持快速緩存，執(zhí)行的過程是把要訪問的地址整行拷貝到緩存區(qū)，先進行頁解碼和行解碼，然后進行列解碼并根據(jù)讀寫信號進行選擇。目前嵌入式系統(tǒng)中使用的DRAMs都支持高效內(nèi)存訪問模式，還特別支持流行的頁（page）訪問模式和區(qū)間（burst）訪問模式（相當(dāng)于以列為主的訪問）。這種訪問模式消耗的能量低于隨機訪問方式，例如，IBM′s Cu-11 Embedded DRAM macro支持的隨機訪問時間是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)常要進行元素間計算的，則把分別存儲A和C的塊放在相鄰的位置上，這樣，既可以減小地址總線的負擔(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ù)處理，這個條件可以滿足。處理過程可分為二步：第一步進行塊間的規(guī)劃；第二步對塊內(nèi)變量進行規(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)典遺傳算法，以此來驗證內(nèi)存規(guī)劃的有效性。本文的算法可記為LBP（LBP-Layout of Block and Page）。

2.1 算法的前提條件

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

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

（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ù)，然后對問題進行編碼和尋找最優(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ù)目有限，所以可用十進制編碼來表示變量（如把圖1中abcdefgh編碼為12345678）。

（3）雜交過程選擇同一代中的某些位進行交換，不同代的交換容易產(chǎn)生非法個體， 所以在某代個體內(nèi)部進行交換，可以提高算法的有效性。選取某代雜交的概率為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是用隨機訪問方法和本文的訪問方法進行實驗的結(jié)果。從表中可以看出，規(guī)劃后的延遲時間都縮短了，另外還驗證了規(guī)劃內(nèi)存方法的使用減少了嵌入式系統(tǒng)能耗。能耗的計算采用文獻中的算法，如圖3（a）所示。

文獻中的算法是對頁進行規(guī)劃時，尋找頁訪問次數(shù)最大，對列進行規(guī)劃時，尋找列訪問次數(shù)最大。在具體應(yīng)用中，只能用一種方法。而本文同時對內(nèi)存中頁和行進行規(guī)劃，所以對系統(tǒng)性能的提高更有效。圖3（b）是與文獻算法的結(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)負擔(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)，同時彌補了現(xiàn)用嵌入式操作系統(tǒng)CLinux等在內(nèi)存管理方面的不足。

責(zé)任編輯：gt