Joyce' Blog
0%

计组复习笔记（一）

发表于 更新于
名称 控制对象
RegDst 选择目的寄存器
RegWr 读或写寄存器
ExtOp 立即数扩展方式
ALUSrc ALU单元的输入
MemWr 读或写存储器
MemToReg 选择要写回的寄存器数据
ALUctr ALU单元的操作
Branch 是否分支指令
Jump 是否跳转指令
Zero 分支条件是否为真

ori 逻辑与 指令，其中一个操作数为立即数。

程序计数器PC：存放下一条将要执行的指令在内存中的地址。

堆栈指针寄存器sp：指向堆栈中的栈顶。（返回地址保存在此，return返回指令将保存在栈顶地址弹到PC中）

练习

第一章

假定基准程序A在某计算机上的运行时间为100秒，其中90秒为CPU时间，其余为I/O时间。若CPU速度提高50%，I/O速度不变，则运行基准程序A所耗费的时间是70秒。(注意提高50%，表示现在速度是原来的1.5倍)

冯诺依曼计算机根据指令周期的不同阶段区分从存储器中取出的是指令还是数据，在取指周期根据PC所指示的地址，取出的是指令；在执行周期根据指令中所指示的地址，取出的是数据。

概要

影响性能的因素：

  1. 算法（语句条数）
  2. 编程语言、编译器、体系结构（每条语句对应的指令条数）
  3. 处理器、存储系统（指令执行速度）
  4. I/O系统（I/O执行速度）

八个伟大思想：

  1. 面向摩尔定律的设计：预测设计完成时的工艺水平
  2. 使用抽象简化设计：高级语言、MIPS指令集
  3. 加速大概率事件：寻址附近的指令
  4. 通过并行提高性能
  5. 通过流水线提高性能
  6. 通过预测提高性能
  7. 存储器层次
  8. 通过冗余提高可靠性

计算机部件：输入、输出、存储器、数据通路（运算器）、控制器。后两者合称处理器。

性能：执行时间的倒数，提高性能的因素可从公式分析：

CPU Time=CPU Clock Cycles * Clock Cycle Time=CPU Clock Cycles / Clock Rate

Clock Cycles=Instruction Count * Cycles per Instruction

CPU Time=Instruction Count CPI Clock Cycle Time=Instruction Count * CPI / Clock Rate

MIPS=Instruction Count/(Execution time 10^6)=Clock rate/(CPI 10^6)

功率墙——多核微处理器，通过并行提高性能

指令

指令设计的四个基本原则

  1. 简单源于规整(算数运算的固定格式)
  2. 越小越快(MIPS仅有32个寄存器)
  3. 加速大概率事件(立即数、零号寄存器、PC相对寻址)
  4. 折中(没有“小/大于则跳转”的指令，只有小于置位，和(不)等则跳转，因为硬件难度；在指令中提供更大的地址与常数并且保持所有的指令具有相同的长度)

MIPS指令集

算术运算（两个源操作数一个地址）

0(\$zero)用于寄存器间数据移动 ）

存储器操作：

主存按字节寻址，按字对齐，找地址时，数组的下标要*4。MIPS大端对齐，数据高位在地址低位。load和store指令将低16位作为偏移地址，rs为基址。

立即数操作：

有符号数1000 0000 … 0000表示最小的负数$-2^{31}$，0000 0000 … 0000表示0；

逻辑操作：

rs未使用，被置为全0；与0异或，等同取反；

决策指令：

C代码：

1
while (save[i]==k)i+=1;

MIPS代码：

1
2
3
4
5
6
7
loop: sll $t1,$s3,2
	  add $t1,$t1,$s6
	  lw $t0,0($t1)
	  bne $0,$s5,exit
	  addi $s3,$s3,1
	  j loop
exit: ...

“基本块”

过程调用

6个步骤

寄存器分配

\$a0 – $a3: arguments (reg’s 4 – 7)

\$zero: (0)用于寄存器间数据移动

\$v0, $v1: result values (reg’s 2 and 3)

\$t0 – $t9: temporaries(reg’s 8 – 15，reg’s24 –25) Can be overwritten by callee

\$s0 – $s7: saved (reg’s 16 and 23) Must be saved/restored by callee

\$gp: global pointer for static data (reg 28)

\$sp: stack pointer (reg 29)

\$fp: frame pointer (reg 30)

\$ra: return address (reg 31)

例

叶程序：

1
2
3
4
5
6
int leaf(int g,int h,int i,int j)
{
    int f;
    f=(g+h)-(i+j);
    return f;
}

Arguments g, …, j in \$a0, …, $a3

f in \$s0 (hence, need to save $s0 on stack)

Result in $v0

1
2
3
4
5
6
7
8
9
10
leaf:
	addi $sp,$sp,-4
	sw $s0,0($sp)
	add $t0,$a0,$a1
	add $t1,$a2,$a3
	sub $s0,$t0,$t1
	add $v0,$s0,$zero
	lw $s0,0($sp)
	addi $sp,$sp,4
	jr $ra

