广义数据变换：优化嵌入式应用数据缓存性能
1. 引言
在许多数组密集型嵌入式应用中，冲突缺失在总数据缓存缺失中占比显著。以7个图像和视频处理嵌入式应用为例，在8KB直接映射数据缓存的情况下，冲突缺失平均占总缓存缺失的42.2%，部分应用中冲突缺失占比超50%。冲突缺失具有重复性，且嵌入式系统数据缓存关联性小，这都导致冲突缺失数量增多。
减少冲突缺失的常用技术是数组填充，它有两种主要形式：
-数组内填充：通过增加数组的列或行来避免数组不同列（或行）在数据缓存中冲突。例如，将数组声明A(N, M)修改为A(N, M + k)。
-数组间填充：在两个连续数组声明间插入虚拟数组声明，防止数组间潜在的冲突缺失。例如，将声明序列A(N, M), B(N, M)转换为A(N, M), D(k), B(N, M)。
然而，数组填充会增加数据空间大小，这在嵌入式环境中可能无法接受。实验表明，数组填充平均可使执行时间减少10.3%，但数据空间需求平均增加15.1%。且大部分冲突缺失（平均92.1%）来自数组间冲突。因此，一种能减少数组间冲突缺失且不增加数据空间需求的技术在嵌入式环境中很有必要。
本文提出一种基于编译器的数据变换策略——广义数据变换，它将同时使用的数组映射到一个公共数组空间，使原执行中依次访问的元素在新数组空间中连续存储，从而显著减少数组间冲突缺失。
2. 假设与背景
考虑嵌套循环中具有仿射下标函数的数组引用。对于一个n层嵌套循环中对m维数组的引用，可用迭代向量表示，每个数组引用可表示为，其中m × n矩阵X为引用矩阵，
