济南做网站需要多少钱,宿州市埇桥建设规划局网站,网站维护与建设合同书,申请域名费用系列文章#xff1a; 操作系统详解(1)——操作系统的作用 操作系统详解(2)——异常处理(Exception) 操作系统详解(3)——进程、并发和并行 操作系统详解(4)——进程控制(fork, waitpid, sleep, execve) 操作系统详解(5)——信号(Signal) 文章目录 一些概念CPE 初步优化消除不必…系列文章 操作系统详解(1)——操作系统的作用 操作系统详解(2)——异常处理(Exception) 操作系统详解(3)——进程、并发和并行 操作系统详解(4)——进程控制(fork, waitpid, sleep, execve) 操作系统详解(5)——信号(Signal) 文章目录 一些概念CPE 初步优化消除不必要的函数调用消除不必要的内存引用 基于处理器机制的深度优化现代处理器超标量(Superscalar)乱序执行处理器结构寄存器重命名多核处理器 数据流图分析促进并发(parallelism)n*1 循环展开n*n循环展开吞吐量界限(Throughout)不同的运算结合 优化的限制因素寄存器溢出分支预测 如何优化一个程序的运行速度可以从以下几个方面着手
算法数据结构执行的步骤循环
本文将主要从计算机系统底层方面探讨如何降低运行时间。
一些概念
CPE
即Cycles Per Element, 运行每一个操作需要的时钟周期
T CPE*n Overhead n: 操作数量 overhead: 其它操作时延
初步优化
以下是一个粗糙的c程序代码: void combine1(vec_ptr v, data_t *dest)
{long i;*dest IDENT;for (i 0; i vec_length(v); i) {data_t val;get_vec_element(v, i, val);*dest *dest OP val;}
}
/*
v: 一个向量
dest: 存储执行结果
OP: 运算符, 可以是, *等
vec_length: 返回向量长度
get_vec_element: 范围下标为i的元素, 存放在val中
IDENT: 单位元, 加法就是0, 乘法就是1
*/CPE如下:(Element为执行一次循环)
可见gcc自带的优化也能对性能起到很大影响.本例中是O1优化.
消除不必要的函数调用
void combine2(vec_ptr v, data_t *dest)
{long i;long length vec_length(v);*dest IDENT;for (i 0; i length; i) {data_t val;get_vec_element(v, i, val);*dest *dest OP val;}
}由于v的长度是定长的, 不会被循环改变, 所以可以在循环前面先得到, 这样就不用每次循环都调用一次了. 在本例中优化幅度很小.但是由于length()的时间复杂度是O(n), 当v的长度很大的时候, 循环执行n次, 时间复杂度为O(n^2), 增长速度远远大于O(n)
消除不必要的内存引用
假设v结构体中存储数据的部分是一个数组, 我们用get_vec_start函数能够获取v的指向数组开头的指针, 那么可以得到一下代码:
void combine3(vec_ptr v, data_t *dest)
{long i;long length vec_length(v);data_t *data get_vec_start(v);*dest IDENT;for ( i 0 ; i length ; i ) {*dest *dest OP data[i] ;
}虽然消除了函数调用, 由于compiler已经帮我们做了很多优化, 所以转成汇编代码后效率并不会差距很大.
我们看一下汇编代码: combine3: data_t double, OP *datalength in %rax, datai in %rdx, dest in %rbx1 .L17: loop:
2 vmovsd (%rbx), %xmm0 Read product from dest
3 vmulsd (%rdx), %xmm0, %xmm0 Multiply product by data[i]
4 vmovsd %xmm0, (%rbx) Store product at dest
5 addq $8, %rdx Increment datai
6 cmpq %rax, %rdx Compare to datalength
7 jne .L17 If !, goto loop我们发现, 每一次都要先从内存中取出(%rbx), 即*dest中存储的值, 运算以后还要写回(%rbx), 如果将代码改为下面:
void combine4(vec_ptr v, data_t *dest)
{long i;long length vec_length(v);data_t *data get_vec_start(v);data_t acc IDENT;for (i 0; i length; i)acc acc OP data[i];*dest acc;
}combine4: data_t double, OP *datalength in %rax, datai in %rdx, limit in %rbp, acc in %xmm01 .L25: loop:
2 vmulsd (%rdx), %xmm0, %xmm0 Multiply acc by data[i]
3 addq $8, %rdx Increment datai
4 cmpq %rax, %rdx Compare to datalength
5 jne .L25 If !, goto loop运算结果存储在寄存器中避免循环一次执行一组额外的读写最后再写入内存即可
这是由于读写涉及内存访问, 而这比访问寄存器慢数万倍.
这难道就是优化的极限了吗?
基于处理器机制的深度优化
现代处理器
超标量(Superscalar)
能够实现指令(instruction)层面的并行执行, 一个clock cycle执行多条指令
乱序执行
(只要不影响程序执行结果), 指令的执行顺序可以与汇编语句的顺序不同.
处理器结构
这部分的实际设计思想比较复杂, 本文只是简要提及几个重要概念. 微操作Instruction Decode Unit 读取程序的指令并将它们分解为更细的基础操作。 比如说一条汇编语句addq %rax, 8(%rdx)可以被分解为
load 8(%rdx) - t1
addq %rax, t1 - t2
store t2, 8(%rdx)其中load, addq(运算), store就是基础的操作。
寄存器重命名
addq $8, %rdx 被翻译为 addq $8, %rdx.0 - %rdx.1 寄存器名后面的 .t 表示一个标签用来标识操作的执行顺序。
多核处理器
在上图中, Execution Unit 从 Instruction Control Unit 得到需要执行的操作在么一个时钟周期能执行一组操作。
现代的处理器都有多个处理单元。以Intel i7处理器为例其处理单元如下
下面解释一下几个名词的意思 Latency: 就是执行一条操作需要的时间。比如上表中的第一行第一列Integer Addition的Latency是1说明执行1条整数加法需要1个时钟周期。而执行一次浮点数乘法需要5个时钟周期。
Issue: 中文又译作“发射”时间。比方说一个整数乘法需要3个时钟周期但如果用pipeline执行每一个clock都能“发射”一条微指令这样每一个clock都能执行一条指令.
Capacity: 容量即处理器有几个该运算的处理单元。从上图可知有4个Integer arithmetic Unit 整数运算单元故Capacity为4.
数据流图
Data-Flow Graphs, 用于可视化程序的数据依赖.
以combie4为例 (data_t ) float, OP *
void combine4(vec_ptr v, data_t *dest)
{long i;long length vec_length(v);data_t *data get_vec_start(v);data_t x IDENT;for (i 0; i length; i)x x OP data[i];*dest x;
}汇编
.L25: # Loop:
vmulsd (%rdx),%xmm0,%xmm0 # x * data[i]
addq $8, %rdx # Increment datai
cmpq %rax,%rdx # Comp to datalen
jne .L25 # if !, goto Loop微指令
load (%rdx.0) - t.1
mulq t.1, %xmm0.0 - %xmm0.1
addq $8, %rdx.0 - %rdx.1
cmpq %rax, %rdx.1 - cc.1
jne-taken cc.1更清晰的图 此图显示出只有当load执行以后mul才能执行因为mul对load有数据依赖. 当有多个循环时可简化为如下
分析
上图中有两条数据依赖的路径
x(%xmm)的更新mul操作i(%rdx)的更新add操作
关键路径 决定着所有操作时延上线的道路。
浮点数乘法的时延为5整数加法的时延为1
// 核心问题抽象
for(i 0; i length; i)x x * data[i];所以一次循环最少也需要5个clock才能执行完所以理论上combine4的latency就是5.
我们回顾一下combine4优化的结果 正符合理论结果 CPE正好就是微操作的latency. 当然细心的读者可能发现了为什么整数乘法的结果是1.27而不是1呢 这种数据流表示只是为latency提供了一个下限。实际情况更为复杂
有多少功能模块可用。比方说unit0和unit1不光执行整数加法还执行浮点运算、除法运算等等。所以并不是每一个clock都能加载整数加法运算。功能模块传递的数据量也是有上限的。
促进并发(parallelism)
以上我们虽然了解了限制运行速度的底层原理但还是无法进一步优化代码。可以注意到Issue的值都为1. 我们可以将操作的时延降到1或更低吗 这就需要将多条指令同时执行而不是只能一个等着另一个。
n*1 循环展开
首先来看一下这个代码
void combine5(vec_ptr v, int *dest)
{int i;int length vec_length(v);int limit length - 1;data_t *data get_vec_start(v);data_t acc IDENT;/* combine 2 elements at a time */for (i 0; i limit; i2)acc acc OPER data[i] OPER data[i1];/* finish any remaining elements */for (; i length; i)acc acc OPER data[i];*dest acc ;
}在for循环中一次执行了两次操作。 这种方法叫做 Loop Unrolling , 译为 循环展开 . 在本例中执行2个运算有1个独立的data链所以叫做 2*1循环展开.
3*1循环展开也类似作出相应的数据流图 load操作不存在依赖关系因为load不会改变data数组的内容所以肯定可以并发运行。
关键路径:
integer add: 时延为1double mul: 时延为5
图中加黑的是关键路径可见虽然做了循环展开latency bound仍然不变平均执行一次操作仍需要5个cycles. 我们看到对于整数加法CPE 有所改进得到的延迟界限为 1.00。会有这样的结果 是得益于减少了循环开销操作。
但是其它情况并没有改良。
n*n循环展开
要想进一步降低时延就要让两次mul操作之间不存在数据依赖也就是让两次mul分开并发地执行。 见代码:
void combine6(vec_ptr v, int *dest)
{int i;int length vec_length(v), limit length-1;data_t *data get_vec_start(v);data_t acc0 IDENT, acc1 IDENT;/* combine 2 elements at a time */for (i 0; i limit; i2){acc0 acc0 OPER data[i];acc1 acc1 OPER data[i1];}/* finish any remaining elements */for (; i length; i)acc0 acc0 OPER data[i];*dest acc0 OPER acc1;
}上面用了两个变量acc0, acc1分别来存储data[i] data[i1] 的运算结果。等到循环结束后再合并。这样两个循环内的乘法不存在 data dependency.
一次循环有两次操作有2个独立的操作所以是 2*2循环展开。 我们成功突破了时延的下限 除了整数加法以外其余操作都降低了一般的时延。 那么优化的极限是什么呢
吞吐量界限(Throughout) 注意到Capacity, 而这正是处理单元的数量。理论上随着循环展开数量的不断增加操作的时延应该会不断逼近Issue. 而如果有两个处理单元的话那么1个lock里就能执行两个操作这使得时延变为0.5而最优的时延值就是 Throughout.
不同的运算结合
void combine7(vec_ptr v, int *dest)
{int i;int length vec_length(v), limit length-1;data_t *data get_vec_start(v);data_t acc IDENT;/* combine 2 elements at a time */for (i 0; i limit; i2){acc acc OPER (data[i] OPER data[i1]);}/* finish any remaining elements */for (; i length; i)acc acc OPER data[i];*dest acc ;
}这个函数和combine5的唯一区别就是这一句 acc acc OPER (data[i] OPER data[i1]);
这使得两个乘法不存在数据依赖 优化的限制因素
寄存器溢出
当寄存器不够用时会用栈作为存储。 所以过多的循环展开反而导致速度下降。
分支预测
由于追求最高的效率所以远在分支预测的结果出来前就要加载下面更多的操作进行执行。所以一旦发现预测错误就要撤销所有已经做的操作。 一般来说Core i7 芯片由于一次预测错误将导致约19个时钟周期。 不过正常来说分支预测都不位于关键路径上不用特别担心。
不过下面是一个很明显的栗子显示了预测错误惩罚的结果
