基于嵌入式系統(tǒng)內(nèi)存規(guī)劃方法的研究

針對有內(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)是針對沒有MMU的處理器設(shè)計(jì)的，因此不能使用處理器的虛擬內(nèi)存管理技術(shù)，而采用實(shí)存儲(chǔ)管理策略，從而對內(nèi)存的訪問是直接的。它對地址的訪問不需要經(jīng)過MMU，而是直接送到地址線上輸出，所有程序中訪問的地址都是實(shí)際的物理地址。而且，大多數(shù)嵌入式操作系統(tǒng)對內(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)行。因而對內(nèi)存操作要格外小心。由此可見，開發(fā)者不得不參與系統(tǒng)的內(nèi)存管理，否則系統(tǒng)的效率和性能都不能令人滿意。開發(fā)者可以用一個(gè)內(nèi)存管理器來幫助管理內(nèi)存，可以借鑒流行操作系統(tǒng)對內(nèi)存池（pool）中塊（block）進(jìn)行管理的思想。訪問時(shí)先尋找對應(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)行改善。同時(shí)，內(nèi)存塊間相對位置也用同樣的方法進(jìn)行規(guī)劃，使得塊間的轉(zhuǎn)換也盡快完成。本文采用遺傳算法，同時(shí)對內(nèi)存數(shù)據(jù)存儲(chǔ)進(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ī)訪問時(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)?acacebdbefgfdah，則根據(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ù)。