题库
分析论述题
- 指令级并行、数据级并行、线程级并行的思想和发展历程 （L05-P5~ 、L06-P32？书本P296为L06-P2~3中文翻译）
指令级并行，线程级并行，数据级并行区别？
数据级并行
指令级并行（Instruction Level Parallel，ILP）是指指令之间存在的一种并行性，利用它计算机可以并行执行两条或以上的指令。
数据级并行（Data Level Parallel，DLP）是指处理器能够同时处理多条数据，属于SIMD模型，即单指令流多数据流模型。
线程级并行（Thread Level Parallel，TLP）是指多个线程以重叠的方式共享一个单独处理器的功能单元。
自20世纪80年代中期依赖，随着微处理器的发展，单处理机的性能高速增长；但近些年来由于功耗问题和ILP开发空间缩小等问题，人们开始将视角转向多处理机的开发；还有一个问题是ILP本身也不再适应当代数据密集型计算的变化，难以有效利用ILP技术提升性能。 所有能够更有效地进行大规模计算的数据级并行技术和开发并行代价更小的线程级并行技术就此出现。
- 同时多线程的产生原因和拥有技术 （L06-P30~31 、书本P325绿线）
原因：现代多流出处理器通常含有多个并行的功能单元，而单个线程不能有效地利用这些功能单元。而且，通过寄存器重命名和动态调度机制，来自各个独立线程的多条指令可以同时流出，而不用考虑他们之间的相互依赖关系。
拥有技术：是一种在多流出、动态调度的处理器上同时开发线程级并行和指令级并行的技术，是多线程技术的一种改进。
- 线程切换画图分析或文字描述 （五个图 L06-P44、书本P325~326）
L06-P44
第一张图片可以看出，在不支持多线程的处理器中，由于缺乏足够的指令集并行而限制了流出槽的利用率，而且有严重的停顿，若出现Cache不命中的情况将导致整个处理器处于空闲状态。
图片能较好地说明了多线程和同时多线程在提高性能方面的潜在优势。
- 传统摩尔定律和新摩尔定律的定义，以及为何有这样的变化 （L01、L02-P19）
出题形式：根据给出的图表分析，如这条曲线符合摩尔定律中的…参考
摩尔定律：集成电路芯片上所集成的电路的数目，每隔18个月就翻一番。微处理器的性能每隔18个月提高一倍，而价格下降一倍。
新摩尔定律：未来计算机硬件不会更快，但会更“宽”。
为啥有这样的变化：因为功耗问题、存储与CPU的发展脱节以及ILP开发空间减小的原因导致单核处理器时代的终结，和多核、众核时代的到来。
- 单核处理器时代的终结，即回答单核所遇到的问题 （L02-P17~，书本P1画绿线）
Power Wall /功耗+ILP Wall /指令集并行+Memory Wall/内存上升与CPU脱节
大功耗问题；可以进一步有效地开发的指令集并行性已经很少；存储器访问速度的提高缓慢。
- 单核到多核的发展曲线，ppt后面画的一些图，能看出有啥意义（L02-P3~）
- 什么是MPP、SMP、机群 （L10）(书本P329)
SMP只需回答是对称式…共享机即可
MPP：大规模并行处理机Massively Parallel Processor
SMP：对称式共享存储器多处理机Symmetric shared-memory MultiProcessor
机群:是一种价格低廉、易于构建、可扩放性极强的并行计算机系统。它由多台同构或异构的独立计算机同构高性能网络或局域网互联在一起，协同完成特定的并行计算任务。
- Flynn分类、Johnson扩展的图像理解及划分依据 （L10-P11~12、P47）
需要理解Flynn-Johnson classification及其意义
参考书 P3-1.2.1.4
Flynn分类是按照指令流和数据流的多倍性进行分类的。多倍性指的是在系统最受限的部件上，同时处于统一执行阶段的指令或数据的最大数目。
Flynn分类把计算机系统的结构分为SISD、SIMD、MISD和MIMD四类，其中SISD是传统的顺序处理计算机，SIMD以阵列处理机为代表，MISD只是一种人为划分，没有成行机器，多处理机属于MIMD结构。
MIMD之所以流行是由于他的灵活性和高性价比。
Johnson扩展 PPTL10-P47，和MIMD的通信机制与存储器类型有关。Global Memory共享型存储、Distributed M分布式存储、Shared Variables是共享变量、Message Passing是消息传递
分析论述题主要是关于并行和论述发展趋势两方面
简答题和概念题
- 计算机系统结构定义 （L01）
有经典定义和宽泛定义两种：经典的定义是阿姆达尔给出的；宽泛的定义就是抽象层定义。
参考书 P2-1.2.1.2
经典定义：计算机系统结构是指机器语言程序员所看到的计算机属性，即概念性结构与功能特性。计算机系统结构的实质是确定计算机系统中软硬件的界面，界面之上是软件实现的功能，界面之下是硬件和固件实现的功能。
宽泛定义：囊括计算机设计的3个方面：指令系统结构，组成，硬件。
除了经典定义，还加入了计算机组成和计算机实现。
- MIMD的两种通信机制 （L10-P32、书本P298）
Flynn分类里面的多指令流多数据流处理器
共享存储器通信机制：处理器之间是通过load和store指令对相同存储器地址进行读写操作来实现的。对应共享地址空间的存储系统结构计算机。
消息传递通信机制：根据简单的网络协议，通过传递消息来请求某些服务或传输数据，从而完成通信。对应采用多个独立地址空间的计算机系统。
- MIMD的两种memory系统结构 （L10-P32、书本P298）
第一种方案（共享式）：把物理上分离的所有存储器作为一个统一的共享逻辑空间进行编址，系统中只有唯一的地址空间，所有的处理器共享该地址空间。
第二种方案（分布式）：每个处理器有自己的存储器，该存储器只能被该处理器访问而不能被其它处理器直接访问，这种存储器称为局部存储器或私有存储器。
- 向量机定义和优势 （L09-P6 、书本P94）
向量机定义：设置了向量数据表示和向量指令的流水线处理机。
优势：流水线适合于进行大批量重复且没有直接关联的计算，科学计算领域内的很多运算都可以表示向量的运算。
- RAID定义及其作用，以及RAID1、4、5、6的特点 （L08-P42/46/48/50）
包括P37、P38需要理解，知道RAID1-6的变化意义和读写特点，参考
RAID：廉价磁盘冗余阵列Redundant Arrays of (Inexpensive) Disks
在磁盘阵列中设置冗余信息以解决可靠性下降问题，当单个磁盘失效时，丢失的信息可以通过冗余盘中的信息重新构建。
RAID1：镜像磁盘，优点读性能好、缺点在于实现成本过高。
RAID4：数据以块（块大小可变）交叉的方式存于各盘， 奇偶校验信息存在一台专用盘上，读取操作每次只需访问数据所在的磁盘，仅在磁盘出现故障时，才会去读校验盘，并进行数据的重建。对于写入操作，差不多需要访问所有的磁盘，以读出旧值来重新计算校验码。
RAID5：数据以块交叉的方式存于各盘，无专用冗余盘，奇偶校验信息均匀分布在所有磁盘上。读写特点和RAID4差不多的样子。
RAID6：在RAID的基础上增加了一个独立校验信息，放在另一个校验盘中。写入数据需要访问一个数据盘和两个冗余盘。存储开销是RAID5的两倍，RAID6的写过程需要6次磁盘操作（3读3写）。
- 存储器层次架构的依据和意义 （L07 书本P188）
主存-辅存层次和Cache-主存层次（参考书P142 题5.28）
依据
程序访问的局部性原理：对于绝大多数程序来说，程序执行时所访问的指令和数据在地址上不是均匀分布地，而是相对地簇聚，包括空间局部性和时间局部性。
时间局部性指程序即将用到的信息可能是目前正在使用的信息，如循环；
空间局部性指程序即将用到的信息很可能与目前正在使用的信息在存储空间上相邻或临近。
意义
为了实现价格合理的同时，速度和容量都满足计算机系统要求的存储器系统，也就是要“容量大、价格低”，也要满足计算机性能需求。
- 指令集架构的类型，主要是load-store型存储结构 （L03-P3~12）
CPU中用来存操作数的存储单元主要有堆栈、累加器、通用寄存器组三种，所以可以讲指令集结构分为堆栈型结构、累加器型结构、通用寄存器型结构。
在通用寄存器结构中，根据ALU指令操作数来源的不同，又可以进一步分为寄存器-存储器型（RM）、寄存器-寄存器型（RR）以及存储器-存储器（MM）结构，RR结构也称为load-store结构。
- 堆栈：操作数隐式，即堆栈栈顶和次栈顶的数据，运算结果写入栈顶。
- 累加器：一个操作数隐式，即累加器，另一个操作数显式给出，结果送回累加器。
- 通用寄存器：两个操作数都显式给出。
- 流水线的定义和特征 （L04）
流水线、流水段、深度、瓶颈等等，大致背，能表达出来即可，基本上出选择或判断
参考书 P39-3.2.2.1、书本P54
流水线：讲一个重复的时许过程分解成若干个子过程，而每个子过程都可有效地在其专用功能段上与其他子过程同时执行；
流水段：流水线中每个子过程及其功能部件称为流水线的段(级)，段与段相互连接形成流水线；
深度：流水线的段数称为流水线的深度；
瓶颈：流水线中时间最长的段。
特点
1、流水线实际上是把一个大的处理部件分解成多个独立的功能部件，并依靠他们的并行工作来提高吞吐率；
2、流水线中隔断的时间应尽可能相等，否则将引起流水线堵塞和断流；
3、流水线每个段后面都要设置一个缓冲寄存器（锁存器），称其为流水寄存器；
4、流水线技术适合于大量重复的时许过程；
5、流水线需要有通过时间和排空时间，分别指第一个任务和最后一个任务从进入流水线到流出结果的那个时间段，在这两个时间段内流水线不能满负荷工作。
- 流水线定向技术的定义和作用 （L04）
定义：在发生写后读冲突的情况下，在计算结果尚未出来前，后面等待使用该结果的指令并不真正立刻就要用到该结果。因此只要将结果数据从其产生的地方直接传送到所有需要它的功能部件，就可以避免冲突。
作用：解决RAW冲突，减少数据冲突引起的停顿。
- 流水线暂停的定义和特点 （L04-P38、书本P75）
定义：为了消除冲突，可以前一条指令将流水线停顿一个时钟周期，推迟指令的操作。该停顿周期往往被称为“气泡”，也就是“暂停”。
特点：当一条指令被暂停时，在该暂停指令之后流出的所有指令都要被暂停，而在该暂停指令之前流出的指令则继续进行。显然，在整个暂停期间，流水线不会启动新的指令。
- 流水线的3种冲突、3种数据冲突（L04-P41、45~47）和3种相关的定义以及冲突与相关的关系 （L05-P8、P12、P9）
流水线的三种冲突
··结构冲突 Structural Hazard：因硬件资源满足不了指令重叠执行的要求而发生的冲突；
··数据冲突 Data Hazard：当指令在流水线中重叠执行时，因需要用到前面指令的执行结果而发生的冲突；
··控制冲突 Control Hazard：流水线遇到分支指令或其他会改变PC值的指令所引起的冲突。
三种数据冲突
··写后读冲突 RAW：指令j用到指令i的计算结果，在i将结果写入寄存器之前就去读该寄存器，因而得到的是旧的值。
··写后写冲突 WAW：指令j和指令i的结果寄存器相同，在i将结果写入寄存器之前就将结果写入寄存器，因此寄存器中最终存的结果是i的结果而非正确的j的结果。
··读后写冲突 WAR：指令j的计算结果被指令i用到的寄存器相同，在i读取使用该寄存器之前，指令j就将结果写入该寄存器，导致i读取到的值是错误的。
三种相关
··数据相关：若两条指令i、j数据相关，则表明指令j使用了指令i的结果，或者指令j与指令k数据相关，指令k由于指令i数据相关。
··名相关：若两条指令名相关，则代表指令i、j有以下两种情况，（反相关）指令i所读的名和指令j所写的名相同/（输出相关）指令j和指令i所写的名相同。与数据相关不同，名相关的两条指令之间没有数据流动。
··控制相关：指由分支指令引起的相关。与一条分支指令控制相关的指令不能被一道该分支之前，否则这条语句就不受该分支控制了；如果一条指令和某分支指令不存在控制相关，就不能把该指令一道该分支指令控制范围内。
相关和冲突的关系
相关性是程序的特性；冲突是流水线结构的特性；
相关性的存在只预示着存在有冲突的可能性。
- 吞吐率、最大吞吐率和实际吞吐率的定义 （L04-P22）
参考书 P40-3.2.3.1
吞吐率TP：在单位时间内流水线所完成的任务数量或输出结果的数量。
最大吞吐率：
- 三种映像策略的定义及特点 （L07-P17~18 书本P193）
全相联映像 Fully Associative ：主存中的人一块可以被放置到Cache中的任意一个位置。
特点：空间利用率最高，冲突概率最低，实现最复杂。
直接映像 Direct Mapping ：主存中的每一块只能被放置到 Cache中唯一的一个位置。
特点：空间利用率最低，冲突概率最高，实现最简单。
组相联映象 Set Associative ：主存中的每一块可以被放置到Cache中唯一的一个组中的任何一个位置。
特点：组相联是直接映象和全相联的一种折衷，组的选择常采用位选择算法。
- 替换算法及种类 （L07-P25 书本P198）
替换算法定义：当要从主存中调入一个块到Cache中，出现该块所映像到的Cache块（一个或一组）已全被占用的情况时，需要选择其中的一块用新调入的块取而代之，替换算法指的是被替换块的选择算法。
种类：直接映像Cache中的替换很简单，因为只有一个块没有选择；而在组相连映像和全相联映像Cache中有多个快，有三种替换算法：
··随机法：随机算泽被替换的块，优点简单易于实现，缺点是没有考虑Cache块过去被使用的情况，反映不了程序局部性，命中率低；
··FIFO先入先出算法：选择最早调用的块作为被替换的块，优点易于实现，缺点还是不能正确反映程序的局部性；
··LRU最近最少使用法：选择近期使用次数最少的块作为被替换的块，优点是能较好地反映程序的局部性原理，缺点是比较复杂，硬件实现成本高。
- 写策略（L07-P27、书本P202）
绕Cache写还是…，组合使用，理解意义和作用
当处理机往Cache中写数据时，Cache和主存内容的一致性容易被破坏，为了保证正确性，用写策略来解决主存内容更新的时间。
··写直达Write Through：指在执行“写”操作时，同时将数据写入Cache中相应的块和下一级存储器中，保证下一级存储器中的数据始终最新；
··写回法Write Back：只将数据写入Cache中相应的块，只有当相应块被替换的时候，才被写回下一级存储器中，此时常在Cache每一块设置“修改位”标识，当一个块被替换时，若没有被修改过则不必写回。
当发生写不命中时，是否将数据调入相应的块有两种选择：
··按写分配法Write Allocate/写时取法：写不命中时，先把所写单元所在的块从主存调入Cache，再进行写入；
··不按写分配No-write Allocate/绕写法：写不命中时，直接写入下一级存储器而不将相应的块调入Cache。
虽然上述两种方法都可应用与写直达法和写回法，但写回法Cache一般采用按写分配，而写直达一般采用不按写分配。
L07-P27.png
- 三种Cache失效，就是三种类型的不命中3C （L07 书本P206）
强制性不命中 Compulsory Miss：当第一次访问一个块是该块不在Cache中，需要从下一级存储器中调入Cache，即为强制性不命中
容量不命中 Capacity Miss：程序执行时所需的块不能全部调入Cache中，则当某些快被替换后，若又被重新访问就会发生不命中，称为容量不命中；
冲突不命中 Conflict Miss：在相联或直接映像Cache中，若太多块映像到同一组/块中，则会出现该组/块中某个块被替换后又被重新访问，就发生了冲突不命中。
Reducing Miss Rate
Larger Block size (compulsory misses)
Larger Cache size (capacity misses)
Higher Associativity关联度 (conflict misses)
计算题
- 求CPI、MIPS、程序执行时间（如作业1-1.7）
主要是L02中的计算机性能计算
参考书 P4 、 P18-题1.32~1.34、1.38、1.40
题目中常问的求速率就是求MIPS（每秒处理的百万级的机器语言指令数）
题目常会给出主频，主频是时钟周期时间的倒数；题目中问的程序执行时间就是CPUtime。（计算CyclesPerSecond）
IC：所执行的指令条数
CPI：每条指令的平均时钟周期数
%7D%5C%5C%20%5CRightarrow%20MIPS%20=%5Cfrac%7B%20frequency%7D%7BCPI%5Ctimes%2010%5E6%7D%5C%5C)
- 求吞吐率、加速比、效率，画时空图（如作业2-3.8）
主要是L04中的流水线性能计算，有三个指标；时空图横坐标：时间，纵坐标：段数，时空图如L04-P81那种
参考书 P40-3.2.3.1 吞吐率
(1)吞吐率TP是指在单位时间内流水线所完成的任务数量或输出结果的数量。n为任务数，T_k为处理完成n个任务所用的时间。
(2)各段时间均相等下TP：流水线分为k段，每段用书delta_t。
(3)各段时间不完全相等下实际TP：delta_t_i为第i段时间，一个任务共有k段，坟墓中第一部分是流水线完成第一个任务所用时间，第二部分是完成其余n-1个任务所用时间。
(4)流水线最大吞吐率，所以流水线的最大吞吐率和实际吞吐率都是有时间最长的端决定，也就是流水线的瓶颈。
%20TP=%5Cfrac%7Bn%7D%7BT_k%7D%5C%5C(2)TP=%5Cfrac%7Bn%7D%7B(k+n-1)%5CDelta%7Bt%7D%7D%5C%5C(3)TP=%5Cfrac%7Bn%7D%7B%5Csum_%7Bi=1%7D%5E%7Bk%7D%20%5CDelta%20t_i%20+%20(n-1)%5Ctimes%20max(%5CDelta%20t_1,%20%5CDelta%20t_2,%20%5Ccdots%20,%5CDelta%20t_k)%7D%5C%5C(4)TP_%7Bmax%7D=%5Cfrac%7B1%7D%7Bmax(%5CDelta%20t_1,%20%5CDelta%20t_2,%20%5Ccdots%20,%5CDelta%20t_k)%7D)
参考书 P40-3.2.3.2 加速比 可以看一下P60-题3.35
(1)加速比指的是顺序处理一批人物所用时间T_s与按流水处理方式处理同一批任务所用时间T_k之比。
(2)各段时间相等，都是delta_t，流水线实际加速比。
(3)时间不完全相等时间，实际加速比。
S=%5Cfrac%7BT_s%7D%7BT_k%7D%5C%5C(2)S=%5Cfrac%7Bnk%7D%7Bk+n-1%7D%5C%5C(3)S=%5Cfrac%7Bn%5Csum%5Ek_%7Bi=1%7D%20%5CDelta%20t_i%7D%7B%5Csum%5Ek_%7Bi=1%7D%20%5CDelta%20t_i%20+(n-1)%5Ctimes%20max(%5CDelta%20t_1,%20%5CDelta%20t_2%20,%20%5Ccdots%20,%5CDelta%20t_k)%7D)
参考书 P41-3.2.3.3 效率
流水线的效率即流水线设备的利用率，是指流水线中的设备实际使用时间与整个运行时间的比值。通用一般公式为E=n个任务实际占用的时空区面积/k个段总的时空区面积
(1)如果各段时间相等，则各段的效率是相同的，且都等于整条流水线的效率。
(2)
简答题补充：
为啥时空图效率总小于1：因为不能满负荷使用
为啥不能满负荷使用：因为有通过时间和排空时间（看L04-P22流水线五个阶段）
- 平均存取时间（如作业2-6，书本P203~204，L07-P32、44）
主要是L07中的Cache性能计算的，还有可能考命中率
平均存取时间 = 命中时间 + 不命中率 X 不命中开销
CPU时间 = (CPU执行周期数 + 存储器停顿周期数) X 时钟周期时间
存储器停顿周期数 = 访存次数 X 不命中率 X 不命中开销
=>CPU时间 = IC X (CPI + 每条指令的平均访存次数 X 不命中率 X 不命中开销) X 时钟周期时间
- 阿姆达尔定律题-单部件改进公式和多部件改进公式（L02-P63~）
主要是L02中的阿姆达尔定律的考题，百分之百出，包括增强比例和加速比等
参考书 P3-1.2.2.1(2) 、P12-题1.35~1.37、1.39、
单部件改进公式（1）：
Extime为总执行时间；Fraction_enhanced为部件可改进比例，例：该部件的处理时间占整个系统的运行时间的百分之40，则F = 0.4；Speedup_enhanced为部件加速比，例：将某一功能的处理速度加快10呗，则S = 10。
多部件改进公式（2）
%20+%20%5Cfrac%7BFraction_%7Benhanced%7D%7D%7BSpeedup_%7Benhanced%7D%7D%20%5Cright%20%5D%20%5Cend%7Bcases%7D%5C%5C%20%5CRightarrow%5Cleft%20(%201%20%5Cright)%20Speedup_%7Boverall%7D%20=%20%5Cfrac%7BExtime_%7Bold%7D%7D%7BExtime_%7Bnew%7D%7D%20=%20%5Cfrac%7B1%7D%7B%5Cleft%20(%201%20-%20Fraction_%7Benhanced%7D%20%5Cright%20)%20+%20%5Cfrac%7BFraction_%7Benhanced%7D%7D%7BSpeedup_%7Benhanced%7D%7D%20%7D%20%5C%5C%20%5CRightarrow%20%5Cleft%20(%202%5Cright)%20S_%7Bn%7D%20=%20%5Cfrac%7B1%7D%7B%5Cleft%20(1%20-%20%5CSigma%20F_%7Bi%7D%5Cright)+%20%5CSigma%5Cfrac%7BF_%7Bi%7D%7D%7BS_%7Bi%7D%7D%7D)
- 计算程序并行程度（L10-P102~104）以及远程访问时间影响（L10-P105106、书本-P300-例10.110.2）
老师给出题库没有这道，不过倒数第二节总复习课里面这个老师说打双星（双星意味非常重要），所以还是要看一下
补充
- RISC、CISC
CISC：复杂指令集计算机Complex Instruction-Set Computer
RISC：精简指令集计算机Reduced Instruction-Set Computer
