计算机考研复试之计算机系统结构（上）数据结构与算法小帜的打怪升级之路-

/*前言：计算机系统结构和计算机组成原理有着高度相似之处，尤其是存储系统和输入输出系统。因此本篇博客将计算机系统结构的面试问题分为上下两篇，上篇包含计算机系统结构导论、指令系统和流水线技术；下篇包含存储系统和输入输出系统。下篇博客的学习，我会综合计算机组成原理、计算机系统结构和操作系统的相关部分进行整理。本人专业水平有限，文章如有错误，请您批评指正；若对您的学习与备考有帮助，可以关注、、，谢谢~*/

/**************************计算机系统结构导论***********************/

问题一：从计算机语言的角度看，可将计算机系统划分为多层次结构，由低级到高级分别是什么？

微程序机器级、传统机器语言机器级、操作系统机器级、汇编语言机器级、高级语言机器级、应用语言机器级。

问题二：实现软件可移植性有哪些基本途径？

1. 统一高级语言：难度较大，目前只能做到相对统一
2. 采用系列机：必须保证做到向后兼容（指的是出厂时间顺序），力争做到向上兼容（指的版本）
3. 模拟和仿真：模拟和仿真的区别是，模拟用机器语言程序解释指令，其解释程序存储在主存中。仿真是用微程序解释指令，其解释程序存储在控制存储器中。

补充：模拟技术中，当两者机器语言语义差别较大时，会使解释程序速度下降；模拟技术中，采用的是微程序，由于微程序依赖于计算机系统结构，当两者系统结构差别较大时，就很难通过仿真来移植软件。

问题三：提高并行性的技术途径有哪些？

1. 时间交叉：让多个处理过程在时间上错开，交叉轮流的使用同一套硬件设备的各个部分。如：流水线技术。
2. 资源重复：通过重复设置资源，尤其是硬件资源，来提高系统性能。如：双工系统、相联处理机、阵列处理机。
3. 资源共享：通过提高系统资源利用率来提高系统性能。如：多道程序分时系统。

问题四：多机系统的耦合度包括哪些？

1.最低耦合2.松散耦合3.紧密耦合

问题五：弗林（Flynn）分类法把计算机系统分为哪些类？

首先应明确，弗林分类法是依据指令流和数据流的多倍性来进行划分的。多倍性指：在系统最受限制的部件上，同时处于同一执行阶段的指令或数据的最大可能个数。

弗林分类法将计算机系统分为四类：

1. 单指令流单数据流（SISD）：传统的按顺序执行指令的单处理机
2. 单指令流多数据流（SIMD）：阵列处理机、流水处理机
3. 多指令流单数据流（MISD）：宏流水和脉动阵列机
4. 多指令流多数据流（MIMD）：能全面实现并行任务的多处理机系统

问题六：简述一下什么是Amdahl定律。

用加速比来衡量系统采用的改进措施对系统性能提高的程度。

加速比S=T0/Tn。T0指系统改进前的执行时间，Tn是系统改进后的执行时间。

结论：具有高性能加速比的计算机系统应该是一个整体性能优化平衡的系统，而不应追求个别部件的高性能。

补充：衡量计算机性能的唯一可靠标准是机器真正执行程序的时间。

/*****************************指令系统*******************************/

问题七：什么是数据类型？什么是数据表示？

数据类型是指计算机系统中可以使用和处理的数据的类型。如：整数、浮点数、字符、数组、链表、栈、树 等等。

数据表示是指可以被计算机硬件直接识别，可以被指令系统直接使用的数据类型。

问题八：常见的编址单位有哪些？

1. 字编址：每个编址单位和访问的数据存储单元相一致。
2. 字节编址：每个编址单位都是一个字节。
3. 位编址：每个编址单位都是一个二进制位。

问题九：按指令的寻址空间来分，寻址方式有哪几种？

1. 立即数寻址：直接在指令的地址码部分给出操作数。
2. 寄存器寻址：寻址空间是通用寄存器，速度快。
3. 主存寻址：寻址空间是主存，又包含间接寻址和变址寻址等寻址方式。
4. 堆栈寻址：堆栈操作指令没有地址码部分。

问题十：操作码优化设计的方式有那几种？

1. 定长编码：所有指令操作码长度都相等，如果需要编码的操作码有N个，则至少需要操作码的位数是log2N位（向上取整）。
2. 哈弗曼编码：采用哈夫曼算法构造哈夫曼树来进行编码。（哈夫曼树的形式往往不唯一，但是计算平均码长时数值唯一）
3. 扩展编码：又分为码长表示法和码点数表示法。

问题十一：操作码优化设计的评价方法是什么？

用平均码长来评价编码优化的程度，平均码长公式为L=∑Pi*Li。其中Pi是编码码点i的使用频度，Li是码点i的编码长度。（这个可类比数据结构中哈夫曼树求WPL，就是将节点权值*路径长，最终求和得WPL，道理一样的）

问题十二：设计精简指令系统计算机（RISC）的设计原则是什么？有哪些优点和缺点。

RISC的设计原则是：

① 精简指令条数，保留使用频度较高的指令；

② 简化指令格式，采用简单寻址方式，绝大多数指令可以单周期执行完成；

③ 扩大通用寄存器数量，只允许 Load 指令和 Store 指令可以访存；

④ 指令以组合电路实现为主，少量指令可用微程序解释方式实现；

⑤ 优化编译程序的设计。

优点：简化了指令系统；提高了机器的运行速度和效率；降低系统成本，提高了可靠性。

缺点：加重了汇编语言程序的负担；增加了目标程序占用的存储空间。

问题十三：设置一种浮点数据表示方式需要确定哪些参数？

