?CS:APP3e, Bryant and O'Hallaron?可以參考這里

void bijk(array A, array B, array C, int n, int bsize) {int i, j, k, kk, jj;double sum;int en = bsize*(n/bsize);for (i = 0; i < n; i++)for (j = 0; j < n; j++)C[i][j] = 0.0;for (kk = 0; kk < en; kk += bsize) {for (jj = 0; jj < en; jj += bsize) {for (i = 0; i < n; i++) {for (j = jj; j < jj + bsize; j++) {sum = C[i][j];for (k = kk; k < kk + bsize; k++) {sum += A[i][k] * B[k][j];}C[i][j] = sum;}}}}
}

先來談一下參考資料內bijk函數中的blocking技術吧,和題目的兩層嵌套循環不同, bijk函數是五層的嵌套 作為人類似乎很難去理解為啥我就處理個矩陣,要整它五層嵌套,完了它還對性能有好處.

你想象一下transpose函數中如果dim=9999999999999...時,這世界不會存在一個cache能存下這個數組,假設此時cache就只有bsize*bsize(bsize<dim)大小,寫完一列bsize個dst后就開始寫下一列dst這樣只有第一列是不命中的,其他bsize-1列都是命中的.

for (k = kk; k < kk + bsize; k++)

bijk函數中 k<kk+bsize就是控制程序寫完一個bsize 后就開始寫下一列.

這就是blocking技術的核心了.

我們現在開始改transpose函數:

#include <stdio.h>void transpose(int *dst, int *src, int n, int bsize) {  // n為數組大小（假設是方陣的邊長）, bsize為塊大小, bsize宜接近高速緩存大小  int i, j, kk, jj;  // 處理能夠完整被塊大小分割的部分  for (kk = 0; kk < n; kk += bsize) { // 注意這里應該使用n而不是en  for (jj = 0; jj < n; jj += bsize) { // 同上  for (i = kk; i < kk + (kk + bsize < n ? bsize : n - kk); i++) { // 確保不越界  for (j = jj; j < jj + (jj + bsize < n ? bsize : n - jj); j++) { // 確保不越界  // 計算一維數組中的索引  int src_index = i * n + j;  int dst_index = j * n + i;  dst[dst_index] = src[src_index]; // 復制元素}  }  }  }  
}int main() {int dim=500;int src[dim][dim];int dst[dim][dim];int i, j;
//給數組賦值for (i = 0; i < dim; i++)for (j = 0; j < dim; j++)src[i][j] = i+j;
//轉置transpose(dst,src,dim,500);
//檢查轉置后的結果for (i = 0; i < dim; i++)for (j = 0; j < dim; j++){if(src[i][j]!=dst[j][i])printf("轉置出錯\n");}return 0;
}