计算机系统结构笔记(一)

¶Amdahl定律

加速比定义:

$$
S_n = \frac{新速度}{老速度} = \frac{老时间}{新时间} = \frac{T_o}{T_n}
$$

作为计算机组成原理的总原理加快经常性事件的定量形式,Amadahl定律为:

$$
S_n = \frac{1}{(1-F_e)+ \frac{F_e}{S_e}}
$$

如下图所示

¶证明

改进之前程序运行总时间可写为:

$$
T_o = T_o ( 1 - F_e + F_e)
$$

改进后总时间降为:

$$
T_n = T_o ( 1 - F_e + \frac{F_e}{S_e})
$$

所以,加速比$S_n$表示为

$$
S_n = \frac{T_o}{T_n} = \frac{1}{(1-F_e)+ \frac{F_e}{S_e}}
$$

¶CPU性能公式

• CPU时间: 一个程序在CPU上运行的时间,不包括I/O时间.

  • 时钟周期时间: 时钟周期时间越短,相应的CPU性能就越好
  • 程序的时钟周期数: CPU时间 = 程序的时钟周期数 $ \times $ 时钟周期时间
  • 指令周期数CPI: 平均每条指令耗费的时钟周期数
  • IC: 程序执行的指令条数. 指令周期数CPI = 程序的时钟周期数 / IC

程序执行的CPU时间可以写成:

$$
CPU时间 = IC \times CPI \times 时钟周期时间
= IC \times CPI / 时钟频率
$$

¶局部性原理

程序执行时间的90%都是在执行程序中10%的代码。

• 时间局部性(Temporal Locality):如果一个信息项正在被访问,那么在近期它很有可能会被再次访问。
• 空间局部性(Spatial Locality):程序即将用到的信息很可能与目前正在使用的信息在空间上相邻或者临近。

¶实例

//求数组元素之和,v为数组名,n为数组大小
int sum(int *v,int n)
{
    int i=0;
    int sum=0;
    for(i=0;i<n;i++)
    {
        sum+=v[i];
    }
    return sum;
}

sum具有时间局部性

v数组具有空间局部性

¶总结

• 阿兰.图灵:图灵机-计算机的(理论基础)
• 冯.诺依曼:冯诺依曼体系结构(架构基础)
• 戈登.摩尔:摩尔定律(物质基础)
• 阿姆当:Amdahl定律(计算机系统结构的总原则)

¶并行

并行性:计算机系统在同一时刻或者是间隔内进行多种运算或操作

• 同时性:两个或两个以上的事件在同一时刻发生
• 并发性:两个或两个以上的事件在同一时间间隔内发生

从处理数据的角度上来看:

• 字串位串:每次只对一个字的一位进行处理
• 字串位并:同时对一个字的全部位进行处理,不同字之间是串行的
• 字并位串:同时对许多字的同一位(称为位片)进行处理
• 全并行:同时对许多字的全部位或部分位进行处理

从执行程序的角度上来看:

• 指令内部并行:单条指令中各微操作之间的并行
• 指令级并行:并行执行两条或两条以上的指令
• 线程级并行:并行执行两个或两个以上的线程
• 任务级或过程级并行:并行执行两个或两个以上的过程或任务(程序段)
• 作业或程序级并行:并行执行两个或两个以上的作业或程序

¶提高并行的三种途径

• 时间重叠:引入时间因素,让多个处理过程在时间上相互错开,轮流重叠地使用同一套硬件设备的各个部分,以加快硬件周转而赢得速度
• 资源重复:引入空间因素,以数量取胜。通过重复设置硬件资源,大幅度地提高计算机系统的性能
• 资源共享:软件方法,使多个任务按一定时间顺序轮流使用同一套硬件设备

¶单处理机

在发展高性能单处理机过程中,起主导作用的是时间重叠原理.

实现时间重叠的基础:部件功能专用化.

在单处理机中,资源重复原理的运用也已经十分普遍

• 多体存储器
• 多操作部件
• 阵列处理机(并行处理机)

¶计算机系统评价

计算机系统设计的四个要素

• 性能
• 成本
• 能耗
• 可靠性

性能

• 响应时间(response time):完成一个任务的全部时间
• 吞吐率(throughput):单位时间内完成的任务数

其他指标:

• $MIPS = \frac{指令条数}{执行时间 \times 10^6}=\frac{f}{CPI \times 10^6}$
• $程序执行时间Te = \frac{指令条数}{MIPS \times 10^6}$
• $MFLOPS = \frac{程序中的浮点操作数}{执行时间 \times 10^6}$

唯一真正可以衡量计算机性能的指标是真实程序的执行时间.

基准测试程序( Benchmark)

