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

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

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

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

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

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

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

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

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

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

總 結

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