X

曜彤.手记

随记,关于互联网技术、产品与创业

吉 ICP 备10004938-2号

《CSAPP(第三版)》读书笔记(第 4-5 章)


书接上文,本文为第 4-5 章的笔记。

第四章、处理器体系结构

  1. (Page:243)ISA 在编译器编写者和处理器设计人员之间提供了一个概念抽象层。编译器编写者只需知道允许哪些指令,以及它们是如何编码的;而处理器设计者必须构造出执行这些指令的处理器。
  2. (Page:245)程序员可见状态:程序寄存器条件码(rflags)、程序计数器(PC)、内存以及状态码(表明程序是否正常运行或发生了某个特殊事件,比如“异常”)。
  3. (Page:246)假想的 Y86-64 指令集:

  1. (Page:250)CISCRISC

  1. (Page:256)大多数现代电路技术都是用信号线上的高低电压来表示不同的位值的。逻辑 1 使用 1.0 伏特左右的高电压表示;逻辑 0 使用 0.0 伏特左右的低电压表示。而一个数字系统需要三个组成部分:*可进行位操作的函数组合逻辑、存储位的存储器单元、控制存储器单元更新的时钟信号
  2. (Page:257)HCL(硬件控制语言) -> HDL(硬件描述语言,如 Verilog / VHDL)-> 硬件。
  3. (Page:257)逻辑门:数字电路的基本计算单元。

  1. (Page:261)算数/逻辑单元(ALU)是一种重要的组合电路:

  1. (Page:262)存储器时钟组合电路(combinational circuit)不存储任何信息,仅简单地响应输入信号,产生等于输入的某个函数的输出。而时序电路(sequential circuit)则具有状态,可以存储信息。存储设备是由同一个时钟控制的,而时钟是一个周期性信号,决定什么时候要把新值加载到设备中。两类存储器设备:

(某些情况下,对时序电路的“读”操作是不受时钟控制的)

  1. (Page:264)执行一条指令的各个阶段

- 部分指令在各个阶段的执行细节

pushqpopq 的执行细节:

条件跳转、callret 的执行细节:

  1. (Page:273)上述 Y86-64 SEQ(Sequential)顺序处理器的硬件实现图:

- 符号表示

  1. (Page:275)要控制处理器中活动的时序,只需要寄存器和内存的时钟控制(对于写操作)。并且,处理器从来不需要为了完成一条指令的执行而去读由该指令更新了的状态(比如 pushq 指令不会从内存中重新读取指令执行过程中修改过的 %rsp 的值)。

- SEQ 硬件状态变化图

  1. (Page:282)非流水线流水线化

- 流水线操作的一个时钟周期

- 一些可能降低流水线效率的因素

- 流水线相关

  1. (Page:291)Y86-64 处理器流水线化的硬件结构:

- 一些说明

  1. (Page:293)PC 分支预测:如果取出的指令是条件分支指令,要到几个周期后,处理器才知道是否要选择该分支。类似地,对于 ret 指令来说,要到指令通过“访存”阶段后,才能确定返回地址。(使用条件传送而非条件控制转移,以优化性能。条件传送指令不会影响流水线的推进,即它不会修改 PC,因此后续需要执行的指令也是可见,并且可以提前进入流水线的)
  1. (Page:295)流水线冒险(hazard):相邻指令间的“相关”导致的流水线计算错误问题。

- 一个“流水线冒险”的例子

- 解决“流水线冒险”的;几个方案

  1. (Page:307)流水线化系统中异常报告的细节问题:
  1. (Page:311)“转发”的优先级(即应该转发哪一个转发源的值?):流水线化的实现应该总是给处于最早流水线阶段(最接近当前指令的)中的转发源以较高的优先级

  1. (Page:314)流水线控制逻辑需要处理的情况(针对假想的 Y86-64 架构):
  1. (Page:317)附加的流水线寄存器操作:

  1. (Page:318)特殊控制条件的流水线状态:

  1. (Page:323)Y86-64 的不足:

第五章、优化程序性能

  1. (Page:343)编译器对程序只使用安全的优化:
// 下述两个函数在 x 与 y 相等时所表示出的行为不同;
void bar(int* x, int* y) {
  *x += *y;
  *x += *y;
}
void foo(int* x, int* y) {
  *x += 2 * (*y);
}
int f();
void bar() { // 不会被优化成类似 foo 的结构;
  return f() + f() + f();
}
void foo() {
  return 3 * f();
}
  1. (Page:345)表示程序性能:使用每元素周期数(Cycles Per Element,CPE)作为一种表示程序性能的方法。它可以帮助我们在更细节的级别上理解迭代程序的循环性能。(处理的元素数量与所花费时钟周期,这条直线的斜率)
  2. (Page:355)优化 — 消除不必要的内存引用

