软件流水中的一种数据分配算法

An Algorithm to Data Allocation in Software Pipeling

数据元素的存储器分配是指令级并行优化编译过程中不可回避的一个关键性问题．该问题解决得好坏直接关系到编译优化的效率．本文第１节主要介绍ＩＬＳＰ（ｉｎｔｅｒｌａｃｅｄｉｎｎｅｒａｎｄｏｕｔｅｒｌｏｏｐｓｏｆｔｗａｒｅｐｉｐｅｌｉｎｉｎｇ）算法的基本思想．第２节以距阵乘法为例阐述了在ＩＬＳＰ算法下多重循环中数据元素的存取特点．第３节则从理论上对该特点进行了深入的分析研究，同时就一般多重循环给出了一个行之有效的ＩＬＳＰ算法下数据元素内存分配算法．第４节给出一个实验比较结果．

In the optimizing compilation process of instruction level parallelism, the memory allocation of data elements is an unavoidable key problem, which has a direct effect on the efficiency of the final results of optimizing compilation. In this paper, the first part briefly presents the background of the paper. Part 1 is the principles of a brand new software pipelining algorithm—ILSP(interlaced inner and outer loop software pipelining). In part 2, taking the example of matrix multiplication, the authors expound the characteristic of data accessing under ILSP algorithm, and make a deep theoretical analysis on that characteristic and conclude a general algorithm on memory allocation of data elements in the nested loops. The experiment is presented in part 4. And part 5, the conclusion.