多媒体应用的高级数据布局优化

### 多媒体应用的高级数据布局优化 #### 1. 引言与相关工作 处理器和内存速度之间的差距不断增大，促使人们设计具有深层内存层次结构的系统。大多数以数据为主的多媒体应用无法高效利用缓存，大部分时间都在等待内存访问。这不仅增加了平均内存访问时间，还意味着内存带宽、系统总线负载和相关功耗的显著额外成本。 我们主要针对嵌入式（并行）实时多媒体处理（RMP）应用领域，因为该领域的算法适合进行编译时分析。尽管嵌入式RMP应用相对规则，但在循环和索引表达式中并非完全线性或仿射，同时对大型工作集的复杂访问使得现有方法难以充分利用局部性。早期研究表明，图像处理和科学应用的大部分执行时间都花在缓存未命中导致的缓存停顿上，因此减少缓存未命中至关重要。 源级程序转换可以在很大程度上提高这些应用的缓存性能，但仍存在大量缓存未命中。存储顺序优化有助于减少容量未命中，但最终仍存在与次优数据布局相关的冲突缓存未命中。虽然之前提出了数组填充来减少冲突未命中，但现有方法无法消除大部分冲突未命中。此外，很少有研究衡量数据组织对缓存性能的影响，因此需要研究额外的数据布局或组织技术来减少缓存未命中。 数据从主内存映射到缓存的基本关系为： (块地址) MOD (缓存中的组数) 根据每组中的行数，我们定义了直接映射、n路组相联和全相联缓存。如果我们根据数据的生命周期和大小将其安排在主内存的特定块地址上，就可以控制数据到缓存的映射，从而在很大程度上消除关联性对数据映射的影响。但这需要在多个不同变量之间进行权衡，因此需要一种全局数据布局方法。我们提出了主内存数据布局组织（MDO）方法，这是一种新的形式化和自动化的内存高层数据组织优化方法，并将在实际应用中进行验证。 #### 2. 示例说明 下面通过一个示例简要介绍主内存数据布局组织（MDO）的基本原理。 考虑图1中的示例，图1(a)中的初始算法需要三个数组来执行完整程序。图1(b)中的初始主内存数据布局是单一连续的，与数组和缓存大小无关。对于直接映射缓存，初始算法在最坏情况下（即每个数组的初始地址都是缓存大小的倍数）可能会有3N个（交叉）冲突缓存未命中。为了消除所有冲突缓存未命中，三个数组不能映射到相同的缓存位置。 图1(c)中的MDO优化算法将完全没有（交叉）冲突缓存未命中。这是因为在MDO优化算法中，数组总是映射到缓存中固定且不重叠的位置，这得益于图1(d)所示的主内存数据存储方式。为了获得这种修改后的数据布局，需要执行以下步骤： 1. 将初始数组拆分为大小相等的子数组，每个子数组的大小称为瓦片大小。 2. 合并不同的数组，使它们的瓦片大小之和等于缓存大小。然后递归存储合并后的数组，直到所有相关数组都完全映射到主内存中。这样就得到了一个新数组，它包含所有数组，但组成数组的存储方式使得它们映射到缓存中时可以消除冲突未命中。这个新数组在图1(c)中用“x[]”表示。 在图1(c)和(d)中，有两个重要的观察结果： 1. 不同数组数据进行递归分配，每次递归的大小等于缓存大小。 2. 用于将修改后的数据布局施加到链接器的生成地址包含取模运算，这些运算可以在后续的单独优化阶段中移除。 ```plaintext Source code a ·- for(i=0;i<N ;i++) a[i] = b[i] + c[i] ; for(i=0;i<N ;i++) { } indexl = i%tsl + i/tsl * C + 0 ; index2 = i%ts2 + i/ts2 * C + 8; index3 = i%ts3 + i/ts3 * C + 16 ; x[indexl] = x[index2] + x[index3] ; b ·- Memory Data Layout I a[N] I b[N] I c[N] 0 N 2N f<--C-ac-he-+i+-C-ac-he-+< ts!····// ~aci; Size Size tsJ········· .... ...-·size (ts~ tilesize) ts 1 ~ ts2 ~ ts3 ~ 8 elements ts3 ``` | 项目 | 详情 | | ---- | ---- | | 初始算法 | 需要三个数组执行程序，初始数据布局单一连续，最坏情况有3N个冲突缓存未命中 | | MDO优化算法 | 无冲突缓存未命中，数组映射到固定且不重叠的缓存位置 | | 数据布局修改步骤 | 1. 拆分初始数组为子数组；2. 合并数组使瓦片大小之和等于缓存大小并递归存储 | #### 3. 主内存数据布局组织（MDO） ##### 3.1 一般问题 高效缓存利用的主内存数据布局组织问题（DOECU）可以表述为：“对于一个具有m个循环嵌套和n个变量（数组）的给定程序，获得一种数据布局，使其冲突未命中尽可能少”。这个问题有两个子问题： 1. **瓦片大小评估问题**：设$x_i$为数组i的瓦片大小，C为缓存大小。对于给定程序，需要求解以下m个方程以获得所需