非叶程序：

1
2
3
4
5
int fact (int n)
{
    if (n < 1) return 1;
    else return n * fact(n - 1);
}

Argument n in $a0

Result in $v0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
fact: addi $sp,$sp,-8
	  sw $ra,4($sp)
	  sw $a0,0($sp)
	  slti $t0,$a0,1
	  beq $t0,$zero,L1
	  addi $v0,$zero,1
	  addi $sp,$sp,8
	  jr $ra
L1:   addi $a0,$a0,-1
	  jal fact
	  lw $a0,0($sp)
	  lw $ra,4($sp)
	  addi $sp,$sp,8
	  mul $v0,$v0,$a0
	  jr $ra

字符串复制

1
2
3
4
5
6
7
void strcpy(char x[],char y[])
{
    int i;
    i=0;
    while((x[i]=y[i])!='\0')
        i+=1;
}

Addresses of x, y in \$a0, $a1

i in $s0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
strcpy:
	addi $sp,$sp,-4
	sw $s0,0($sp)
	add $s0,$zero,$zero
L1: add $t1,$s0,$a1
	lbu $t1,0($t1)
	add $t3,$s0,$a0
	sb $t2,0(t3)
	beq $t2,$zero,L2
	addi $s0,$s0,1
	j L1
L2: lw $s0,0($sp)
	addi $sp,$sp,4
	jr $ra

分支和跳转中的寻址

PC相对寻址：因为MIPS指令都是4字节长，所以抛出相对寻址时所加的地址被设计为字地址而不是字节地址，跳转范围扩大4倍。

直接跳转：PC高四位不变

动态链接库(DLL)的晚过程链接：在随后的调用中，查找例程、重映射例程、链接例程被跳过

即时编译器JIT：选择性的将一些方法编译成宿主机上的本地机器语言

在字节寻址的机器中，连续的字地址相差4；

Instruction class MIPS examples
Arithmetic add, sub, addi
Data transfer lw, sw, lb, lbu, lh, lhu, sb, lui
Logical and, or, nor, andi, ori, sll, srl
Cond. Branch beq, bne, slt, slti, sltiu
Jump j, jr, jal

计算机的算术运算

乘法

高位HI，低位LO

Instructions

mult rs, rt / multu rs, rt 64-bit product in HI/LO

mfhi rd / mflo rd Move from HI/LO to rd，Can test HI value to see if product overflows 32 bits

mul rd, rs, rt Least-significant 32 bits of product –> rd

除法

浮点运算

数值表示

尾数精度=尾数位数+1

单精度规格化数：阶码取值范围在1~254之间；尾数可以取任何值。

对于float型，特殊的值：

符号位 阶码/指数 尾数 数值
+/- 全0 全0 0
+/- 全1(=255) 全0 +无穷/-无穷
+/- 全0 非0 非规格化数
+/- 全1(=255) 非0 非数NaN

移码

范围

精度：float（$2^{-23}$）

例

表示-0.75：

float: 1 01111110 100 … 00

double: 1 01111111110 1000…00

高级语言中可以定义多种数据类型，因此需要存取不同长度操作数的数据传输指令。

浮点数加法

对阶的时候，需要小阶向大阶看齐，因为大阶如果向小阶看齐，那么就要左移，不符号规格化的要求。

浮点数乘法

浮点数乘法运算结果规格化：不需要左移，最多需要一次右移；除法：不需要右移，最多需要一次左移。正常的运算过程下，若尾数为0，则结果的阶码也置为0.

浮点加法不满足结合律

子字并行

Matrix Multiply

未优化：

1
2
3
4
5
6
7
8
9
10
11
void dgemm (int n, double* A, double* B, double* C)
 {
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < n; ++j)
    {
     double cij = C[i+j*n]; /* cij = C[i][j] */
     for(int k = 0; k < n; k++ )
      cij += A[i+k*n] * B[k+j*n]; /* cij += A[i][k]*B[k][j] */
      C[i+j*n] = cij; /* C[i][j] = cij */
   }
}

优化后：

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <x86intrin.h>
void dgemm (int n, double* A, double* B, double* C)
{
	for ( int i = 0; i < n; i+=4 )
    for ( int j = 0; j < n; j++ ) {
    	__m256d c0 = _mm256_load_pd(C+i+j*n); /* c0 = C[i][j] */
    for( int k = 0; k < n; k++ )
    	c0 = _mm256_add_pd(c0, /* c0 += A[i][k]*B[k][j] */
              _mm256_mul_pd(_mm256_load_pd(A+i+k*n),
             _mm256_broadcast_sd(B+k+j*n)));
    	_mm256_store_pd(C+i+j*n, c0); /* C[i][j] = c0 */
    }
}