跳至主要內容

计算机体系结构

yyshino大约 12 分钟

第一章

简答题：发展并行性的三种途径

  1. 并行性：（parallelism）指问题中具有可以同时运算或操作的特性。并行性包含同时性和并发性两层含义。（同时性（Simultaneity）：两个或多个事件在同一时刻发生。并发性（Concurrency）：两个或多个事件在同一时间间隔内发生。 ）
  2. 发展并行性的三种途径：
    1. 时间重叠：（Time Interleaving）是在并行性概念中引入时间因素，让两个或多个任务在时间上相互错开，轮流使用同一套设备的各个组成部分，以加快硬件周转而赢得速度。
    2. 资源重复：（Resource Replication）是在并行性概念中引入空间因素，通过重复设置硬件资源来提高可靠性或性能。
    3. 资源共享：（Resource Sharing）是利用软件的方法让多个任务按一定时间顺序轮流使用同一套设备，以提高设备利用率和系统性能。

作业1 10分

  1. 先求平均CPI
  2. Se 改变前的CPI/改变后 | Fe 变化前CPI占总CPI的比例
  3. Sn=1/[(1-Fe) + Fe/Se]

image-20230522172017903image-20230522172332372image-20230522172407920

看一下时间，空间局部性

  • 时间局部性：程序中近期被访问的信息项很可能马上将被再次访问。
  • 空间局部性：指那些在访问地址上相邻近的信息项很可能会被一起访问。

神威太湖之光 选择

2017年6月19日，全球超级计算机500强榜单公布，中国国家超级计算无锡中心的“神威·太湖之光”和国家超算广州中心的“天河二号”第三次携手夺得冠亚军 ，美国“泰坦”20多年来首次跌出前三｡

2022年超算“前沿”运算峰值速度超过每秒100亿亿次（1102.00Pflop/s）。

第二章

引入数据表的原则2个，简答题（2.1.3）

  1. 是否有利于提高系统效率，是否减少了实现时间和存储空间
    • 举例1：两个200*200的二维定点数组相加A=A+B
    • 无阵列：需循环执行4*(200*200)=16万条指令
    • 有阵列：1条向量指令，减少16万次取指时间
  2. 看引入数据表示后，其通用性和利用率是否高；
    • 通用性：是否仅局限于一种数据结构的支持。
    • 利用率：引入某种数据表示后，该数据类型操作的次数
    • 数据结构的发展总是优先于机器的数据表示，应尽可能为数据结构提供更多的支持

2.1.4 10分必考

image-20230523155637021image-20230523155701786image-20230517202018036

操作码的优化

哈夫曼树啥的 10分（可参考期中考试）

Huffman编码

画huffman树

计算平均码长（根据使用频度和操作码码长计算）

扩展编码

两种长的扩展编码，在huffman编码的基础上，根据使用频度值分为两部分

risi有哪些技术，ppt四个标题（重叠窗口技术）

  • 重叠寄存器窗口技术
  • 延迟转移（Delayed Branch）
  • 比较转移指令
  • 优化编译

第四章

页面替换算法

  • 页面替换发生时间：

    • 当发生页面失效时，要从磁盘中调入一页到主存。如果主存所有页面都已经被占用，必须从主存储器中淘汰掉一个不常使用的页面，以便腾出主存空间来存放新调入的页面。

  • 替换算法的确定

    • 主存的命中率
    • 是否便于实现，软、硬件成本

随机算法（RAND）

  • 随机算法（Random ，RAND）：用软的或硬的随机数产生器来形成主存中要被替换页的页号。
    • 简单，易于实现
    • 没有利用历史信息
    • 命中率低，很少使用

先进先出算法（FIFO）

  • 先进先出算法（First-In First-Out ，FIFO）：选择最早装入主存的页作为被替换的页。
    • 配置计数器字段
    • 虽然利用历史信息，但不一定反映出程序的局部性

命中：主存中连续两次数据相同那么他就是命中

命中率：命中页/总页

示例：

image-20230524155155369
image-20230524155155369

命中率= 5/10=50%

近期最少使用算法（LRU）

  • 近期最少使用算法（Least Recently Used ，LRU）：选择近期最少访问的页作为被替换的页。
    • 配有计数器字段。
    • 比较正确反映程序的局部性。

主存页面数=主存容量/页面大小

虚页地址=(虚存地址/页面大小)取整

示例：

image-20230524154745662
image-20230524154745662

优化替换算法（OPT）

  • 优化替换算法（Optimal Replacement Algorithm， OPT）:是在时刻t找出主存中每个页将要用到时刻ti，然后选择其中ti-t最大的那一页作为替换页。
    • 理想化算法