• 实际应用程序
• 修正(或脚本化)的应用程序
• 核心测试程序
• 小测试程序
• 合成测试程序

基准测试程序套件( Benchmark suites): SPEC89 SPEC92 SPEC2006 SPEC2017

数据中心可靠率要达到99.9999%,也就是不可靠率不超过0.00001%

¶计算机系统结构的发展

冯·诺依曼结构的主要特点

• 计算机以运算器为中心。
• 在存储器中,指令和数据同等对待。
• 存储器是按地址访问、按顺序线性编址的一维结构,每个单元的位数是固定的。
• 指令的执行是顺序的

输入输出方式的改进

• 程序控制
  a)程序等待:CPU需轮询LO设备,造成CPU时间浪费
  b)程序中断:CPU与I/O设备可并行工作
• DMA直接存储器访问:减少CPU对I/O的干预
• I/O处理机:满足复杂的I/O请求

采用并行处理技术

存储器组织结构的发展

• 相联存储器
• 通用寄存器组
• 高速缓冲存储器cache

指令系统的发展

• 复杂指令集CISC
• 精简指令集RISC

注意精简指令集的寄存器用得更多,硬件更为简单.

¶课后作业

1.7 对于一台400MHz计算机执行标准测试程序,程序中指令类型,执行数量和平均时钟周期数如下:

指令类型	指令执行数量	平均时钟周期数
整数	45000	1
数据传送	75000	2
浮点	8000	4
分支	1500	2

求该计算机的有效CPI、MIPS和程序执行时间。

解:

$$
CPI =(45000\times 1+75000\times 2+8000\times 4+1500\times 2) / 129500=1.776
$$

$$
MIPS=\frac{f}{CPI}=\frac{400}{1.776}=225.225
$$
程序执行时间为
$$
(45000\times 1+75000\times 2+8000\times 4+1500\times 2)/400=0.575ms
$$

1.8 计算机系统有三个部件可以改进,这三个部件的加速比如下:部件加速比1=30；部件加速比2=20；部件加速比3=10；
(1)如果部件1和部件2的可改进比例为30%,那么当部件3的可改进比例为多少时,系统的加速比才可以达到10？
(2)如果三个部件的可改进比例为30%、30%和20%,三个部件同时改进,那么系统中不可加速部分的执行时间在总执行时间中占的比例是多少？

(1) 解: 在多个部件可改进的情况下,由Amdahl定理的拓展:

$$
S_n=\frac{1}{(1-F_n)+\sum \frac{F_i}{S_i}}
$$

已知S1=30,S2=20,S3=10,Sn=10,F1=0.3,F2=0.3,得:

$$
10 = \frac{1}{1-(0.3+03+F3)+(0.3/30+03/20+F3/10)}
$$

得$F_3=0.36$,即部件3的可改进比例应达到36%

(2) 解: 设系统改进前的执行时间为T,则3个部件改进前的执行时间为:(0.3+0.3+0.2)
T=0.8T,不可改进部分的执行时间为0.2T,已知3个部件改进后的加速比分别为$S_1$=30,$S_2$=20,$S_3$=10,因此3个部件改进后的执行时间为
$$
T_n=\frac{0.3T}{30}+\frac{0.3T}{20}+\frac{0.2T}{10}=0.045T
$$
改进后整个系统的执行时间为:$Tn=0.045T+0.2T=0.245T$

那么系统中不可改进部分的执行时间在总执行时间中占的比例是:
$$
\frac{0.2T}{0.245T}=0.82
$$

1.11 假设浮点数指令FP指令的比例为30%,其中浮点数平方根FPSQR占全部指令的比例为4%,FP操作的CPI为5,FPSQR操作的CPI为20,其他指令的平均CPI为1.25,现有两种改进方案
第一种:把 FPSQR操作的CPI减至3
第二种:把所有的FP操作的CPI减至3
试比较两种方案对系统性能的提高程度。

解: 由题意可知,
$$
CPI_{原始}=5 \times 0.3 + 1.25 \times 0.7 = 2.375
$$
设除FPSQR外其余指令的平均CPI为$X$,则有:
$$
2.375 = 20 \times 0.04 + X \times 0.96
$$
得 $X=1.640625$

则
$$
CPI_{方案一}=3 \times 0.04 + 1.640625 \times 0.96 = 1.695
$$
$$
CPI_{方案二}=3 \times 0.3+ 1.25 \times 0.7 = 1.775
$$

因此,显然方案二方案一对系统性能的提高程度更高.

¶补充概念

CPU对各种存储器的访问速度基本上是：

CPU 内部RAM > 外部同步RAM > 外部异步RAM > FLASH/ROM

DRAM为主存,也就是内部RAM