嵌入式多媒體應(yīng)用中的片上存儲(chǔ)器分配

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

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

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

（1） 取出其中一個(gè)B 類約束條件，不妨設(shè)為S2=（A1，A2），初始化其標(biāo)志為1。

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

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

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

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

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

總 結(jié)

上述數(shù)據(jù)存儲(chǔ)器的分配方法只考慮了TMS320C55x中數(shù)據(jù)分配的主要方面，還有一些因素文中尚未涉及，如長整型數(shù)據(jù)的分配就必需考慮數(shù)據(jù)存儲(chǔ)器地址的對(duì)齊問題，這時(shí)數(shù)據(jù)分配的求解變得更加復(fù)雜?？梢詫⒕仃嚩陶偷膫€(gè)數(shù)規(guī)定為偶數(shù)，以簡化對(duì)齊問題，所以上述求解方法仍具有普遍的實(shí)用意義。