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

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

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

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

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

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

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

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

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

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

總 結

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