核心系统数据库组 褚霸(余锋) http://blog.yufeng.info 2013-5-7 CPU高效编程技术 核心系统数据库组 褚霸(余锋) http://blog.yufeng.info 2013-5-7.

Presentation on theme: "核心系统数据库组 褚霸(余锋) http://blog.yufeng.info 2013-5-7 CPU高效编程技术 核心系统数据库组 褚霸(余锋) http://blog.yufeng.info 2013-5-7."— Presentation transcript:

1 核心系统数据库组 褚霸(余锋) http://blog.yufeng.info 2013-5-7
CPU高效编程技术 核心系统数据库组 褚霸(余锋)

2 微处理器的核心技术 流水线处理 运算器高速化 RISC和CISC 超标量执行 乱序执行 分支预测 缓存 多核心

3 了解处理器Nehalem E5620 长流水线 >= 15级 X86指令解释为微指令后乱序执行
等待执行的微指令放在Reserveration Station 多个ALU运算单元并发、乱序执行 Reorder Buffer中实现串行化 Instruction Retirement

4 Pipeline 示例：4级和8级的流水线

5 Intel的长流水线

6 Front End 读入x86指令， 每个时钟周期 16字节 x86指令解析为微指令（μop） 微指令（μop）缓存

7 乱序执行-1 寄存器重命名 分配临时寄存器 微指令进入保留站 发射指令 EU EU EU 各种运算 Load/Store

8 乱序执行-2 按指令顺序写出结果 指令生效，真正写入 内存和物理寄存器 存入临时寄存器 触发具有数据依赖的指令执行 EU中计算结果
Load/Store

9 指令量化分析 取指令，每个16字节/cycle X86指令解析为微指令 保留站到EU的Port，总共6个 简单指令3条/cycle
P0，P1，P5到ALU单元 P2，P3，P4到Load/Store单元 Instruction Retirement，4条μop/cycle Dependency Chain长度

10 指令优化 长流水线 >= 15级 充分发挥Intel处理器乱序执行的能力 Branch prediction miss性能损耗大
减少/消除conditional branch Bit运算代替比较 Comvg指令代替比较 充分发挥Intel处理器乱序执行的能力 避免指令间存在long dependency chain 避免指令间隐性的依赖关系，例如对eflags的依赖

11 CPU内部各部件访问速度

12 充分利用寄存器 # define LZ4_COPYSTEP(s,d) A64(d) = A64(s); d+=8; s+=8; # define LZ4_COPYPACKET(s,d) LZ4_COPYSTEP(s,d) #define LZ4_WILDCOPY(s,d,e) do { LZ4_COPYPACKET(s,d) } while (d<e);

13 位运算 int r; if (!(val>>32)) { r=4; } else { r=0; val>>=32; } if (!(val>>16)) { r+=2; val>>=8; } else { val>>=24; } r += (!val); return r;

14 并行执行 *op++ = *ref++;

15 消除Conditional Branch 如何消除这个if语句 if (a < b) { r = c; } else { r = d;
Bit运算版本1 int mask = (a-b) >> 31; r = (mask & c) | (~mask & d); Bit运算版本2 r = d + mask & (c-d); cmovg版本 r = (a < b) ？c : d;

16 分支可能性提示 #define likely(expr) expect((expr) != 0, 1) #define unlikely(expr) expect((expr) != 0, 0) while likely(ip<matchlimit-(STEPSIZE-1)) { … }

17 The Blocking Technique

18 The Blocking Technique
// Increasing memory usage improves compression ratio // Reduced memory usage can improve speed, due to cache effect // Default value is 14, for 16KB, which nicely fits into Intel x86 L1 cache #define MEMORY_USAGE 14 #define HASH_LOG (MEMORY_USAGE-2) #define HASHTABLESIZE (1 << HASH_LOG) struct refTables { HTYPE hashTable[HASHTABLESIZE]; };

19 memchr magic_bits = ((unsigned long int) 0x7efefefe << 32) | 0xfefefeff; /* Set up a longword, each of whose bytes is C. */ charmask = c | (c << 8); charmask |= charmask << 16; charmask |= charmask << 32; /* Instead of the traditional loop which tests each character, we will test a longword at a time. The tricky part is testing if *any of the four* bytes in the longword in question are zero. */ while (n >= sizeof (longword)) { longword = *longword_ptr++ ^ charmask; if ((((longword + magic_bits) & ~magic_bits) != 0) … }

20 memchr续 { const unsigned char *cp = (const unsigned char *) (longword_ptr - 1); if (cp[0] == c) return (__ptr_t) cp; ... if (cp[7] == c) return (__ptr_t) &cp[7]; } n -= sizeof (longword);

21 False sharing

22 对齐cacheline typedef union { GFAllctr_t gfa; char align_gfa[ERTS_ALC_CACHE_LINE_ALIGN_SIZE(sizeof(GFAllctr_t))]; } ErtsAllocatorState_t; char *states = erts_sys_alloc(0, … + ERTS_CACHE_LINE_SIZE - 1)); states = ((((UWord) states) & ERTS_CACHE_LINE_MASK) ? (char *) ((((UWord) states) & ~ERTS_CACHE_LINE_MASK) + ERTS_CACHE_LINE_SIZE) : (char *) states);

23 perf list RAW HARDWARE EVENT DESCRIPTOR Even when an event is not available in a symbolic form within perf right now, it can be encoded in a per processor specific way. For instance For x86 CPUs NNN represents the raw register encoding with the layout of IA32_PERFEVTSELx MSRs (see [Intel(R) 64 and IA-32 Architectures Software Developer's Manual Volume 3B: System Programming Guide] Figure 30-1 Layout of IA32_PERFEVTSELx MSRs) or AMD's PerfEvtSeln (see [AMD64 Architecture Programmer's Manual Volume 2: System Programming], Page 344, Figure 13-7 Performance Event-Select Register (PerfEvtSeln)).

24 致谢 部分图片和代码来自鸣嵩 《treelink比赛分享》

25 Gtalk: mryufeng@gmail.com
多谢大家! Questions？ QQ:526275 Gtalk: