嵌入式多媒體應用中的片上存儲器分配

引    言

隨著CPU速度的迅速提高，CPU與片外存儲器的速度差異越來越大，匹配CPU與外部存儲器的方法通常是采用Cache或者片上存儲器。微處理器中片上存儲器結(jié)構(gòu)通常包含指令Cache ，數(shù)據(jù)Cache 或者片上存儲器。對于嵌入式設備上的數(shù)據(jù)密集的應用，數(shù)據(jù)Cache 與片上存儲器相比存在以下缺陷：（1） 片上存儲器是固定的單周期訪問，可在設計時而不是運行時研究數(shù)據(jù)訪問模式；而Cache還要考慮擊不中的情況，因而有可變的數(shù)據(jù)訪問時間，執(zhí)行時間的預測更加困難。（2） 使用Cache 執(zhí)行時間的不可預測性影響編譯器的優(yōu)化；（3） 細顆粒的Cache 對于圖像編碼等的規(guī)則數(shù)據(jù)訪問并不合適，因而使用Cache 對于嵌入式設備可能不是最優(yōu)的。文指出，對于大多數(shù)應用，使用片上存儲器比使用數(shù)據(jù)Cache能量平均大約節(jié)省40 % ，芯片面積與時間的乘積僅為Cache的46%。因而對于嵌入式多媒體處理器，片上RAM作為數(shù)據(jù)Cache的替代，功耗更低。片上存儲器的有效使用對于提高嵌入式應用的速度，降低功耗具有重要的意義。

文討論了在同時具有數(shù)據(jù)Cache和片上SRAM的處理器上標量和矩陣變量的存儲器分配方法。文以摩托羅拉公司的DSP56000為平臺，文以AMS Gepard DSP為平臺，分別討論了如何把數(shù)據(jù)分配到X/Y數(shù)據(jù)存儲器塊，以便最大限度地利用數(shù)據(jù)移動的并行性。DSP56000片上X、Y數(shù)據(jù)存儲器都是單端口的，并且容量較小。與DSP56000不同，TI公司的TMS320C55x具有更多的數(shù)據(jù)總線，片上RAM容量更大，且分塊多，具有訪問能力更強的 DARAM。

TMS320C55x具有極低的功耗（0.05mW/MIPS） ，非常適合手持設備，現(xiàn)在已經(jīng)集成至TI 公司專門針對3G手機的高性能多媒體處理器上。C55x 片上除了24K字節(jié)的指令Cache外，還有64K字節(jié)的雙端口存儲器（DARAM），96K字節(jié)的單端口存儲器（SARAM）。DARAM和SARAM 總共160K字節(jié)，分成20個塊，每個塊8K字節(jié)。本文以C55x的視頻編碼器為例，討論片上存儲器的有效使用。

數(shù)據(jù)的片外、片上動態(tài)分配

因為片上存儲器比片外存儲器具有更高的數(shù)據(jù)訪問能力和更小的訪問功耗，所以盡可能分配數(shù)據(jù)到片上存儲器，未能分配到片上的數(shù)據(jù)可在CPU處理前轉(zhuǎn)移到片上，已經(jīng)轉(zhuǎn)移到片上的數(shù)據(jù)，應盡可能在片上保存直到其生命期結(jié)束，以便盡可能減少數(shù)據(jù)從片外存儲器到片上存儲器的數(shù)據(jù)轉(zhuǎn)移。在視頻編碼等應用中，標量、常數(shù)相對于矩陣而言，通常數(shù)量較少，可以分配到片上；若分配到片外，在運算時直接存取片外數(shù)據(jù)，CPU流水線將會停滯。直接存儲器存取（DMA）可以在存儲器之間，存儲器與外設之間轉(zhuǎn)移數(shù)據(jù)，除了DMA通道參數(shù)初始化以外，DMA轉(zhuǎn)移數(shù)據(jù)和CPU處理數(shù)據(jù)可以并行進行。設置DMA通道參數(shù)需要一定的時間，采用DMA來轉(zhuǎn)移單個變量或常數(shù)的開銷可能比直接存取更大，因此DMA適合轉(zhuǎn)移具有較多數(shù)據(jù)的矩陣，并不適合片外標量的轉(zhuǎn)移。包含大量元素的矩陣可以分配到片外，處理前使用DMA轉(zhuǎn)移到片上存儲器。

