Memory-hierarchy management
Memory-hierarchy management
复制标题
内存层次管理
DOI：
--
复制
发表时间：
1993
期刊：
影响因子：
--
通讯作者：
S. Carr
中科院分区：
文献类型：
--
作者：
S. Carr
高性能微处理器设计的趋势是增加芯片上的计算能力。微处理器现在可以处理显着更多的数据，每个机器周期比以前的模式。不幸的是，内存速度没有跟上步伐。结果是计算速度和存储器速度之间的不平衡。这种不平衡导致机器设计人员使用更复杂的内存层次结构。反过来，程序员明确地重新构造代码，以便在特定的内存系统上运行良好，从而产生特定于机器的程序。
我们认为，特定于机器的编程是朝着错误方向迈出的一步。应该由编程人员而不是程序员来处理特定于机器的实现细节。为此，本论文开发和实验的编译器算法，管理内存层次的机器浮点密集型数字代码。具体而言，我们处理以下问题：
标量替换。在标准数据流分析中，由于缺乏有关数组值流的信息，因此无法捕获寄存器中的数组重用。我们开发并实验了一种技术，在条件控制流的存在下执行标量替换，以将数组重用暴露给标准数据流算法。
打开并卡住。许多循环在每个循环中需要的数据比目标计算机能够处理的数据多。我们提出并实验了一种自动的技术来应用展开和果酱这样的循环，以减少其内存需求。
环形交叉口。在高级微处理器上运行的程序中，高速缓存局部性对性能至关重要。我们开发和实验的技术，以达到良好的缓存局部性的嵌套内的顺序循环。
阻挡。迭代空间分块是一种用于在缓存内获得时间局部性的技术。虽然它已被应用于“简单”内核，但还没有调查其在一系列算法风格上的适用性。我们将展示如何应用块循环梯形，菱形，三角形的迭代空间。此外，我们展示了如何克服某些复杂的依赖模式。
上述技术的实验表明，在单个芯片上的整数倍加速是可能的。这些结果表明，许多数值算法可以表示在一个自然的，独立于机器的形式，同时保持良好的内存性能，通过使用编译器优化。
The trend in high-performance microprocessor design is toward increasing computational power on the chip. Microprocessors can now process dramatically more data per machine cycle than previous models. Unfortunately, memory speeds have not kept pace. The result is an imbalance between computation speed and memory speed. This imbalance is leading machine designers to use more complicated memory hierarchies. In turn, programmers are explicitly restructuring codes to perform well on particular memory systems, leading to machine-specific programs.
It is our belief that machine-specific programming is a step in the wrong direction. Compilers, not programmers, should handle machine-specific implementation details. To this end, this thesis develops and experiments with compiler algorithms that manage the memory hierarchy of a machine for floating-point intensive numerical codes. Specifically, we address the following issues:
Scalar replacement. Lack of information concerning the flow of array values in standard data-flow analysis prevents the capturing of array reuse in registers. We develop and experiment with a technique to perform scalar replacement in the presence of conditional-control flow to expose array reuse to standard data-flow algorithms.
Unroll-and-jam. Many loops require more data per cycle than can be processed by the target machine. We present and experiment with an automatic technique to apply unroll-and-jam to such loops to reduce their memory requirements.
Loop interchange. Cache locality in programs run on advanced microprocessors is critical to performance. We develop and experiment with a technique to order loops within a nest to attain good cache locality.
Blocking. Iteration-space blocking is a technique used to attain temporal locality within cache. Although it has been applied to "simple" kernels, there has been no investigation into its applicability over a range of algorithmic styles. We show how to apply blocking to loops with trapezoidal-, rhomboidal-, and triangular-shaped iteration spaces. In addition, we show how to overcome certain complex dependence patterns.
Experiments with the above techniques have shown that integer-factor speedups on a single chip are possible. These results reveal that many numerical algorithms can be expressed in a natural, machine-independent form while retaining good memory performance through the use of compiler optimizations.