嵌入式多媒体应用中的片上存储器分配

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中数据分配的主要方面，还有一些因素文中尚未涉及，如长整型数据的分配就必需考虑数据存储器地址的对齐问题，这时数据分配的求解变得更加复杂。可以将矩阵短整型的个数规定为偶数，以简化对齐问题，所以上述求解方法仍具有普遍的实用意义。