局部變量由編譯器分配到軟件棧上，C55x具有兩個軟件棧：數(shù)據(jù)棧和系統(tǒng)棧。C55x的棧有三種工作模式，可設置成雙16比特快返回模式，以減少棧所占的存儲器空間，并提高其運行速度。數(shù)據(jù)棧和系統(tǒng)棧在函數(shù)調(diào)用及返回時同時訪問，可將這兩個棧分配到DARAM塊或者不同的SARAM塊內(nèi)。

本文中數(shù)據(jù)存儲器的分配，強調(diào)從實際多媒體應用處理的基本數(shù)據(jù)塊出發(fā)，分析簡單直觀。多媒體算法總是將原始輸入數(shù)據(jù)分成一定大小的塊進行處理，并產(chǎn)生對應該輸入的最后輸出。如果片上沒有足夠的存儲器，大量的輸入數(shù)據(jù)和最后結(jié)果僅能可存儲在片外。對于元素較多的矩陣，可以根據(jù)算法特征將矩陣分成若干數(shù)據(jù)子塊，如H.263編碼器中的宏塊，搜索窗等，或者單純根據(jù)可得到的片上存儲器數(shù)量分成適當大小的子塊逐個運算，然后分析數(shù)據(jù)子塊的生命期和使用頻率。我們定義數(shù)據(jù)子塊的生命期為首次使用到最后一次使用之間的間隔，而通常變量的生命期為定義到最后使用之間的間隔，例如定義整型數(shù)組int MB[384]，用來存儲待編碼宏塊的數(shù)據(jù)，圖像的某個宏塊的數(shù)據(jù)在該宏塊編碼結(jié)束后，該宏塊數(shù)據(jù)的生命期也就結(jié)束，然后該數(shù)組用來存儲下一宏塊的數(shù)據(jù)，因而變量的生命期遠比存儲在該變量中的某一具體數(shù)據(jù)生命期要長。若數(shù)據(jù)子塊具有不相交的生命期，則可以共享相同的片上存儲器。

很多數(shù)據(jù)子塊在運算中多次使用，可在首次運算前轉(zhuǎn)移到片上，并盡可能保存到生命期結(jié)束，即直到這些數(shù)據(jù)不再使用為止，因而這些數(shù)據(jù)僅需要一次轉(zhuǎn)移。將程序執(zhí)行時間看成是由很多連續(xù)的時間間隔組成的，若在下個時間間隔內(nèi)需要轉(zhuǎn)移新的數(shù)據(jù)到片上供CPU處理，而片上又沒有足夠的存儲器存儲這些數(shù)據(jù)，這時將隨后需要連續(xù)頻繁使用的數(shù)據(jù)保留到片上；對于隨后較少使用的數(shù)據(jù)，若片外存儲器還保存有該數(shù)據(jù)的備份，這些數(shù)據(jù)可直接覆蓋，等到下次使用時再從片外存儲器拷貝到片上；否則，在覆蓋前將數(shù)據(jù)轉(zhuǎn)移到片外。在片上分配一定的緩沖區(qū)，用來存儲需要再次使用的數(shù)據(jù)，可有效地減少片外存儲器的訪問。對于中間結(jié)果，盡量在使用前分階段計算，使用后釋放，以縮減存儲中間結(jié)果的存儲器需求。通過數(shù)據(jù)的這種動態(tài)分配，既可以減少或避免訪問片外慢速存儲器所引起的指令延遲，又可以減少片外到片上的數(shù)據(jù)轉(zhuǎn)移。

在H.263視頻編碼器中，編碼是按宏塊順序進行的，INTRA宏塊編碼僅需要當前的編碼宏塊數(shù)據(jù)，INTER宏塊編碼還需要以當前宏塊為中心的重建圖像搜索窗。因此根據(jù)算法特征將整幀輸入圖像劃分成宏塊，某個宏塊數(shù)據(jù)在編碼前轉(zhuǎn)移到片上，這一宏塊編碼結(jié)束后就不再使用，這部分片上存儲器就可釋放，用來存儲下一宏塊數(shù)據(jù)。若在編碼的同時采用DMA轉(zhuǎn)移下一個宏塊，這需要在片上分配兩個宏塊的存儲器空間，用來存儲編碼的原始圖像。

