计算矩阵A和B的乘法，其基本代码是

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

但这样的代码却存在以下的问题：
1、局部性较差
由于B是按列访问的，所以其局部性较差
2、不能保证A[i]始终在缓存中
内层循环的执行可能导致A[i]被缓存置换策略淘汰。

在单CPU上进行优化

在GPU上进行优化

并行算法

分块矩阵

很多并行算法都和分块矩阵有关，这是因为分块矩阵有非常好的性质。

简单地说，我们可以把分块矩阵当成矩阵中的元素一样相乘，然后把原矩阵带回即可。

信息传输

在节点间传输信息的时间可以使用下面的式子描述
$$
T_{msg} = t_s + t_w L
$$
其中$t_s$是startup time或者latency，也就是传输一条长度为0的信息所需要的时间。$t_w$是每多发送一个单词所额外需要的时间那么$1/t_w$就是单位时间的带宽（按单词计算），$L$是消息中的所有单词。对于大多数分布式系统来说，$t_s$是相当大的。

Cannon算法

Cannon算法是一个经典的2D算法。
Cannon算法是对方阵而言的，我们将矩阵A和B分为p个方块，则每个方块的边长是n / sqrt(p)。这个值必须要是能整除的，因而存在不少限制。
对应的，我们有p个处理器来计算这p个分块，处理器P[i, j]计算分块C[i]=A[i]*B[i]。在计算时，Cannon主要采用了称为”Shift and multiply”的思想。
以下图为例，在计算C[0, 0]时，可以不停地将A的框往左移动，B的框往上移动，然后原位相加。