说明：

  • 命中率与地址流有关
    • 例如：一个循环程序，FIFO、LRU的命中率明显低于OPT
    • 颠簸现象：连续不断出现页面失效。
  • 命中率与分配给程序的主存页数有关。
    • 主存页数增加，LRU命中率提高，至少不会下降，而FIFO不一定。

堆栈性算法

定义：设A是一个长度为L的任意虚页地址流，t为已处理过t-1个虚页的时间点，n为分配给该虚页地址流的实页数，Bt(n)表示在t时刻，在n页的主存中的页面集合，Lt表示在t时间点已处理过的虚页中页面相异的页数，若替换算法满足：

$n < Lt时 Bt(n) \subset Bt(n+1)$

$n >= Lt时 Bt(n) = Bt(n+1)$

则称此算法为堆栈型替换算法。（LRU和OPT属于堆栈性算法）

上为栈顶

下为栈底

压栈

出栈

示例

设某程序包含5个虚页，其页地址流为4，5，3，2，5，1，3，2，2，5，1，3。当使用LRU算法替换时，为获得最高的命中率，至少应分配给该程序几个实页？其可能的最高命中率为多少？

image-20230524162611047
image-20230524162611047

高速缓冲存储器

4.3要求全部掌握，对应第四章题目需要会，期中考试中也有

  • 不需要任何替换算法的地址映像？直接相联 选择题
  • 对比法需要会画电路图

Cache、组相联映像

  1. 主存、Cache地址中各个字段的含义、位数及其映像的对应关系
  2. 主存、Cache空间块的映像对应关系
  3. Cache各块随时间的使用状况
  4. 块失效又发生争用的时刻（既不是命中又不是失效的时刻，即替换）
  5. 此期间Cache之命中率

示例

4-15：有 Cache 存储器。主存有 0～7 共 8 块，Cache 有 4 块，采用组相联映像，分2组。假设Cache已先后访问并预取进了主存的第 5，1，3，7块，现访存块地址流又为1,2,4,1,3,7,0,1,2,5,4,6时

image-20230524192918248
image-20230524192918248

什么叫cache的一致性问题

一般情况下，Cache中存放的是主存的部分副本，因此，Cache块应该与相应主存块的内容保持一致。但是在某些情况下，Cache块与相应主存块的内容会不相同，也就是产生了Cache的一致性问题。

  • 多Cache的一致性问题

每一个处理机都有自己专用的Cache，但主存中同一个信息块在多个Cache中都有时，会出现信息不一致情况

写直达法----保证一个

进程迁移----将一个尚未执行完而被挂起的进程调度到另一个空闲的处理机上去执行

对于进程迁移的Cache不一致性----禁止进程迁移

第五章 标量处理机

什么叫做流水线的瓶颈段，怎么解决瓶颈端，简答

定义：流水线各段执行时间不相等

解决：

  1. 细分瓶颈段
  2. 重复设置瓶颈段（增加分配器和收集器）（二是将瓶颈子过程多套并联）

非流水线的时空调度 10分

第五章绝对有大题，要把作业做会，期中考试也有可以做，画时空图，计算几个性能指标，求冲突向量，禁止表等

时空图

性能指标：

  • 吞吐率

各段执行时间相等，输入连续任务情况下：

吞吐率公式：$ T P = n / (k+n-1) \Delta t$ （n为任务数，$T_k$为完成n个任务所用的时间。k 为流水线的段数，$\Delta t$为每个功能子段的执行时间（也称为1拍））

最大吞吐率：$ T P = \displaystyle \lim^{}_{n \to \infty} n / (k+n-1) \Delta t = 1/\Delta t$

image-20230522152613663
image-20230522152613663
  • 加速比
image-20230522153259500
image-20230522153259500
  • 效率
image-20230522153932513
image-20230522153932513

禁止表与冲突向量

image-20230522161921583image-20230522162020009image-20230522162058723image-20230522162139622

延迟禁止表：对预约表中每一行取差，得到一组数，再对这组数去重即可得到延迟禁止表

冲突向量：找出禁止表中最大的数，代表冲突向量的二进制位数，然后根据禁止表中的数在冲突向量的相应位数取一其余补零（从右往左取）。

流水状态图：

  1. 求状态转移

    1. 求出初始状态状态转移（看冲突向量中0的位数（从右往左数），当前状态先右移0的位数，再或上冲突向量，重复操作得到初始状态的转移（我这里简称一级状态）

    2. 对一级状态重复上述操作，得到二级，以此类推

  2. 画状态转移图

    1. 根据状态转移，画出状态转移图

  3. 调度方案：从初始向量出发最后回到初始向量或者在新的向量循环

    1. 根据状态转移图，写出调度方案以及对应的平均延迟
    2. 求最小平均延迟（单位：拍），以及最大吞吐率（1/最小平均延迟）（单位：任务/拍）

  4. 流水时空图、实际吞吐率、效率

    1. 根据预约表画出流水时空图
    2. 实际吞吐率：（看时间轴也就是x轴，时间/总时间）
    3. 效率：（面积/总面积）