在進行INTER幀編碼時，運動搜索需要使用前一幀的重建圖像作為參考，設搜索范圍為 [-16，+16]，編碼該宏塊需要搜索參考圖像中以編碼宏塊位置為中心的9個宏塊，即前一幀中宏塊（x，y） 的的重建圖像直到編碼（x+1，y+1）宏塊后生命期才結(jié)束。以CIF分辨率為例，不可能把一幀圖像的所有重建宏塊保存到生命期結(jié)束，因而部分重建圖像必需暫時存儲在片外，若在編碼（x-1，y-1） 前將重建宏塊（x，y）拷貝到片上并一直保存到編碼（x+1，y+1） 宏塊結(jié)束，只需要在片上分配將近3個GOB的空間用來存儲參考圖像，就可以保證每個宏塊的重建圖像數(shù)據(jù)只需要一次片外到片上的轉(zhuǎn)移。

半像素內(nèi)插結(jié)果，用于在整像素運動搜索后作為半像素搜索的參考，因而可在整像素搜索后、半像素搜索前，圍繞整像素運動矢量，對整像素運動矢量對應的匹配宏塊進行內(nèi)插，這樣就沒有必要在編碼INTER 幀前將整幀圖像進行內(nèi)插，可顯著減少存儲內(nèi)插結(jié)果的存儲器數(shù)量，從而分配在片上。

片上數(shù)據(jù)的存儲器分配

TMS320C55x 除了讀指令的地址數(shù)據(jù)總線外，還有三條用于從存儲器讀操作數(shù)的地址數(shù)據(jù)總線，兩條寫操作數(shù)到存儲器的地址數(shù)據(jù)總線。CPU在一個周期內(nèi)可完成多個操作數(shù)的讀寫，由于每個DARAM塊或SARAM塊有限的訪問能力，這些操作數(shù)位于適當?shù)腄ARAM或SARAM塊內(nèi)，才能在單周期內(nèi)完成多個數(shù)據(jù)的讀入或者數(shù)據(jù)的同時讀寫，而不產(chǎn)生延遲。

指令代碼的分配

應用程序的指令代碼可以存儲在片外存儲器，通過指令Cache進行訪問，可以減少CPU讀指令代碼與CPU讀寫片上存儲器內(nèi)數(shù)據(jù)的沖突，同時將空余更多的片上存儲器空間用于數(shù)據(jù)分配。若存儲程序代碼和數(shù)據(jù)所需的存儲器總和少于片上存儲器容量，將代碼分配到片外存儲器的性能與代碼數(shù)據(jù)全部分配到片上存儲器相比，性能降低大約10%。因此當代碼和數(shù)據(jù)總和小于片上存儲器容量時，應該全部分配到片上存儲器。通常程序代碼僅供CPU讀取、并不修改，而數(shù)據(jù)經(jīng)常需要同時讀寫，因而應盡量將代碼存儲在SARAM內(nèi)，以便將訪問能力更強的DARAM用來存儲數(shù)據(jù)。在單個CPU周期內(nèi)，SARAM僅有一次訪問能力，同時讀取指令和數(shù)據(jù)必然產(chǎn)生延遲，為了保證讀取數(shù)據(jù)時不產(chǎn)生延遲，數(shù)據(jù)不能與訪問這些數(shù)據(jù)的代碼存儲在同一SARAM塊內(nèi)。也就是說，當程序代碼大小不是剛好整數(shù)個塊大小時，可通過調(diào)整代碼或者數(shù)據(jù)的存儲器分配，以免CPU讀代碼與讀寫數(shù)據(jù)產(chǎn)生沖突。

數(shù)據(jù)分配

前面已經(jīng)討論過變量和常數(shù)的分配，這里主要討論耗時較多的矩陣運算。通常可以用C語言或者匯編語言編寫應用程序，C語言編譯后可產(chǎn)生匯編代碼。在匯編語言的代碼中，找到處理矩陣操作數(shù)的指令，依次列舉這些指令不產(chǎn)生延遲的矩陣分配限制，并求解滿足這些限制條件的片上存儲器分配。下面列出了C55x中一些常見的存儲器操作數(shù)訪問形式：

（1） Xmem read ‖Ymem read。

Xmem write ‖Ymem write。

Xmem read ‖Ymem write。

為了不產(chǎn)生延遲，要求Xmem 和Ymem 位于DARAM塊內(nèi)或者不同的塊內(nèi)。

