Skip to content

Architecture

体系结构复习

第一章

  1. Amdahl 定理

Amdahl定理描述了改进可并行部分后计算机系统整体的加速比例

​

  • 书上的定理
\begin{align} Fe &= \frac{T_{可并行}}{T_{总}}\\ Se &= \frac{T_{可并行}}{T'_{可并行}}（T'_{可并行}表示改进后T_{可并行}需要的时间)\\ &那么:\\ T'_{总} &= T_{总}((1-Fe) + \frac{Fe}{Se}) ,(去除不可并行的部分，然后乘上可并行部分的加速比例)\\ &因此改进后整个任务的加速比为:\\ Sn &= \frac{T_{总}}{T'_{总}} = \frac{1}{(1-Fe) + \frac{Fe}{Se}} \end{align}

  1. 概念:为什么发展计算机系统结构

  2. 体系结构：研究软硬件功能分配和软硬件界面

  3. 组成原理：逻辑实现
  4. 实现：物理实现
🌰：
    确定是否需要乘除指令 -- 系统结构
    乘除指令用乘法器还是加法器实现 -- 组成原理
    乘法器或加法器的物理实现 -- 实现

  1. 模拟和仿真

  2. 模拟：软件实现（宿主机，虚拟机），灵活但是速度慢

  3. 仿真：硬件实现（宿主机，目标机），速度快但是不灵活

  4. CPU性能公式

\mathbf{CPI} = \frac{\mathbf{CPU}时钟周期总数}{指令条数} \\ T_\mathbf{CPU} = T_{0} \times \sum_{i=1}^n(\mathbf{CPI}_{i}\times \mathbf{I}_{i})\\

一些表示衡量指令执行速度的单位

MIPS(Million instructions per second)，GIPS，TIPS。IPC为Instructions per cycle $$ \begin{align} \mathbf{MIPS} &= \frac{指令条数}{指令执行时间\times10^6}=\mathbf{f}\times\mathbf{IPC} \ \mathbf{GIPS} &= \frac{指令条数}{指令执行时间\times10^9}=\mathbf{f}\times\mathbf{IPC} \ \mathbf{TIPS} &= \frac{指令条数}{指令执行时间\times10^{12}}=\mathbf{f}\times\mathbf{IPC}\ \end{align} $$

  1. 设计方法

  2. 自上而下：专用计算机

  3. 自下而上：通用，效率低

  4. 中间开始：合理

  5. 佛林分类法

按照指令流和数据流的多倍型特征进行分类

  • 指令流：机器执行的指令序列
  • 数据流：由指令流调用的数据序列
  • 多倍性：最大可能数

S：single|M：multiple|I：Instruction|D：Datasteam

于是分成：

SISD：标量流水处理机

SIMD：并行、向量、超流水线

MIMD：几乎不存在

MIMD：不存在

缺点：

  • 分类粗（SIMD中包含多种）

  • 数据流受指令流控制（MISD不可能存在）

  • 冯氏分类

用最大并行度来分类，假设同时处理的字数m，字的二进制位数n，用(m,n)表示

缺点是只考虑数据并行

  1. 汉德勒分类

多层次分类

  1. 补充：计算机系统的层次结构

共0-6层。

  • 0-1层CPU功能：硬联逻辑，微程序
  • 2层软硬件分界：机器语音
  • 3-5层系统软件：操作系统，汇编语言，高级语言

  • 6层应用软件：应用程序

  • 补充：系列机

具有相同的系统结构，但是组成和实现技术不同的计算机系统【性能，价格】

  1. 补充：虚拟机

由软件实现的机器

第二章

  1. 数据类型

数据表示：计算机硬件能够直接识别，被指令系统直接调用的数据类型

数据结构：软件实现的数据表示，算法

🌰：
    C = A + B
    （1）无向量数据表示：需要4条指令
    （2）有向量数据表示：需要1条指令

  1. 指令组成

  2. 操作码：操作种类，操作数描述

  3. 地址码：地址，地址附加信息，寻址方式

操作码三种编码方式：

  • 固定长度
  • Huffman：（手工：自上而下编码）

  • 扩展编码：由固定长操作码与Huffman编码结合

  • 地址码的优化设计

  • 存储容量

  • 执行速度

  • 指令系统的二八定律

  • 简单指令占20%，出现频率80%

  • 复杂指令占80%，出现频率20%

  • 补充：RISC的定义、特点和细想精华

  • 定义：精简指令系统——只保留功能简单，能在一个时钟周期内完成的指令，其他复杂功能用一段子程序实现

  • 特点：单周期、固定指令格式、编译优化、减少指令和寻址方式种类|LOAD/STORE，硬布线控制逻辑

  • 思想精华：减少\mathbf{CPI}

存储系统

  1. 定义
\begin{align} \mathbf{price}(便宜 + 贵) &\simeq \mathbf{price}(便宜) \\ \mathbf{speed}(便宜 + 贵) &\simeq \mathbf{speed}(贵) \\ \mathbf{capacity}(便宜 + 贵) &\simeq \mathbf{capacity}(便宜) \\ \end{align}
  1. 访问效率
