針對嵌入式多媒體系統的外存頁面重映射
2008-12-31 00:00:00王力生康珊
計算機應用研究 2008年9期
摘 要：介紹一種基于硬件的、可編程的外存頁面重映射機制，它可以明顯地改善性能，并且由于減少了外存總線的訪問而降低了功耗。另外還提出了一種把應用數據與指令存儲器映射到外存頁面的高效算法，使用圖著色技術來支配頁面映射程序，目標是通過把沖突頁面重映射到不同的存儲體來避免頁面缺失。
關鍵詞：存儲器頁面重映射；存儲器著色；嵌入式系統；嵌入式控制器
中圖分類號：TP301 文獻標志碼：A
文章編號：1001-3695(2008)09-2697-03
External memory page remapping for embedded multimedia systems
WANG Lisheng，KANG Shan
(Dept. of Computer， College of Telecommunication， Tongji University， Shanghai 201804， China)
Abstract:This paper presented a hardwarebased， programmable external memory page remapping mechanism which could significantly improve performance and decrease the power budget due to external memory bus accesses.Also developed an efficient algorithm to map application data and instruction memory into external memory pages.Employed graphcoloring techniques to guide the page mapping procedure. The objective is to avoid page misses by remapping conflicting pages to different memory banks.
Key words:memory page remapping; memory coloring; embedded systems; memory controllers
在設計低成本、有限功耗的嵌入式系統時，由于與外存相關的延遲及其高總線容量，它是一個具有挑戰性的成本/性能設計點，嵌入式多媒體軟件應用程序（如MPEG-2/H.264編/解碼、JPEG編/解碼、語音處理G.721及PGP加密算法）都占有較高的存儲位置。這些應用程序都典型地以頻繁的數據存儲器訪問以及固定的訪問模式為特點。可以使用自意識存取模式的緩存以及存儲器規劃技術來改善外存訪問的性能[1]。然而大多數方法都把注意力集中在性能改善上，卻很少有考慮相關的功耗影響方面的工作。
1 研究背景
過去的研究表明嵌入式應用程序呈現出確定性的數據訪問模式。由于存儲器延遲是程序執行中一個不可忽略的部分，需要有效地利用這種對數據訪問模式的知識來調節嵌入式應用系統。
在許多嵌入式多媒體應用系統中，都是在執行著一些循環體，在數據元素的數組與矩陣中循環。循環變換（如循環展開、循環分塊）與數組重構可以通過增加這些存儲器訪問的局部性來改善數據訪問與性能[2]。先前的工作[3，4]已經指出可以重新安排存儲器訪問來顯著地改善應用系統的性能。通常都是用跨距以及索引之間的間距來描述與多媒體數據有關的外存訪問模式的特征[5]，Brown等人[6]則使用一種能捕獲開啟頁面數的工具來描述外存訪問模式。最近，Lee等人[7]對嵌入式多媒體應用系統中的性能/功耗之間的權衡進行了研究，并提出多媒體應用系統擁有三種存儲器訪問模式。存儲器訪問模式的分析一直被用來指導源代碼變換及數據規劃。數據規劃最優化的目標是減少緩存不命中次數，進而改善系統性能并降低功耗。Pettis與Hansen[8]提出了一種重新映射指令地址空間的方法。該方法企圖讓一個進程時常地調用在主存中相鄰的代碼來改善緩存的性能。他們考慮了程序大小以及程序的組織問題。
在多媒體應用系統中，數據訪問模式包括幾個大規模的緩沖器存儲視頻幀、音頻樣本以及位流抖動緩沖器。對這些緩沖器的訪問會產生大量的不連續訪問，這些訪問之間擁有很大的跨距。圖1、2顯示了兩種主要的模式。圖1描述了一種在FIR數字濾波器與二維圖像漸變中廣泛使用的模式。二維跨距訪問模式由圖2所示，它一般用在運動估計、圖像預處理/后加工、運動補償以及圖像渲染中。
2 頁面重映射算法
本文研究的核心是改善廣泛用在嵌入式系統中的外部SDRAM的訪問效率。這里可以把一個SDRAM看做一組包含大量頁面的存儲體。頁面大小取決于專門的存儲器生產商以及存儲器的結構。通常情況下，頁面大小為1 KB。圖3顯示了一種典型的SDRAM。在每個存儲體內部，只有一個頁面可以在某一時刻被開啟或訪問，故某時刻可開啟的最大頁面數等于存儲體的總數。
在一個多體存儲系統中，如果連續訪問同一個存儲體，那么存儲器控制器便會發出一個“加壓”命令來關閉那個存儲體中已開啟的頁面，然后緊跟著一條“激活”命令來開啟將要訪問的頁面。從“加壓”到“激活”這個時間段，存儲器僅僅處理狀態轉變，并沒有實際地轉移數據。這個“轉變時間”稱為“頁面丟失損失”。若下一個要訪問的頁面在另一個存儲體中，相關的“加壓”與“激活”命令會與當前正在進行的數據轉移同時進行，因此，這個頁面丟失就被當前的轉移操作隱藏掉了。將頁面缺失最小化對功耗與性能的改善都有好處。
2.1 頁面重映射的動機
回到圖3，一個SDRAM可以被分解為M個獨立的存儲體，每個體包含N個頁面。每個頁面由Ii， j表示；i是存儲體索引號，j是體內頁面索引號。對于一個已給的程序，追蹤工具（profiling tool）可以產生頁面發生轉換頻率的數據。例如，若把頁面Ii， j移到頁面Ip，q，就稱為S（Ii， j，Ip，q）現代的32位處理器支持物理地址擴展（PAE）模式，它允許硬件尋址高達64GB的存儲空間。然而外部設備（如DMA）只能訪問較低的4GB存儲空間。因此，為了DMA操作，可以把數據復制到那部分空間內。但是使用這種方法會帶來巨大的開銷，因為它涉及到了存儲器的復制。為了避免這個弊端，一些計算機系統提供可編程的硬件來支持使用一個單獨的存儲器管理單元（MMU）為數據轉移重映射存儲器。
操作系統加載程序通過選擇可用頁面或線性地分配頁面將新頁面映射到存儲器，直至存儲器被用完。如果可以使用頁面基本信息來指示操作系統將頁面重新映射到新的物理地址上，便可以最優外部存儲器訪問。這僅需對操作系統與鏈接程序作小小的修改。圖4顯示了一個帶有數據緩存與I/O DMA的嵌入式系統。
圖中在外部總線接口單元的前面插入了一個頁面重映射模塊，其功能是在兩個屬于同一頁面PMT會連同每個在執行的程序一起提供給操作系統或鏈接程序，它們將會根據PMT中提供的信息把程序加載到存儲器頁面，而操作系統存儲器管理系統會按圖4所示的那樣執行頁面重映射模塊。由于多媒體程序要執行很長時間，并且只在第一次加載程序時才發生重映射，重映射算法是低開銷的。
2.2 重映射算法
在此將描述一下產生頁面重映射表的算法。該算法的基本想法是把外存當做一個二維的頁面數組來對待。在數組中同行的頁面共享同樣的行地址，同列的頁面共享同一個存儲體。重映射進程的目的是要重新分配頁面的物理地址，目的是為了使同列中或同個存儲體中的轉換最小化。在該算法中，被重映射的頁面局限于同行中的再分配，這個限制可以大大地減小PMT的大小。
存儲器頁面布局的二維特性允許把這個算法歸為著色問題。每個存儲體被著以不同的顏色。對于每個頁面來說，首先分配給它一個試探性的顏色或存儲體。如果被重映射的頁面與另一個頁面沖突，那么將重新分配顏色來最小化沖突引起的代價。該算法構建了一張頁面轉換圖，每個節點代表一個頁面，兩節點之間的邊被賦上了權值（該權值表示這兩個頁面間發生的頁面轉換次數）。這個算法的重點在于消除第一次頁面轉換時的沖突。
當把一個頁面映射到物理內存時，該算法會設法分配一個沒有沖突的顏色或與先前被映射頁面間沒有發生頁面轉換的存儲體，這樣做是為了避免轉換損失。若沖突不可避免，將激發著色程序在一行頁面中選擇，通過使用這個程序來確保解決轉換圖中的第一次頁面轉換沖突并不會增加總負擔。
2.2.1 頁面轉換圖
轉換圖捕獲了在程序執行中的頁面穿越。本文算法通過構建帶有權重邊的頁面轉換圖開始，邊上的權重是由剖析進程捕獲的，權重代表轉換次數。邊上的權值越大意味著轉換越頻繁。圖5（a）展示了一個有4行內存頁面4個存儲體的存儲器系統，總共是16個頁面。程序使用了其中7個。為了描述該算法，7個頁面任意地分布在存儲器中。每個頁面由其體地址與頁面行地址指出。（b）是一個頁面轉換圖，它是用追蹤工具產生的。
2.2.2 頁面著色
頁面地址重映射的工作是定義一個頁面重映射表，目的是為了最小化SDRAM體中的頁面轉換。本文將通過圖5的例子詳細地描述頁面著色算法。尋找最佳頁面著色是一個NP完全問題，所以使用探索式方法來解決這個問題。
算法首先按照轉換圖中邊上的權值排序；然后使用這個排好序的集合，并把不同的顏色分配給這些邊連接的頁面。當啟動著色進程時，頁面都是沒有被映射過的。而在處理每條邊時，就把每條邊所關聯的頁面進行重映射。在映射期間要考慮三種類型的信息：a） 這個頁面是否已被映射過；b） 已經被指定顏色的頁面的存儲體號；c） 權值參數數組。
每個頁面都有一個特有的權值參數數組，它包含了那個頁面與所有其他頁面的關系，并且該數組還隱含了把一個頁面放到每個存儲體所需的代價。例如，若一個頁面的權值參數數組為{500，0，100，0}，那么就意味著映射到體0的代價是500，映射到體2的代價是100，而映射到其余兩個體的代價為0。該算法的目標是將最終消耗最小化。顯而易見，在這種情況下，該頁面應該被映射到體1或體3。所有的存儲體的權值參數初始值都為0。
在每個頁面被映射后，此頁面以及與它相連的頁面的參數數組都需要更新。對于所有正在被處理的邊來說，有五種可能出現的情形：
a）邊連接的兩個頁面都還未被映射到物理內存中，它們來自不同的頁面行，兩行中有一行是有開啟位置的，但是不在同一體中。由于可以分配給它們不同的顏色，并且將其重新映射到不同的體號，這是一種較簡單的情形。權值參數數組將根據其存儲體的位置而更新。
b）該情形與第一種情形相類似，除了兩個頁面當中有一個已經被映射過了，未被映射過的可以被放到一個非沖突的位置上。
c）除了兩個頁面都已經被映射到不同的存儲體之外，也與上兩個情形相似。無須重映射，只有這兩個頁面的權值參數需要更新。
d）當這條邊所關聯的兩個已被處理過的頁面被映射到同一行時，可以確保它們是不沖突的，因此也就不需要做什么。
e）前三種情形需要存儲器有空余的空間將頁面放入不同的體中。該情形是用來處理這種要求不能被滿足的情況。在此情形下，兩個頁面只能被放在同一個存儲體中（如一種沖突的場合）。依然把頁面放入有空的存儲體中，然后選擇一個頁面行來為那個行中的所有頁面重新指定體號，進而解決沖突。
每個頁面的權值參數通常并不改變，并且與頁面是怎樣被映射的毫無關系。僅當頁面被映射到一個非0權值參數的存儲體時，這個權值會被計入總代價中。在情形e)中，有兩種選擇來最小化沖突代價:(a)用窮舉法在所有可能的存儲體分配中選擇一個代價最小的。這個方法的復雜度是O(N!)（N是存儲體個數）。此方法僅適用于小數目的存儲體數（2或4個）。（b)貪心算法，它僅調動沖突的頁面，將其與其他被映射的頁面調換。此方法復雜度為O(N)，它就適用于大數目的存儲體（8或16個）。在多數情況下，仍然可以作出非沖突的分配，然而在某些應用程序中，沖突是不可避免的，只能被最小化。
上述的進程一直重復執行，直至轉換圖中所有的邊都被處理完畢。
3 實驗
筆者選擇了模擬設備Blackfin家族片上系統處理器作為主要對象，所有的程序都使用模擬設備VDSP++工具鏈來編譯和模擬。首先在頁面重映射停用的前提下使用程序追蹤文件探查器來產生頁面轉換圖，把這張圖傳回給頁面著色算法來計算最優的頁面重映射表（PMT）；然后在啟用頁面重映射的前提下將生成的PMT再裝回改進的模擬設備中，頁面重映射模塊將加載PMT，并過濾掉通過外部總線的所有地址通信。功耗和延遲的統計數據都是被監控的，高速緩沖存儲器模型也被嵌入到模擬器中來精確地模擬基準程序的性能。
實驗的目標是為了證實頁面重映射方案在功耗與性能方面的所帶來的好處。在工作平臺上，模擬了一個外部的SDRAM存儲器，它有2、4和8個存儲體，頁面大小為1KB。該SDRAM配置的更多細節可參閱文獻[9]。在著色映射中，顏色的數量等于2、4和8，與存儲體數量相同。
表1描述了本文所研究的基準程序的主要特征。實驗是在一套多媒體負載中運行的，并選擇了MPEG-2與H.264來處理視頻，JPEG來進行圖像壓縮，G.721來進行聲音處理以及用PGP加密。從表中可見，視頻基準程序（MPEG-2與H.264）與其他基準程序相比，對存儲器給予了較大的壓力。而PGP是所有基準程序中工作量最小的，工作量與存儲器大小都會影響頁面重映射算法的結果。
表1 實驗中所用的基準程序以及其重要指數
基準程序總周期數效用比請求/周期指令大小/KB數據大小/MB
表2把原始程序與頁面重映射程序的頁面缺失率進行了比較，并顯示了由于SDRAM中的頁面重映射而引起的改善百分比。結果顯示，通過加入頁面重映射模塊，在一個2體SDRAM系統中達到40.2%的改善，在4體SDRAM系統中可以達到69.7%，而在8體系統上可達到81.4%。
表2 基準程序頁面缺失降低率
4 結束語
外存系統性能對嵌入式應用系統來說是至關重要的，本文使用一種追蹤向導（profile guided）的軟/硬件方法來執行頁面重映射。該算法考慮了嵌入式多媒體應用系統的頁面存取模式，描述了一種高效的著色理論來智能地將頁面映射到外存中以避免頁面缺失。實驗結果證明了頁面重映射算法的效用。與原始程序映射相比，該算法可將頁面缺失率降低70%~80%，用頁面缺失率的降低換來了性能的提高及功耗的減少。
參考文獻：
[1]BOSE P，ALBONESI D H，MARCULESCU D.Guest editors’introduction:power and complexity aware design[J].IEEE Micro，2003，23(5):811.
[2]BYNA S， SUN X H，GROPP W，et al.Predicting memory access cost based on dataaccess patterns[C]//Proc of IEEE International Conference on Cluster Computing.Washington DC:[s.n.]，2004:327-336.
[3]KANDEMIR M，RAMANUJAM J，CHOUDHARY A.Improving cache locality by a combination of loop and data transformations[J].IEEE Computer Society，1999，48(2):159167. [4]McKINLEY K S，CARR S，TSENG C.Improving data locality with loop transformations[J].ACM Press，1996，18(4):424-453.
[5]PHALKE V，GOPINATH B.Program modelling via interreference gaps and applications[C]//Proc of the 3rd International Workshop on Modeling， Analysis， and Simulation of Computer and Telecommunication Systems.Washington DC:[s.n.]，1995:212-216.
[6]BROWN M，JENEVEIN R M，ULLAH N.Memory access pattern analysis[C]//Proc of the Workload Characterization:Methodology and Case Studies.Washington DC:[s.n.]，1998:105113.
[7]LEE J，PARK C，HA S.Memory access pattern analysis and stream cache design for multimedia applications[C]//Proc of Conference on Asia South Pacific Design Automation.New York:[s.n.]，2003:22-27.
[8]PETTIS K，HANSEN R C.Profile guided code positioning[C]//Proc of ACM SIGPLAN Conference on Programming Language Design and Implementation.New York:[s.n.]，1990:16-27.［9］Analog Devices Inc，NORWOOD M A.SDRAM selection guidelines and configuration for ADI processors[EB/OL].(2004)[2004-0813].http://www.analog.com/processors/china/blackfin/technicalLibrary/applicationNotes/index.html.
[10]鐘玉琢，喬秉新.運動圖像及其伴音通用編碼國際標準——MPEG-2[M].北京：清華大學出版社，1997.
[11]畢厚杰.新一代視頻壓縮編碼標準——H.264/AVC[M].北京：人民郵電出版社，2005:191. [12]黎洪松.數字視頻技術及其應用[M].北京：清華大學出版社，1997.