（2）Lmem1 read ‖Lmem2 write。

為了不產(chǎn)生延遲，要求Lmem1和Lmem2位于DARAM塊內(nèi)或者不同的塊內(nèi)。

（3） Xmem read ‖Cmem read。

例如匯編指令：MACMR Xmem，Cmem，ACx，為了不產(chǎn)生延遲，Xmem，Cmem不在同一塊內(nèi)，這包括不在同一SARAM塊內(nèi)，也不在同一DARAM內(nèi)。

（4） Xmem read ‖Ymem read ‖Cmem例如匯編指令：MPY Xmem ，Cmem ，AC0 ：：MPY Ymem ，Cmem，AC1 以及FIRSADD Xmem ，Ymem ，Cmem ，ACx ，ACy 都要求Xmem 和Ymem 位于DARAM塊內(nèi)或者不同的SARAM塊內(nèi)，并且Xmem ，Cmem不在同一塊內(nèi)。

上述指令不產(chǎn)生延遲的約束條件可分成兩類基本約束條件：（1）兩變量位于DARAM塊內(nèi)或者兩變量位于不同的塊內(nèi)，記為條件A，這是由SARAM塊或者DARAM塊訪問能力產(chǎn)生的限制 （2）兩變量位于不同的塊內(nèi)，記為條件B，這是由于CPU總線的特殊結(jié)構(gòu)產(chǎn)生的限制。其中條件A中的兩變量可在同一DARAM塊內(nèi)，或者不同的SARAM 塊內(nèi)，或者一個變量在DARAM內(nèi)，另一個在SARAM內(nèi)。條件B 指的是兩變量在不同的DARAM塊內(nèi)，或者在不同的SARAM塊內(nèi)，或者一個變量在DARAM塊內(nèi)，另一個在SARAM 塊內(nèi)。條件A可看成是兩種條件的邏輯或關(guān)系。

A = B or C。

其中條件C定義為兩變量都位于DARAM塊內(nèi)。循環(huán)中的操作數(shù)一般表現(xiàn)為矩陣的一個元素，在一個應用程序中，通常有多個矩陣，矩陣中的元素應同時滿足多個上述基本條件。當矩陣較多，限制條件復雜時，可以使用計算機求解數(shù)據(jù)存儲器分配，以滿足矩陣訪問不產(chǎn)生延遲的條件。在這里，我們只需要求出滿足條件的一個解，并不需要求出所有可能的解，因而對求解問題做一定的簡化。

設x，y分別是矩陣X，Y的某一個元素，X，Y位于不同的塊內(nèi)是 x，y位于不同的塊內(nèi)的充分條件，同樣X，Y都位于DARAM內(nèi)或者不同的塊內(nèi)是x，y都位于DARAM內(nèi)或者不同的塊內(nèi)的充分條件，例如X位于 DARAM塊，Y矩陣部分位于與X 相同的DARAM內(nèi)，其余位于SARAM內(nèi)，也能使x，y滿足條件A。

例如：N個矩陣需要同時滿足N1個A 類條件和N2個B類條件。從每個A類條件中任選一個條件（B或者C），最多有2N1個組合，每種組合與N2個b類條件聯(lián)立求解，其中某些組合可能沒有解，任意一個解都能滿足不產(chǎn)生延遲的條件。這時任何一種組合中可能包含M （0<=M<=N1）個C類條件，其余的為B類條件。

C 類條件是兩個矩陣必需在DARAM塊，將需要滿足C類條件的所有矩陣存儲器的大小相加，相同的矩陣不重復累加，結(jié)果為需要分配到DARAM的矩陣總數(shù)量，當結(jié)果超過可得到的片上DARAM數(shù)量時，這種條件組合下就沒有解。

每個B類條件要求某兩個矩陣必需在不同的塊內(nèi)，由于存在多個B 類條件，事實上可能要求多個矩陣相互不在同一個塊內(nèi)，例如要求矩陣A1和A2不在同一塊內(nèi)，矩陣A3和A1不在同一塊內(nèi)，矩陣A3和A2不在同一塊內(nèi)，這實際上是要求A1，A2，A3相互不在同一塊內(nèi)。若有一組矩陣，其中任何兩個矩陣都必需分配在不同的存儲器塊內(nèi)，稱為B類約束矩陣組。若不存在一個矩陣，要求與某個B類約束矩陣組中的所有矩陣都存在B類約束關(guān)系，稱這個組為最大B類約束矩陣組。最大B 類約束條件矩陣組中的矩陣數(shù)目就是分配這些矩陣所需的最少的存儲器塊數(shù)。

