天空 Blond - 体系结构
type: channel
link: https://skyblond.info/tag/%E4%BD%93%E7%B3%BB%E7%BB%93%E6%9E%84/
items: 【代码札记】基于Cache的矩阵乘积算法性能改进

【代码札记】基于Cache的矩阵乘积算法性能改进
type: item
date: 2020-12-11T19:52:00+08:00
description: 标题挺唬人，其实没啥。可就这么一点小东西，让我三年来第一次体会到大学的价值，与正经程序员的专业所在。背景今天看了看体系结构课程的实验，之前这门课上的都是一些理论课，内容就跟计算机组成原理差不多，又是选修课，老师凑活着讲，我凑活着听。其中第二个实验是「基于Cache的矩阵乘积算法性能改进」。看了看实验要求，就是写一个矩阵乘法的代码，一种是行列相乘累加，另一种则是要先计算转置矩阵，然后利用转置矩阵计算乘法，本质上还是行列相乘累加，而且还额外多了一个求转置。一个三层循环（行列遍历、相乘累加）优化成了一个两层循环（行列遍历求转置）加一个三层循环（行列遍历、相乘累加），不论怎么看都像是负优化，怎么可能快呢。估计是我理解错了，遂去谷歌。结果结果我真是万没想到，还真是这样的，不光代码是这样，结果也是有优化的。我在WSL2里面使用GCC 8.3.0编译如下代码：#include <time.h> #include <stdio.h> #include <stdlib.h> int matrix_size = 200; int optimized = 1; int main() { // 定义变量 float *a,*b,*c; long int i,j,k,size,m; double duration; clock_t start, finish; size=matrix_size; m=size*size; a=(float*)malloc(sizeof(float)*m); b=(float*)malloc(sizeof(float)*m); c=(float*)malloc(sizeof(float)*m); // 初始化 for(i=0;i<size;i++) for(j=0;j<size;j++) { a[i*size+j]=(float)(rand()%1000/100.0); b[i*size+j]=(float)(rand()%1000/100.0); c[i*size+j]=(float)(rand()%1000/100.0); } // 开始计时 start = clock(); // 运算 if (optimized) { // 计算转置 for(i=0;i<size;i++) for(j=0;j<size;j++) { b[i * size + j] = c[ j * size + i]; } // 计算 for(i = 0;i < size;i++) for(j=0;j<size;j++) { c[i*size+j]=0; for(k=0;k<size;k++) c[i*size+j]+=a[i*size+k]*b[j*size+k]; } } else { for(i=0;i<size;i++) for(j=0;j<size;j++) { c[i*size+j] = 0; for(k=0;k<size;k++) c[i*size+j]+=a[i*size+k]*b[k*size+j]; } } // 停止计时 finish = clock(); // 计算用时 duration = (double)(finish - start) / CLOCKS_PER_SEC; printf( "%fms\n", duration * 1000); return 0; }调整matrix_size和optimized，得出了以下数据：矩阵大小未优化耗时(ms)优化耗时(ms)加速比20044.02335.9861.223500698.498545.8911.28010007554.3174364.0171.731150032430.60214646.7102.214200077378.99835082.5802.2062500204543.49767557.6533.0283000343537.171116164.1932.957好家伙，我这波直接好家伙，WSL2的单核性能太差了！（不对好家伙，我这波直接好家伙，优化前后差距太大了！后来我又用Java试了一下（Java11 AdoptOpenJDK HotSpot ）：package demo.structure; import java.util.Random; public class Main { public static final int matrix_size = 3000; public static final boolean optimized = true; public static void main(String[] args) { double[] a = new double[matrix_size * matrix_size]; double…