CPU无法达到peak performance的原因矩阵乘法的讨论介绍理论基础块状矩阵计算优化技巧代价模型strength reduction内联函数inline f循环展开loop unrolling去掉下标计算sub-exPRession eliminate查表look up table合并循环减少条件判断

转载请注明出处：http://blog.csdn.net/c602273091/article/details/54851077

上一节说到的是OpenMP的写法，这一次主要是介绍代码优化。

CPU无法达到peak performance的原因

本来CPU的性能应该如上图所示的，但是实际使用的时候并没有达到这个效果。

主要是因为：

存储器的层次设计。发生cache、TLB miss的时候，就需要等待很多个周期；

流水线、ILP等等并行设计有缺陷，使得吞吐量无法达到预期；

有的操作比如存储操作看似不需要浪费周期，其实数据传输等等会浪费不少周期。

矩阵乘法的讨论

介绍

原始的矩阵乘法就如上图的实现。

但是使用加速之后效果怎么样呢？ATLAS做加速的效果远远超过了三个循环的矩阵计算。

理论基础

在这里需要介绍一些存储器方面的知识。

矩阵存储分为行优先和列优先的。行列优先的不同使得每次存入cache的一行是列方向或者是行方向。

现在解构一下取数据的关系：

对存储数组A、B、C计算读取次数。

块状矩阵计算

使用块状计算矩阵，如下图。那么之前计算矩阵就改成了四个循环。

想对这块更了解，可以看我之前写的18-600里cache的介绍。 想直观看这个算法，可以看：

优化技巧

代价模型

计算代价的部分如下图：（左边是具体每部分、右边是具体例子）

计算一开始的代价：19n

去掉结构体，去掉了索引这个步骤：6n

改变循环体内部可以移出的操作：5n

使用循环展开：3.5n

strength reduction

减少需要浪费很多资源的操作，比如去掉除法、log等等或者替换成别的操作。

内联函数（inline f）

减少函数调用，把简单函数改成内联函数。

循环展开（loop unrolling）

这里主要是涉及CPU在取内存中数据到寄存器的时候，循环展开可以减少CPU周期。

去掉下标计算（sub-expression eliminate）

有时候计算循环中的下表很浪费CPU周期，一部分放到循环外就可以加快速度。

查表（look up table）

提前计算好要用到的一些数据，尤其减少循环多次计算的浪费。这个做法和暴力破解很像。

合并循环

减少循环次数，可以减少不少计数器的操作。

减少条件判断

减少循环中的条件判断，如果你提前知道哪个是需要跳过的。