矩阵相乘例子学习
pe-matrix使用python编写:
pe-py计算时间需要6小时
语言优化
- 使用Java编写需要46分钟
- 使用c编写需要19分钟
解析
- python是解析性语言,运行指令需要经过解析、执行,需要的时间也会越多
- Java是介于解析语言与编译语言之间,经过优化,Java会比python跑得更快
- C是之间运行字节码,因此速度最快
For Loop优化
原来的循环如下:
pe-for修改顺序为:
pe-for-opt性能表现如下:
pe-for-perf可见for的顺序不同,性能会有非常大的差异
分析:
-
CPU访问cache非常快
-
CPU访问内存非常慢
-
如果访问数据都在cache中,则缓存命中,否则不命中
-
CPU访问数据具有局部性,因此局部性的数据更容易放进cache中
-
下面分析下不同for的内存表现:
pe-for-an-opt
从上图可见,在内存访问的连续性来说,ikj会更优
可以通过命令查看程序的缓存命中率:
valgrind --tool=cachegrind ./mm
编译优化
pe-matrix-compiler并行优化
pe-matrix-pall运行时间为3s
缓存使用优化
- register: 1 cycle
- L1-cache: 4 cycles,
- L2-cache: 10 cycles,
- L3-cache: 50 cycles,
- DRAM: 150 cycles
如果内循环计算一行C
- 4096个数据吸入C
- 4096个数据从A读入
- 4096 * 4096 = 16, 777, 216 从B读入
而遗憾的是CPU L1缓存只有32k
这会导致在计算一个内循环,数据会不断的从内存读入,cache的缓存会不断的被刷走,导致运算低效
解决思路
通过减少内循环的计算量,从而减少数据被刷走的机率
pe-matrix-multi-2如上图,如果内循环只计算C 64 * 64
- 64 * 64 = 4096会写入C
- 64 * 4096 = 262, 144会从A读入
- 64 * 4096 = 262, 144会从C读入
- 总共需要访存 528, 384
可见通过减少计算C的维度,可以大大减少访存的数量
pe-matrix-multi-3pe-matrix-s-size
递归优化
还没看懂,先贴出来
pe-matrix-splitpe-matrix-split-time
SIMD编译优化
现代CPU不仅仅提供SISD,还会提供SIMD的指令操作
通过clang和llvm的编译优化 -march=native -ffast-math可以把某些指令并行化
优化后的时间为0.7s
下面看看例子总的优化对比
pe-matrix-perf代码简单优化技巧
数据结构
- 通过增加数据结构的字段,来加快访问速度
例如通过增加链表的尾指针,来加快访问链表结尾的速度
- 预计算
例如计算伯努利分布,可以通过先把结果在程序运行之前算出来,构造出一个数据表,那么在程序运行的时候就可以直接拿到结果了
-
缓存
通过把结果缓存起来,可以加快程序运行的速度,例如使用LRU算法或者redis之类的中间件
-
稀疏表示
例如一个稀疏矩阵,大部分数据都是零,而零乘以任何数都是零,是没用的计算,通过构造稀疏数据结构,既可以节省计算时间,也可以节省存储空间
例如CSR技术
pe-csr逻辑优化
-
常量计算
例如const double area = pi * 3
可以通过编译器,直接计算出结果,来减少运行时的开销
-
公共表达式共用
例如表达式a - b已经计算过一次了,那么d就可以直接取结果,来减少多一次的计算
-
使用更廉价的计算符
例如计算两个圆是否相交
计算开根号是复杂的
那么可以两边平方来优化
pe-square- 更快的返回
例如计算x和y的距离,来加快运算的返回
- if条件优化
例如' '是更常见的一个符号,则可以提前判断,来减少if的运算
循环优化
- 表达式运算外提
- 循环平铺
减少了循环判断和++操作
- 局部平铺
- 循环融合
函数优化
-
inline
-
减少尾递归
- 减少递归
二进制操作优化
pe-xpe-neg
-
设置k位
y = x | (1 << k)
-
清除k位
y = x & ~(1 << k)
-
反转k位
y = x ^ (1 << k)
-
取头字节
(x & mask) >> shift
-
交换两个整数
x = x ^ y; y = x ^ y; x = x ^ y;
-
取两数最小的一个
min = y ^ ((x ^ y) & -(x < y));
计算机体系结构
流水线增加吞吐量
pe-pipe-line乱序执行,解决流水线的冲突和冒险
pe-issue分支预测
pe-predit-ifCPU遇到跳转指令的时候,由于会出现两个分支的代码,而CPU不想等待判断结果出来,为了效率,而执行下一个指令,因此,CPU会预判一条路径执行下去,如果判断对了,则提高了效率,否则,CPU会把执行的中间结果清理,并执行对的分支
并行优化
pe-quick-sort- 快排的总工作量是 O(n log n)
- 最大的串行工作量 n + lg n = n
- 并行度 = n log n / n = log n
可见如果要再优化快排的并行度,需要把partition并行化
题外话:使用堆来实现栈的功能
- 当程序进入一个函数,会把部分寄存器的信息保存
- 把参数入栈
- 栈的指针下移
- 函数返回时,会恢复寄存器
- 栈指针上移
假设我要用堆连存储某个函数的栈的信息
- 可以new出一片足够大的区域
- 指针不下移,而是移动到堆的地址
- 函数返回时,不上移栈指针,而是从堆的地址切回到栈的地址
归并排序优化
pe-merge-sort- 总工作量:n log n
- 串行最大工作 n + log n
- 并行化:log n
问题出在merge的时间复杂度为n
通过二分并行处理merge:
pe-merge-binpe-merge-bin-code
可得:
串行时间:log n ^2
编译器优化
TBD
性能测量
pe-sort这式一个排序算法的测量时间分布图
发现图像会出现非常奇怪的抖动。
他的原因是CPU随着计算的时间,会呈现出发热,此时计算机为了降温,所以把CPU的始终频率调低,导致排序出现上面的图形
问题的调整
pe-question一般来说,要解决问题,必先发现问题
稳定的重现后,才可以比较容易的调整
最后把问题解决
测量时的问题
计算机的状态是不稳定的
- 无可预知的后台进程
- 中断
- 代码和数据的对齐
- CPU运行时的调度
- 超频
- 竞争
- 网络状态
- 磁盘访问和内存访问的错误和重试
测量工具
- gettimeofday
- gdb
- gprof
- perf
- cachegrind
测量结果
取最小值
访存优化
栈
- 申请和释放都是O(1)
堆
- 会引起内部碎片和外部碎片
- 大小不固定
- 多线程竞争
- 不同内存片位于不同的页表
管理
pe-single-heappe-multi-heap
pe-multi-heap-2
pe-heap
GC
- 通过智能指针
- 通过构造内存引用图,后台进程不断扫描,并清理没有引用的内存
网友评论