C中实现矩阵乘法的一种高效的方法

如何计算矩阵乘法，这个大家都知道。通常情况下，我们都是用以下代码实现的：


代码如下:

for(i=0;i<n;++i)
    for(j=0;j<n;++j){
        sum=0;
        for(k=0;k<n;++k)
            sum+=A[i][k]*B[k][j];
        C[i][j]+=sum;
}

但是考虑了高速缓存的问题后，其实有一种更好的实现方式：


代码如下:

for(i=0;i<n;++i)
    for(k=0;k<n;++k){
        r=A[i][k];
        for(j=0;j<n;++j)
            C[i][j]+=r*B[k][j];
}

细看一番就会发现这两种实现语义是等价的，但是后者的实际运行效率却比前者高。

那为什么会如此呢？

那是因为CPU读数据时，并不是直接访问内存，而是先查看缓存中是否有数据，有的话直接从缓存读取。而从缓存读取数据比从内存读数据快很多。

当数据不在缓存中时，CPU会将包含数据在内的一个数据块读到缓存，如果程序具有良好空间局部性，那么第一次cache miss后，之后的几次数据访问就可以直接在缓存中完成。除了空间局部性（程序倾向于引用与当前数据邻近的数据）之外，还有时间局部性（程序倾向于引用最近被引用过的数据）。

回到矩阵乘法。（我们只考虑内循环）

前者对矩阵A，有良好的空间局部性，假设一次能缓存四个元素，则每次迭代对于A只有0.25次miss，但是对于B，则不然，因此B是按列访问的，每次访问都会miss，因此每次迭代总的miss数是1.25。

后者对于矩阵C和矩阵B都有良好的局部性，每次迭代都只有0.25词miss，因此总的miss数是0.5。后者每次迭代多了一次存储（对C[i][j]写入），但是即便如此，后者的运行效率也比前者高。

总而言之，要想程序跑得快，就要在程序中多利用局部性，让缓存hold住你的数据，减少访存次数。要知道CPU可以在3个时钟周期内访问到L1 cache，10个时钟周期左右的时间访问到L2 cache。访问内存却要上百个时钟周期，孰快孰慢，很清楚了吧？

赞 (0)