示例：

image-20230525152047035
image-20230525152047035

第六章 向量处理机

@6-2 简答or选择

CRAY-1向量流水处理

解题思路：

  1. 记
    1. 相加6拍
    2. 相乘7拍
    3. 求倒数（除）14拍
    4. 存储器读数6拍
    5. 打入寄存器及启动功能部件各一拍
  2. 并行、链接、串行
    1. 并行：相邻各个指令之间没有联系（功能部件或指令没有相同）
    2. 链接：只要不出现功能部件和Vi冲突，有“先写后读”的向量指令可以采用链接方式执行
    3. 串行：出现功能部件或Vi冲突
  3. 区别
    1. 链接和并行可以看做一个整体只需要加一次(N-1)；每一个串行的指令都需要加 (N-1)，N为向量长度；
    2. 并行指令可以同时执行，取最长时间（拍）

Vi冲突：并行工作的各向量指令，源向量或结果向量使用了相同的Vi

例如：V4 <- V1 + V2
      V5 <- V1 ^ V2            ^ 表示任何操作

功能部件冲突：同一个功能部件被要求并行工作的多条指令所使用

例如：V3 <- V1 + V2
      V6 <- V4 + V5

链接方式：只要不出现功能部件和Vi冲突，有“先写后读”的向量指令可以采用链接方式执行

image-20230529134211222
image-20230529134211222

6.3 可能有画图 10分

ILLIAC IV 阵列机传递信号

步骤：

  1. 画出互联结构图
  2. 第一步看与他直接相连的处理器，剩下以此类推。

示例

6-3 画出 16 台处理器仿 ILLIAC IV的模式进行互连的互连结构图，列出 PE。分别只经一步、二步和三步传送，就能将信息传送到的各处理器号。

image-20230531185448451
image-20230531185448451

书p234 6-5 考

Cube 立方体置换

image-20230529175044088
image-20230529175044088

PM2I 置换

image-20230529180523615
image-20230529180523615

Shuffle 混洗交换单级网络

image-20230529180635428
image-20230529180635428

第7章 多处理机

10分综合题 参考作业 7-7 7-8

并行性分析 FORK JOIN 时间关系图

FORK JOIN：

  1. 先画依赖图（）
  2. 根据依赖图写FORK JOIN

时间关系图：

  1. 看题目条件（几个处理机/CPU）根据FORK JOIN来画
  2. FORK结束时，会在空闲CPU打开新的任务（第一个任务会在当前CPU执行，第二个会在空闲CPU上执行）
  3. 对比不同CPU处理任务的时间，时间短的会被优先释放

（1）数据相关

如果Pi的左部变量在Pj的右部变量集内，且Pj数据相关于Pi，例：

​ Pi: A=B+D

​ Pj: C=A*E

Pi，Pj不能并行，也不能交换执行次序

（2）数据反相关

如果Pj的左部变量在Pi的右部变量集内，例：

​ Pi: C=A+B

​ Pj: A=D+E

方案：每个P的操作结果先暂存于自己的局部存储器中，不急于去修改原来存放在共享主存中单元的内容，要求局存向共享主存写同步。 Pi，Pj 可并行，不能交换串行

（3）数据输出相关

如果Pi的左部变量和Pj的左部变量相同，例：

​ Pi: C=A+B

​ Pj: C=D+E

只要保证Pi先写，Pj后写， Pi，Pj 即可并行

并行性程序设计语言

派生：FORK 汇合：JOIN

FORK m：派生出标号为m开始的新进程。

  • 准备好新进程启动和执行的必须信息

  • 将空闲处理机分配给派生的新进程，如没有空闲的处理机，则进程排队等待

  • 继续在原处理机上执行FORK m语句的原进程

JOIN n：

  • 附有计数器，初值为0

  • 执行一次JOIN语句，计数器加1，并与n比较

  • 如相等，则允许进程通过JOIN语句，计数器清0，进程继续执行。

  • 若不等，则执行JOIN语句的进程结束，释放处理机。

7.9也可以看看

结尾

ps 例如6.3是参考PPT， 6-3则是书上题目

我按照上课听的课随便写的，只有大题应该是全的，小题没咋讲，还是多看看PPT啥的，大题作业基本都是考试范围，可以去把作业做做