Page 86 - 《软件学报》2024年第6期
P. 86
2662 软件学报 2024 年第 35 卷第 6 期
框架第一次调用算法 1 时的 region 初始划方法为: 不同的数组首先划分为不同的 region, 对于同 region 内的
多个数组访问, 若优化维以上的更高维的表达式不同, 则进一步划分为多个不同 region, 若相同, 则归入同一 region.
框架初始化参数取值如下:
∑
min(循环总迭代数× region_size,bu f_size)
block_len = ∑
region_size
.
max_block_len = 0
block_len
step_len =
2
求解算法中当循环总迭代数不是常量时置为无穷大, 编译器代码变换时会增加相应的判断代码避免循环分块
超过循环迭代总量.
4.4 编译器代码变换
在根据第 4.3 节中的算法计算出数组访问聚类分区方案以及循环分块大小后, 需要编译器对代码进行变换,
中间表示如图
主要是完成循环分块, 生成 DMA、RMA 操作及配套指令, 修改循环体中的访存操作等, 以及当有多次相邻 DMA、
RMA 操作时, 对回答字测试过程进行优化, 将多次相邻的回答字测试进行合并.
GCC 中循环结构的通用表示及代码变换过程如图 13 所示. 图 13(a) 中所示为 GCC 中循环结构的通用表示.
具体变换步骤如下.
for (V = N1; V cond N2; V += STEP) buffer = ldm_malloc();
BODY; trip = 0;
L0:
(a) GCC for 循环中间表示 s0 = trip * CHUNK;
e0 = min(s0 + CHUNK, n);
if (s0 < n) goto L1; else goto L4;
trip = 0; dma/rma_get(data[trip], buffer, reply);
L0: wait(reply);
s0 = trip * CHUNK; L1:
e0 = min(s0 + CHUNK, n); V = s0 * STEP + N1;
if (s0 < n) goto L1; else goto L4; e = e0 * STEP + N1;
L1: L2:
V = s0 * STEP + N1; BODY;
e = e0 * STEP + N1; Use(buffer);
L2: V += STEP;
BODY; if (V cond e) goto L2; else goto L3;
V += STEP; L3:
if (V cond e) goto L2; else goto L3; dma/rma_put(data[trip], buffer, reply);
L3: wait(reply);
trip += 1; trip += 1;
goto L0; goto L0;
L4: L4:
(b) 循环分块后的中间表示示意图 (c) 插入DMA/RMA 操作及修改循环体后的
中间表示示意图
图 13 代码变换过程示意图
Step 1. 进行循环分块变换, 生成的 GCC 13(b) 所示, CHUNK 为 4.3 中求解出的分块大小 block_len.
Step 2. 遍历 region, 对每一个 region 生成一次 DMA 或 RMA 操作. 具体生成 get 还是 put 操作, 需要根据变量
数据流分析结果和访问特征确定, 对于只读变量生成 get 操作, 对于向下暴露变量, 生成 put 操作. 先读后写变量,
既要在循环前生成 get 操作, 又要在循环后生成 put 操作.
Step 3. 修改循环体, 将原数组访问修改成对相应缓冲区数据的访问, 生成的 GCC 中间表示如图 13(c) 所示.
Step 4. 对边界条件进行处理. 循环迭代次数不能整除循环分块大小的情况: 对于 dma/rma _get 操作, 最后一个
循环块中多余 get 的数据不会影响程序结果; 对于 dma/rma_put 操作, 最后一个循环块中多余 put 的数据可能会冲