相关推荐

  • 重构-C++实现矩阵的简单实例

    重构-C++实现矩阵的简单实例 #include <iostream> #include <cmath> using namespace std; double cofactor(double* detPtr,int rank,int t); //代数余子式 double valDet( double *detPtr, int rank); //行列式 template <class T> void exchange(T& t1,T& t2){T tem

  • Javascript图像处理—为矩阵添加常用方法

    前言 上一篇文章,我们定义了矩阵,这篇文章我们来给矩阵添加一些常用方法. toString方法 toString方法通常用作将对象转成字符串描述,所以我们将这一方法定义为输出矩阵元素. 复制代码 代码如下: Mat.prototype.toString = function(){ var tempData = this.data, text = "Mat("+ this.type +") = {\n", num = this.col * this.channel;

  • 利用C++实现矩阵的相加/相称/转置/求鞍点

    利用C++实现矩阵的相加/相称/转置/求鞍点

    1.矩阵相加 两个同型矩阵做加法,就是对应的元素相加. 复制代码 代码如下: #include<iostream>using namespace std;int main(){ int a[3][3]={{1,2,3},{6,5,4},{4,3,2}}; int b[3][3]={{4,3,2},{6,5,4},{1,2,3}}; int c[3][3]={0,0,0,0,0,0,0,0,0}; int i,j; cout<<"Array A:"<<

  • C语言解决螺旋矩阵算法问题的代码示例

    C语言解决螺旋矩阵算法问题的代码示例

    赶集网校招就采用了螺旋输出矩阵作为程序题,要求将矩阵螺旋输出如: 图中6*6矩阵线条所示为输出顺序,如果输出正确的话应该输出1~36有序数字.  我想的是这么做的: #include <stdio.h> //#define LEN 1 //#define LEN 2 //#define LEN 3 #define LEN 4 void printClock(int a[][LEN]){//输出函数 int t; int i = 0, m = 0; int j = LEN, n = LEN; w

  • C语言实现稀疏矩阵

    C语言实现稀疏矩阵

    本文实例为大家分享了C语言实现稀疏矩阵的具体代码,供大家参考,具体内容如下 #include "stdio.h" #define maxsize 10 typedef struct { int i,j; //非零元素的行.列 int v; //非零元素的值 }Triple; typedef struct { Triple data[maxsize]; int m,n; //矩阵的行.列 }TSMarix; InitTriple(TSMarix *M) { int i,j,k,v,t;

  • C++实现:螺旋矩阵的实例代码

    C++实现:螺旋矩阵的实例代码

    通过观察发现矩阵的下标有这样一个规律:a行递增后b列递增然后c行递减再d列递减,但是对应值却是逐渐增加的.因此可用4个循环实现,需要注意的是在赋值时不要把之前的值覆盖了.所以在这里选择相同顔色部分赋值,代码如下: 复制代码 代码如下: #include <iostream>#include <iomanip> using namespace std; // 输出螺旋矩阵void Matrix(){    const int size = 10; // 矩阵大小    int mat

  • C++实现矩阵原地转置算法

    C++实现矩阵原地转置算法

    本文实例描述了C++实现矩阵原地转置算法,是一个非常经典的算法,相信对于学习C++算法的朋友有很大的帮助.具体如下: 一.问题描述 微软面试题:将一个MxN的矩阵存储在一个一维数组中,编程实现矩阵的转置. 要求:空间复杂度为O(1) 二.思路分析 下面以一个4x2的矩阵A={1,2,3,4,5,6,7,8}进行分析,转置过程如下图: 图中右下角的红色数字表示在一维数组中的下标.矩阵的转置其实就是数组中元素的移动,具体的移动过程如下图: 我们发现,这些移动的元素的下标是一个个环,下标1的元素移动到

  • C++实现图的邻接矩阵存储和广度、深度优先遍历实例分析

    C++实现图的邻接矩阵存储和广度、深度优先遍历实例分析

    本文实例讲述了C++实现图的邻接矩阵存储和广度.深度优先遍历的方法.分享给大家供大家参考.具体如下: 示例:建立如图所示的无向图 由上图知,该图有5个顶点,分别为a,b,c,d,e,有6条边. 示例输入(按照这个格式输入): 5 6 abcde 0 1 1 0 2 1 0 3 1 2 3 1 2 4 1 1 4 1 输入结束(此行不必输入) 注:0 1 1表示该图的第0个顶点和第1个定点有边相连,如上图中的a->b所示       0 2 1表示该图的第0个顶点和第2个定点有边相连,如上图中的a

  • C语言 经典题目螺旋矩阵 实例详解

    C语言 经典题目螺旋矩阵 实例详解

    C语言 经典题目螺旋矩阵 //N阶螺旋矩阵 #include <stdio.h> #include <stdlib.h> int main() { int N,i,j,n,num=1; int a[10][10]={0}; printf("输入你要输出的几阶中断:"); scanf("%d",&N); for(n=0;n<=N/2;n++) { for(j=n;j<=N-n-1;j++) a[n][j]=num++; fo

  • C语言科学计算入门之矩阵乘法的相关计算

    C语言科学计算入门之矩阵乘法的相关计算

    1.矩阵相乘 矩阵相乘应满足的条件: (1) 矩阵A的列数必须等于矩阵B的行数,矩阵A与矩阵B才能相乘: (2) 矩阵C的行数等于矩阵A的行数,矩阵C的列数等于矩阵B的列数: (3) 矩阵C中第i行第j列的元素等于矩阵A的第i行元素与矩阵B的第j列元素对应乘积之和,即 如: 则: 2. 常用矩阵相乘算法     用A的第i行分别和B的第j列的各个元素相乘求和,求得C的第i行j列的元素,这种算法中,B的访问是按列进行访问的,代码如下: void arymul(int a[4][5], int b[

  • C/C++实现矩阵的转置(示例代码)

    废话不多说,直接上代码 复制代码 代码如下: #include <iostream>using namespace std; const int N = 5; int matrix[5][5] ={    1,2,3,4,5,    1,2,3,4,5,    1,2,3,4,5,    1,2,3,4,5,    1,2,3,4,5}; void swap(int &a,int &b){    a=a^b;    b=a^b;    a=a^b;}void matrix_tr

随机推荐