用于处理性能瓶颈的面向内存的优化技术

    内存是嵌入式系统的一个关键瓶颈。许多嵌入式计算应用程序花费大量时间访问内存。内存系统不仅是性能的主要决定因素，也是能耗的主要决定因素。
    内存系统优化可以针对内存层次结构的任何阶段。通用和嵌入式社区已经开发了多种技术来优化缓存性能。近，已开发出暂存器存储器的优化技术。优化还可以针对主存储器，特别是当它们被分区时。
    内存系统优化可以针对数据或指令。数组优化是一类重要的面向数据的优化。控制流分析带来了改进指令缓存行为的方法。全局内存分析在嵌入式系统中尤为重要。
    许多嵌入式系统由许多在它们之间传递数据的子系统组成。这些子系统之间的缓冲区必须仔细调整大小，以避免缓冲区溢出和内存浪费。
    循环转换
    一些优化是在编译早期应用的，无需详细了解目标硬件。此类转换试图公开可供后续阶段使用的并行性。循环是此类转换的主要候选者，因为它们可以为数据并行性提供重要的来源。
    循环变换在科学程序和优化编译器中的应用已经被研究了几十年。这里没有足够的篇幅来阐述这个主题；我们仅介绍一些概念来说明如何使用该工作主体。

    理想的循环可以完全并行执行。图 3-15左侧的代码 有一个循环体，其中所有数组仅由i索引。因此，循环迭代不依赖于任何其他迭代。因此，所有循环体可以以任何顺序并行执行，而不会影响结果。在图右侧的代码中，第i次 迭代取决于第i-1次 迭代的结果。

    图 3-15 循环中的并行性和约束
    在这种情况下，在i – 1也完成之前我们无法完成迭代 i ，因此这些循环体必须按照循环枚举的顺序完成。从一个循环迭代到另一循环迭代的数据依赖性称为循环携带依赖性
    编译器必须调度操作，以便它们不会违反数据依赖性，即代码在计算之前不会尝试使用值。一般来说，许多可能的调度都满足数据依赖性，只要我们有办法枚举这些依赖性。虽然单个循环可能提供一些机会，但循环嵌套提供了许多需要详细分析的并行可能性。

    如图 3-16所示，循环嵌套是一组循环，一个循环又一个循环。完美的循环嵌套在嵌套内没有条件。不完美的循环嵌套具有导致嵌套中的某些语句在某些情况下无法执行的条件。

    图 3-16：循环嵌套
    循环和循环嵌套具有许多数据依赖性——每次迭代中的每个操作都会生成自己的数据依赖性。然而，我们也知道循环提供了我们可以利用的结构和规律性。循环和循环嵌套的一些可能的转换包括：
    循环排列会更改嵌套中循环的顺序。
    索引重写改变了循环索引的表达方式。
    循环展开创建循环体的多个副本并适当地修改循环索引。
    循环拆分采用具有多个操作的循环，并为每个操作创建一个单独的循环；循环融合执行相反的操作。
    循环平铺将循环拆分为循环嵌套，每个内部循环处理一小块数据。
    循环填充将数据元素添加到数组中，以更改数组映射到内存系统结构的方式。
    多胞体模型 [1; 4]通常用于表示和操作循环嵌套中的数据依赖关系。
    内部循环体修改c的值，创建从c[i ][j ] 到c[i ][j + 1] 的数据依赖关系。我们将数组中的每个数据元素表示为二维空间中的节点，循环迭代变量形成空间的轴。这些节点在该空间中以三角形定义多面体。
    我们在描述c[i ][j ]和c[i ][j + 1]之间循环传递依赖关系的节点之间添加边。多胞体中的点完全描述了所有循环携带的依赖关系，但我们尚未降低该表示的复杂性。我们可以使用距离向量来描述一组向量的方向和距离。在这种情况下，所有数据依赖关系的形式都是[ij ] = [1 0]。执行此计算的任何循环集都必须满足这些循环携带的依赖性，但许多调度通常是可能的。我们可以应用一个排序向量来描述循环访问节点的顺序。
    我们可以使用矩阵代数来操纵循环的形式。例如，如果我们想要交换循环，将j 放在外循环中，将i 放在内循环中，我们可以将循环嵌套矩阵乘以交换矩阵，如下所示。
    这给出了循环嵌套
    for (j = 0; j < i ; j ++)
    for (i = 0; i < N; i ++)
    c [i + 1][ j ] = a[ i ][j ] *b[j];
    并非所有循环转换都是合法的。 Wolf 和 Lam [15] 表明，如果所有变换后的依赖向量按字典顺序都是正的，也就是说，如果它们在迭代空间中不向后指向，则循环变换是合法的。
    并非所有重要的循环变换都可以通过矩阵代数来操作。例如，循环平铺将一个大数组拆分为几个较小的数组，以更改数组元素的遍历顺序。这种变换不能用矩阵操作来表示，但是一旦循环被平铺，就可以使用矩阵方法来分析新的循环嵌套。
    循环置换和循环融合[16]可用于减少访问矩阵元素所需的时间。当循环排列用于将数组访问顺序更改为底层数据结构中使用的顺序时，可以减少延迟。多维数组由 C 以行优先格式存储，因此我们希望首先访问行。图 3-18 显示了循环排列的示例。
    循环融合允许组合和重用不同循环中对同一数组的引用。还可以修改数组元素的布局，以更改它们映射到高速缓存或并行内存系统的方式

    例如，转置矩阵是循环置换的替代方法。还可以填充循环以更改数据元素落入缓存行的方式。缓存性能的提高可能足以弥补浪费的内存。
    鉴于内存系统是系统功耗的主要贡献者，我们预计循环转换可能会损害或有助于程序的能耗。坎德米尔等人。 [9]通过使用SimplePower模拟几个基准程序的不同版本，研究了编译器转换对能耗的影响。
总结了他们的结果。他们在不同的基准上试验了不同类型的转换，并测量了未优化和优化代码的能耗，测试了每个程序实现的多种缓存配置。
    这些实验的一个有趣结果是，除了循环展开之外，大多数优化都会增加 CPU 内核的能耗。鉴于坎德米尔等人。在技术参数中，能耗的增加被内存系统能耗的减少所抵消，但不同的技术可能会导致此类转换的净能量损失。
    任何优化策略都必须平衡内存系统和的能耗。这些实验还表明，增加高速缓存大小和关联性确实会以增加高速缓存中的静态和动态能耗为代价。
    这些技术参数的存储系统其余部分的增益再次抵消了损失，但不同的技术可能会改变平衡。