Memory Access Utilizing Indirect Memory Addressing Operations

为了实现最近的应用程序的高计算性能，不仅有效地使用硬件资源，如算术单元和寄存器，而且有效地访问大的存储器空间是非常重要的。在许多寻址模式中，我们有间接寻址模式，它通过称为“地址寄存器（AR）”的专用寄存器指向访问地址。通常，允许在一个指令周期中与算术运算一起执行简单的AR更新操作，例如AR*1。这种间接寻址方式易于实现，硬件成本很低，对于实现顺序数组访问等特定的存储器访问具有很大的优势，假设用通用语言编写的程序的所有存储器访问都采用这种间接寻址方式，现有的编译技术生成的目标代码往往包含大量的与存储器访问有关的开销。在这个研究项目中， 关于我们 在假定采用寻址方式的情况下，讨论了各种降低内存访问开销的代码优化方法。在前面的方法中，假设使用AR*1操作进行间接寻址。该方法用图表示法或存取图（简称AG）表示给定的存储器存取，然后基于线图提取算法确定给定程序中变量的有效存储器分配以及每次存储器存取的有效AR分配。本项目在扩展的间接寻址模型的基础上，提出了一种新的启发式代码优化算法，即增加AR *2更新操作的间接寻址算法。由于三角形图及其链式结构（链式三角形图CTG）可以提供有效的存储器地址分配，因此提出了基于从AG中提取CTG的存储器分配方法。该方法被扩展为使用AR*1、AR*2、.的间接寻址。AR*k更新操作。该方法基于从AG中提取链团图（Chained Clique Graph，CCG），并将其应用于编译器中，得到了有效的地址分配。其次，在间接寻址中引入模AR更新操作，如AR* 1MOD 4。一类AG适合于这种新的寻址模型，并提出了一种基于提取这种特定形状的图（链方图CSG）的内存分配方法。地址分配实例证明了该方法的有效性，上述方法只需要一个内存访问序列，即程序中的变量序列，因而适用于各种编译器。少

In order to achieve high computational performance for recent applications, not only effective use of hardware resources such as arithmetic units and registers, but also efficient access of large memory space is very important. In many of addressing modes, we have indirect addressing mode, which points an access address by the dedicated register called "Address Register (AR)". Usually, simple AR update operations such as AR*1 are allowed to execute together with arithmetic operations in one instruction cycle. Such indirect addressing can be easily implemented at very low hardware cost, and has much advantage to realize a certain memory access such as sequencial array access and so on. Suppose we use this indirect addressing for all the memory access of a given program written in a general purpose language, object code generated by available compiler techniques often includes huge number of overhead concerned with memory access. In this research project, a processor only of indirect mem … More ory addressing mode is assumed, various code optimization methods to reduce memory access overhead are discussed. In the previous method, indirect addressing with AR*1 operations is assumed. The method represents a given memory access by a graph notation or an access graph (AG in short), and then, based on the line graph extraction algorithm, determines an efficient memory allocation of variables in a given program together with an efficient AR assignment for every memory access. In this project, extended indirect addressing models with additional AR operations are assumed, and new heuristic algorithms for code optimization are investigated.At first, an indirect addressing with additional AR *2 update operations is introduced. Since a triangle shaped graph and its chain structure (Chained Triangle Graph CTG) give efficient memory address allocations, the memory allocation method based on the CTG extraction from an AG is proposed. This method is extended for indirect addressing with AR*1, AR*2, ..., AR*k update operations. The method is based on the Chained Clique Graph (CCG) extraction from an AG.The proposed methods are applied to the compiler, and efficient address allocations are derived for several examples.Second, modulo AR update operations, such as AR*1MOD4, are newly considered in indirect addressing. A class of AG suitable for this new addressing model is shown, and a memory allocation method based on extraction of this specific shaped graph (Chained Square Graph CSG) is proposed. From address allocation examples, the method is proved to be effective.All the methods presented above just require a memory access sequence, i.e. a sequence of variables in a given program, so that they are applicable for various compilers. Less