深入理解计算机系统 CSAPP 家庭作业6.45 - wpsshop博客
devbox
IT小白
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

深入理解计算机系统 CSAPP 家庭作业6.45

作者：IT小白 | 2024-06-26 00:06:59

赞

踩

深入理解计算机系统 CSAPP 家庭作业6.45

 CS:APP3e, Bryant and O'Hallaron 可以参考这里

  1. void bijk(array A, array B, array C, int n, int bsize) {
  2. 	int i, j, k, kk, jj;
  3. 	double sum;
  4. 	int en = bsize*(n/bsize);
  5. 	for (i = 0; i < n; i++)
  6. 		for (j = 0; j < n; j++)
  7. 			C[i][j] = 0.0;
  8.  
  9. 	for (kk = 0; kk < en; kk += bsize) {
  10. 		for (jj = 0; jj < en; jj += bsize) {
  11. 			for (i = 0; i < n; i++) {
  12. 				for (j = jj; j < jj + bsize; j++) {
  13. 					sum = C[i][j];
  14. 					for (k = kk; k < kk + bsize; k++) {
  15. 						sum += A[i][k] * B[k][j];
  16. 					}
  17. 					C[i][j] = sum;
  18. 				}
  19. 			}
  20. 		}
  21. 	}
  22. }

先来谈一下参考资料内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函数:

  1. #include <stdio.h>
  2.  
  3.  
  4.  
  5. void transpose(int *dst, int *src, int n, int bsize) {  
  6. 	// n为数组大小（假设是方阵的边长）, bsize为块大小, bsize宜接近高速缓存大小  
  7. 	int i, j, kk, jj;  
  8. 	// 处理能够完整被块大小分割的部分  
  9. 	for (kk = 0; kk < n; kk += bsize) { // 注意这里应该使用n而不是en  
  10. 		for (jj = 0; jj < n; jj += bsize) { // 同上  
  11. 			for (i = kk; i < kk + (kk + bsize < n ? bsize : n - kk); i++) { // 确保不越界  
  12. 				for (j = jj; j < jj + (jj + bsize < n ? bsize : n - jj); j++) { // 确保不越界  
  13. 					// 计算一维数组中的索引  
  14. 					int src_index = i * n + j;  
  15. 					int dst_index = j * n + i;  
  16. 					dst[dst_index] = src[src_index]; // 复制元素
  17. 				}  
  18. 			}  
  19. 		}  
  20. 	}  
  21. }
  22.  
  23. int main() {
  24. 	int dim=500;
  25. 	int src[dim][dim];
  26. 	int dst[dim][dim];
  27. 	int i, j;
  28. //给数组赋值
  29. 	for (i = 0; i < dim; i++)
  30. 		for (j = 0; j < dim; j++)
  31. 			src[i][j] = i+j;
  32. //转置
  33. 	transpose(dst,src,dim,500);
  34. //检查转置后的结果
  35. 	for (i = 0; i < dim; i++)
  36. 		for (j = 0; j < dim; j++){
  37. 			if(src[i][j]!=dst[j][i])
  38. 				printf("转置出错\n");
  39. 			}
  40.  
  41. 	return 0;
  42. }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/IT小白/article/detail/757827
推荐阅读
相关标签