优化前

// ...
*dest = IDENT;
for (int i = 0; i < length; i++) {
  *dest = *dest * data[i];
}
// ...

优化后

// ...
data_t acc = IDENT;
for (int i = 0; i < length; i++) {
  acc = acc * data[i];
}
*dest = acc;
// ...
  1. (Page:357)两个描述程序最大性能的下界:
  1. (Page:358)现代乱序处理器的基本结构:

  1. (Page:361)功能单元的性能:

  1. (Page:364)数据流图(DCG)分析:

机器级代码

; void combine4(vec_ptr v, data_t* dest) {
;   long i;
;   long length = vec_length(v);
;   data* data = get_vec_start(v);
;   data_acc = IDENT;
;   for (i = 0; i < length; i++) {
;     acc = acc OP data[i];
;   }
;   *dest = acc;
; }
.L25:                        ; loop:
  vmulsd (%rdx), %xmm0, %xmm0  ; Multiply acc by data[i].
  addq $8, %rdx                ; Increment data+i.
  cmpq %rax, %rdx              ; Compare to data+length.
  jne .L25                     ; If !=, goto loop.

DCGs

  1. (Page:366)循环展开(***-O3*** 情况下编译器一般可以自动执行该优化):通过增加每次迭代计算的元素的数量,减少循环的迭代次数。
void combine6(vec_ptr v, data_t* dest) {
  long i;
  long length = vec_length(v);
  long limit = length - 1;
  data_t* data = get_vec_start(v);
  data_acc0 acc0 = IDENT;
  data_acc1 acc1 = IDENT;

  /* Combine 2 elements at a time, 2x2 */
  for (i = 0; i < limit; i += 2) {
    acc0 = acc0 OP data[i];
    acc1 = acc1 OP data[i + 1];
  }

  /* Finish any remaining elemtns */
  for (; i< length; i++) {
    acc0 = acc0 OP data[i];
  }
  *dest = acc0 OP acc1;
}
  1. (Page:373)重新结合变换(reassociation transformation):改变向量元素与累积值的合并顺序。

C 代码

void combine7(vec_ptr v, data_t* dest) {
  long i;
  long length = vec_length(v);
  long 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; i += 2) {
    acc = acc OP (data[i] OP data[i + 1]);  // point here!!!
  }

  /* Finish any remaining elements */
  for (; i< length; i++) {
    acc = acc OP data[i];
  }
  *dest = acc;
}

DCGs

  1. (Page:378)一些限制因素:
// slow.
void fooA(long x[], long y[], long n) {
  long i;
  for (i = 0; i < n; i++) {
    if (x[i] > y[i]) {
      long t = x[i];
      x[i] = y[i];
      y[i] = t;
    }
  }
}
// fast;
void fooB(long x[], long y[], long n) {
  long i;
  for (i = 0; i < n; i++) {
    long min = x[i] < y[i] ? x[i] : y[i];
    long max = x[i] < y[i] ? x[i] : y[i];
    x[i] = min;
    y[i] = max;
  }
}
  1. (Page:382)内存加载性能的一个例子:
; Inner loop of list_len.
; ls in %rdi, len in %rax.
.L3:               ; loop:
  addq $1, %rax      ; Increment len.
  movq (%rdi), %rdi  ; ls = ls->next.
  testq %rdi, %rdi   ; Test ls.
  jne .L3            ; If nonnull, goto loop.
  1. (Page:383)内存的写/读相关:一个内存读的结果依赖于一个最近的内存写。

机器级代码

; void foo(long* src, long *dst, long n) {
;   long cnt = n;
;   long val = 0;
;   while (cnt) {
;     *dst = val;
;     val = (*src) + 1;
;     cnt--;
;   }
; }
; int main() {
;   long x[] = {-10, 17};
;   foo(x, x, 3);
;   return 0;
; }
; Inner loop of foo.
; src in %rdi, dst in %rsi, val in %rax.
.L3:                ; loop:
  movq %rax, (%rsi)   ; Write val to dst.
  movq (%rdi), %rax   ; t = *src.
  addq $1, %rax       ; val = t + 1.
  subq $1, %rdx       ; cnt--.
  jne .L3             ; If != 0, goto loop.

DCGs

  1. (Page:387)性能优化的基本策略


这是文章底线,下面是评论
  暂无评论,欢迎勾搭 :)