1.尾数的基的值2.尾数的值的数制和码制3.阶码的基的值4.阶码的值的数制和码制5.尾数长度6.阶码长度

问题十四：用扩展编码方法对操作码编码时，怎样才能保证编码的唯一性？

根据要求编码的短码个数和长码个数，留下若干个短码码点作为长码码点的扩展标志，才能使所有的短码码点的编码不是长码码点的前缀，从而保证各指令操作码编码的惟一性。

/*************************流水技术和流水处理机*************************/

问题十五：指令交叉执行时会产生冲突，那么如何解决冲突？

1. 提高存储系统频宽，使存储系统的工作速度同CPU的速度匹配。
2. 先行控制技术，它又可细分为缓冲技术和预处理技术。

问题十六：按流水技术用于系统的等级不同，流水线可分为哪几种？

1. 部件级流水线：由部件内各子部件组成，又称为运算操作流水线
2. 处理机级流水线：指部件之间的流水线，如指令流水线
3. 系统级流水线：指处理机之间的流水线，又称为宏流水线

问题十七：流水线按照功能划分，有几种？

1. 单功能流水线：只能完成一种固定功能的流水线
2. 多功能流水线：流水线可通过不同的连接实现不同的功能。对多功能流水线细分，又有①静态流水线：指同一时间段内只能实现一种连接，从而实现一种功能。只有按照此种连接处理的对象都流出流水线后，才能切换连接方式，实现另一种功能。②动态流水线：同一段时间内，各段的连接方式可以改变，从而并发执行多种功能。

问题十八：反映流水线性能的指标有哪些？（注意：这里涉及到了它们的计算公式，面试虽然不会考查公式计算，但是这种题出笔试一定会涉及利用公式计算三者）

1. 吞吐率：指流水线单位时间输出的处理结果的数量。（细节：吞吐率取决于瓶颈段执行时间）消除瓶颈段来提高吞吐率可采用方法1.将瓶颈段再细分2.多个瓶颈段并联。

Ps:改造瓶颈段主要提升的是吞吐率，但是由于重复设置了设备，因此效率不见得能提升。

1. 加速比：一批处理对象采用顺序执行的方式花的时间t0与采用流水线技术花的时间t1的比值。
2. 效率：有效工作时间之和/占用工作时间之和

重点注意：以上三性能采用公式计算，一定有个前提，处理对象是连续流入且流水线是线性的；如果不是，三性能只能采用时空图来计算。

问题十九：非线性流水线调度要解决的问题是什么？

确定控制处理对象流入流水线的时间间隔，使其既不发生对象争用流水线段的冲突，又有较高的吞吐率和效率。（注，这里常提到一个概念：最优调度策略。是指能使非线性流水线获得最大实际吞吐率的调度策略）

问题二十：单功能非线性流水线最优调度算法步骤是什么？（计算题重点题型）

1. 根据处理对象对流水线各段的使用时间要求建立一个预约表。
2. 由预约表得出禁止表。（禁止表是禁止后续对象流入流水线的时间间隔的集合）
3. 由禁止表得出初始冲突向量。
4. 由初始向量得出状态有向图。
5. 由状态有向图得出最优调度策略。（状态有向图中任意一条环路都是一个可用的无冲突的策略，从中选择一个平均时间间隔最短的策略就是最优调度策略）

问题二十一：流水线的相关指的什么？分别有哪些相关？

流水线的相关即冲突问题，可分为局部相关和全局相关。

局部相关主要有“先写后读”相关、“先读后写”相关和“写-写”相关，这些相关问题和流水线的安排与控制有关。在顺序流动中，会发生“先写后读”相关。解决顺序额流动中的“先写后读”相关有两种方式1.延时（暂停读段指令及其后的指令流动，直到写段指令完成写操作后才继续流动）2.异步流动（让后面的指令可依次越过该指令继续向前流动）。

但是异步流动又会产生新的问题，会发生“写-写”相关和“先读后写”相关。解决的办法也有两种1.延时2.建立相关专用通路。

Ps:“写-写”相关和“先读后写”相关不可能发生在顺序流动流水线中。

全局相关有1.条件转移全局相关（可采用猜测法，然后设置大量寄存器来判断）2.中断（可用精确断点发或者不精确断点法解决）

问题二十二：多发射处理机有哪几种，分别解释一下

多发射处理机有：超标量处理机、超流水处理机、超标量超流水处理机、超长指令字处理机

超标量处理机是在单发射流水处理机基础上，采用资源重复技术，提高空间并行性来提升处理机的指令级并行度（ILP）的。

超流水处理机是在单发射流水处理机的基础上，采用时间交叉途径，提高时间并行性来提高处理机的 ILP 的。

超标量超流水处理机：结合以上两种技术

超长指令字处理机：把一个足够长的指令字分割成多个短指令字，每个短指令都可以独立地控制各自的运算器和寄存器。因此，超长指令字处理方式也是一种多发射处理方式，一个时钟周期解释一条超长指令。

问题二十三：什么是向量处理方式？哪些方式适合流水处理机处理向量？

标量处理方式指使用标量指令处理标量数据，一条指令只能处理一个或者一对标量数据；向量处理指用向量指令处理向量数据，一条向量指令能同时并行处理相同类型的多个或多对标量数据。向量处理方式有三种1.横向处理2.纵向处理3.纵横处理（组内纵向，组间横向）

其中纵向处理和纵横处理适用于流水处理机。

/*上篇到此结束，由于个人计划安排，我会先进行数据结构&算法和计网的复习，本篇的下篇我将尽快更新发布（三天左右），可关注我，第一时间追踪到我的更新*/