面向计算机体系结构的程序优化.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * j = 0, 1, … , n ?1 i = 0 X Y 矩阵乘算法的优化 复用在缓存而不是内存的数据，则数据局部性好 矩阵乘算法及其优化 改变数据布局和语句执行次序都可能改进缓存行的复用 * j = 0, 1, … , n ?1 i = 0 X Y 矩阵乘算法的优化 复用在缓存而不是内存的数据，则数据局部性好 矩阵乘算法及其优化 分块计算是重排循环中迭代次序的较好方法 能极大地改进程序的局部性 * 分块计算的示意图 1. X和Y的灰色部分进行乘加运 算，可得到Z的灰色部分的结果 2. X和Y的灰色部分分别由若干 行和若干列构成 3. 对X和Y进行分块，通过增加 循环来分块计算 b n 矩阵乘算法及其优化 X: Y: Z: * 分块计算的示意图 1. X和Y的灰色部分进行乘加运 算，可得到Z的灰色部分的结果 2. X和Y的灰色部分分别由若干 行和若干列构成 3. 对X和Y进行分块，通过增加 循环来分块计算 b n 矩阵乘算法及其优化 X: Y: Z: * 分块计算的示意图 1. X和Y的灰色部分进行乘加运 算，可得到Z的灰色部分的结果 2. X和Y的灰色部分分别由若干 行和若干列构成 3. 对X和Y进行分块，通过增加 循环来分块计算 b n 矩阵乘算法及其优化 X: Y: Z: * 分块计算的示意图 1. X和Y的灰色部分进行乘加运 算，可得到Z的灰色部分的结果 2. X和Y的灰色部分分别由若干 行和若干列构成 3. 对X和Y进行分块，通过增加 循环来分块计算 b n 矩阵乘算法及其优化 X: Y: Z: * 矩阵乘算法的优化 仍假定n能由b整除, 假定Z的元素已经先行置初值 for (ii = 0; ii n; ii = ii + b) for (jj = 0; jj n; jj = jj + b) for (kk = 0; kk n; kk = kk + b) for (i = ii; i ii + b; i++) for (j = jj; j jj + b; j++) for (k = kk; k kk + b; k++) Z[i][j] = Z[i][j] + X[i][k] ? Y[k][j]; 矩阵乘算法及其优化 b n * 矩阵乘算法的优化 仍假定n能由b整除, 假定Z的元素已经先行置初值 前两行程序表示以块为单位进行矩阵乘 第3行程序表示n/b个X和Y的块相乘得到Z的一块的结果 for (ii = 0; ii n; ii = ii + b) for (jj = 0; jj n; jj = jj + b) for (kk = 0; kk n; kk = kk + b) for (i = ii; i ii + b; i++) for (j = jj; j jj + b; j++) for (k = kk; k kk + b; k++) Z[i][j] = Z[i][j] + X[i][k] ? Y[k][j]; 矩阵乘算法及其优化 b n * 矩阵乘算法的优化 仍假定n能由b整除, 假定Z的元素已经先行置初值 从第4到8行的程序计算左上角为X[ii][kk]和Y[kk] [jj]的两块对左上角为Z[ii][jj]的块的贡献 for (ii = 0; ii n; ii = ii + b) for (jj = 0; jj n; jj = jj + b) for (kk = 0; kk n; kk = kk + b) for (i = ii; i ii + b; i++) for (j = jj; j jj + b; j++) for (k = kk; k kk + b; k++) Z[i][j] = Z[i][j] + X[i][k] ? Y[k][j]; 矩阵乘算法及其优化 b n * 分块计算的示意图 从第4到8行的