下面給出了以某個B 類約束條件中的兩矩陣為基礎(chǔ)，求解包含這兩個矩陣的最大B 類約束矩陣組的步驟。

（1） 取出其中一個B 類約束條件，不妨設為S2=（A1，A2），初始化其標志為1。

（2） 求出包含（A1，A2） 所有可能的三矩陣組如（A1，A2，A3），（ A1，A2，A4），（A1，A2，A5）等，由所有的三矩陣組構(gòu)成一個集合，記為S3，并初始化S3中的各個元素標志為1。若S3為空集，即沒有包含（A1，A2）更大的B類約束組，則停止以該條件為基礎(chǔ)的繼續(xù)搜索；若S3中僅僅包含一個元素，這時這個三矩陣組為包含（A1，A2）最大B 類約束矩陣組，停止以該三矩陣組為基礎(chǔ)的繼續(xù)搜索。只要S3 不為空集，更新原兩矩陣組標志為0。求包含（A1，A2）的三矩陣組的過程，只需要檢查出現(xiàn)次數(shù)不小于2的那些矩陣，若檢查Ai，只需判斷是否存在限制（Ai，A1） 及（Ai，A2）

（3）分別以S3集合中的各個三矩陣組為基礎(chǔ)，檢測是否存在包含此三矩陣的四矩陣組，并初始化檢測到的四矩陣組標志為1，由這些四矩陣組構(gòu)成S4。若檢查到包含此三矩陣的四矩陣組，將原來的三矩陣組標志更新為0；若S4中僅僅包含一個元素，停止以該四矩陣組為基礎(chǔ)的繼續(xù)搜索。搜索四矩陣組的過程，也可簡化為：簡單檢查S3集合中的三矩陣組能否兩兩合并，并初始化合并后的四矩陣組標志為1。若某兩個矩陣組能夠合并，更新它們的標志為0。例如檢查（A1，A2，A3）和（A1，A2，A4） 能否合并，只需檢查是否存在限制條件（A3，A4）；檢查（A1，A2，A3） 和（A1，A2，A5） 能否合并，只需檢查是否存在限制條件（A3，A5）。

（4） 繼續(xù)由四矩陣組搜索五矩陣組，五矩陣組到六矩陣組。直到矩陣組的集合為空集或僅有一個元素，停止搜索。

（5）上述各矩陣組中標志為0已經(jīng)被更大的矩陣組取代，標志為1的矩陣組表示它為包含該矩陣組中各矩陣的最大矩陣了，因此標志為1的矩陣組就是最大B類約束矩陣組。

分別以每個B類約束條件為基礎(chǔ)，搜索包含這兩個矩陣分配的最大B類約束矩陣組；由所有的最大B類約束矩陣組構(gòu)成一個集合S，刪除S中相同的元素，比較各個最大B類約束矩陣組中的矩陣數(shù)量，包含矩陣數(shù)量最多的B 類約束組中的矩陣數(shù)量就是分配這些矩陣所需要的最少片上存儲器塊數(shù)。首先把矩陣數(shù)最多的最大組中的各個矩陣分配到不同的存儲器塊中，然后按照B類約束矩陣組中矩陣數(shù)從多到少的順序分配這個組中尚未分配的矩陣，對于具有相同矩陣數(shù)的組，先分配未分配矩陣較少的B類約束矩陣組中的矩陣。若B類約束的矩陣同時存在C類限制，則分配到DARAM上，否則優(yōu)先分配到SARAM上；若SARAM上沒有足夠的空間，再分配到DARAM上。最后在DARAM上分配C類約束條件中的尚未分配的矩陣。

總    結(jié)

上述數(shù)據(jù)存儲器的分配方法只考慮了TMS320C55x中數(shù)據(jù)分配的主要方面，還有一些因素文中尚未涉及，如長整型數(shù)據(jù)的分配就必需考慮數(shù)據(jù)存儲器地址的對齊問題，這時數(shù)據(jù)分配的求解變得更加復雜。可以將矩陣短整型的個數(shù)規(guī)定為偶數(shù)，以簡化對齊問題，所以上述求解方法仍具有普遍的實用意義。