\mathbf{e} = \frac{T_{1}}{T} = \frac{T_{1}}{H \times T_{!} + (1-H)\times T_{2}}
  1. 预取技术提高访问率
\mathbf{e'} = \frac{\mathbf{e} -1 + \mathbf{n}}{\mathbf{n}},\mathbf{n} = 块大小\times 重复利用率

  1. 虚拟存储器加快内部地址变换的方法

  2. 页表级数

  3. g = \left \lfloor \frac{\log_{2}N_{v}-\log_{2}N_{p}} {\log_{2}N_{p}-\log_{2}N_{d}} \right \rfloor\\ N_{v}为虚拟存储空间大小，N_{p}为页面大小，N_{d}为一个页表存储字大小

  4. 方法：

  5. 目录表

  6. 快慢表

  7. 散列函数

  8. 堆栈型算法

随着分配给程序的主存页面增加，主存的命中率也提高，至少不下降

  1. Cache存储系统地址印映像及变换方法

  2. 全相连：效率高，价格贵

  3. 直接相连：效率低，价格低

  4. 组相连：n = 1 时为直接相连，n = N时为全相连

  5. cache替换算法

  6. 轮换法：替换计数器最大的

  7. LRU

  8. cache的一致性

  9. 写直达

  10. 写回法：替换时写回

  11. 补充：存储器访问

  12. 高位交叉：提高容量

  13. 低位交叉：提高访问速度，解决访问冲突

第四章 流水线

  1. 先行控制技术

  2. 缓冲技术

  3. 预处理技术

  4. 先行指令缓冲栈的作用

只要指令缓冲栈没有满，就自动发出取指令的请求

  1. 流水线特点

  2. 只有连续提供同类任务才能发挥流水线效率

  3. 每个流水段都要设置一个流水寄存器

  4. 各流水段的水间应尽量想等

  5. 流水线性能分析指标

  6. 吞吐率(Though Put) $$ \begin{align} \mathbf{T}{p} &= \frac{\mathbf{n}}{\mathbf{T}{k}}\ \mathbf{T}{k} &= (k+n-1)\cdot \triangle t,k为流水线段数,n为任务数\ \mathbf{T}{p}\max &= \frac{1}{\triangle t} \end{align} $$

  7. 加速比

\begin{align} S &= \frac{T_0}{T_k} = \frac{k \cdot n \cdot \triangle t}{(k+n-1)\cdot \triangle t} \\ S\max &= k \end{align}
  • 效率
\begin{align} E &= \frac{顺序执行的时空区}{k个流水段的总时空区} = \frac{T_{0}}{k\cdot T_{k}} \\ & = \frac{k \cdot n \cdot \triangle t}{k\cdot(k+n-1)\cdot \triangle t} \\ & = \frac{n}{k+n-1} \end{align}

  • 小节：吞吐率看空间，加速比看时间，效率结合起来看

  • 流水线消除瓶颈

  • 将瓶颈部分再细分

  • 将瓶颈部分重复设置

  • 乱序流动中的数据相关（冒险，竞争）

  • 写读相关

  • 读写相关
  • 写写相关

  • 解决：建立相关专用通路（ByPass）

  • 多流水线调度策略

  • 顺序发射顺序完成

  • 顺序发射乱序完成

  • 乱序发射乱序完成

  • 超标量处理机采用的是空间并行性。

超流水线处理机采用的是时间并行性。：每隔1/n个时钟周期发射一条指令

11章：互联网络

  1. 方体置换函数：形成正方体

$ Cube_{0}$ 表示第 0 位取反 其他位不变 如 8 个节点 $$ {Cube_{2}(b_{2}b_{1}b_{0})=\overline{b}{2}b{1}b_{0}} $$

  1. 混洗置换 Shuffle：编码移位
Shuffle(b_{n-1}b_{n-2}…b_{1}b_{0})=(b_{n-2}…b_{1}b_{0}b_{n-1})；
  1. 蝶式置换 Butterfly：编码位交换
\beta (b_{n-1}b_{n-2}…b_{1}b_{0})=(b_{0}b_{n-2}…b_{1}b_{n-1})；

  • 子蝶式：\beta_{(k)}用b_{0}和b_{k}交换

  • 超蝶式：\beta_{(k)}用b_{n-k-1}和b_{n-1}交换

  • 移数置换： $$ a(X) = (X + k) \% N $$

  • 特例：加减2^i置换

  • PM2I_{+i}(j) = (j+2^i) \% N \\ PM2I_{-i}(j) = (j-2^i) \% N \\

补充

  1. SIMD 定义 描述 特点

  2. 定义：单指令多数据流，是单一控制部件下多个处理单元构成的阵列

  3. MIMD 定义 描述

  4. 定义：多指令多数据流，比如多处理机系统

  5. 并行性等级的划分(从数据处理角度)

  6. 字串位串：同一字同一位

  7. 字串位并：同一字所以位
  8. 字并位串：多个字同一位

  9. 字并位并：多个字多个位

  10. 并行性等级

  11. 指令内部并行

  12. 指令间并行
  13. 任务级或过程级
  14. 作业或程序级