解释下列术语
层次机构:按照计算机语言从低级到高级的次序,把计算机系统按功能划分成多级层次结构,每一层以一种不同的语言为特征。
这些层次依次为:微程序机器级,传统机器语言机器级,汇编语言机器级,高级语言机器级,应用语言机器级等。
虚拟机:用软件实现的机器。
翻译:先用转换程序把高一级机器上的程序转换为低一级机器上等效的程序,然后再在这低一级机器上运行,实现程序的功能。解释:对于高一级机器上的程序中的每一条语句或指令,都是转去执行低一级机器上的一段等效程序。执行完后,再去高一级机器取下一条语句或指令,再进行解释执行,如此反复,直到解释执行完整个程序。
计算机系统结构:传统机器程序员所看到的计算机属性,即概念性结构与功能特性。
在计算机技术中,把这种本来存在的事物或属性,但从某种角度看又好像不存在的概念称为透明性。
计算机组成:计算机系统结构的逻辑实现,包含物理机器级中的数据流和控制流的组成以及逻辑设计等。
计算机实现:计算机组成的物理实现,包括处理机、主存等部件的物理结构,器件的集成度和速度,模块、插件、底板的划分与连接,信号传输,电源、冷却及整机装配技术等。
系统加速比:对系统中某部分进行改进时,改进后系统性能提高的倍数。
Amdahl定律:当对一个系统中的某个部件进行改进后,所能获得的整个系统性能的提高,受限于该部件的执行时间占总执行时间的百分比。
程序的局部性原理:程序执行时所访问的存储器地址不是随机分布的,而是相对地簇聚。包括时间局部性和空间局部性。
CPI:每条指令执行的平均时钟周期数。
测试程序套件:由各种不同的真实应用程序构成的一组测试程序,用来测试计算机在各个方面的处理性能。
存储程序计算机:冯·诺依曼结构计算机。其基本点是指令驱动。程序预先存放在计算机存储器中,机器一旦启动,就能按照程序指定的逻辑顺序执行这些程序,自动完成由程序所描述的处理工作。
系列机:由同一厂家生产的具有相同系统结构、但具有不同组成和实现的一系列不同型号的计算机。
软件兼容:一个软件可以不经修改或者只需少量修改就可以由一台计算机移植到另一台计算机上运行。差别只是执行时间的不同。向上(下)兼容:按某档计算机编制的程序,不加修改就能运行于比它高(低)档的计算机。
向后(前)兼容:按某个时期投入市场的某种型号计算机编制的程序,不加修改地就能运行于在它之后(前)投入市场的计算机。兼容机:由不同公司厂家生产的具有相同系统结构的计算机。
模拟:用软件的方法在一台现有的计算机(称为宿主机)上实现另一台计算机(称为虚拟机)的指令系统。
仿真:用一台现有计算机(称为宿主机)上的微程序去解释实现另一台计算机(称为目标机)的指令系统。
并行性:计算机系统在同一时刻或者同一时间间隔内进行多种运算或操作。只要在时间上相互重叠,就存在并行性。它包括同时性与并发性两种含义。
时间重叠:在并行性概念中引入时间因素,让多个处理过程在时间上相互错开,轮流重叠地使用同一套硬件设备的各个部分,以加快硬件周转而赢得速度。
资源重复:在并行性概念中引入空间因素,以数量取胜。通过重复设置硬件资源,大幅度地提高计算机系统的性能。
资源共享:这是一种软件方法,它使多个任务按一定时间顺序轮流使用同一套硬件设备。
耦合度:反映多机系统中各计算机之间物理连接的紧密程度和交互作用能力的强弱。
紧密耦合系统:又称直接耦合系统。在这种系统中,计算机之间的物理连接的频带较高,一般是通过总线或高速开关互连,可以共享主存。
松散耦合系统:又称间接耦合系统,一般是通过通道或通信线路实现计算机之间的互连,可以共享外存设备(磁盘、磁带等)。
计算机之间的相互作用是在文件或数据集一级上进行。
异构型多处理机系统:由多个不同类型、至少担负不同功能的处理机组成,它们按照作业要求的顺序,利用时间重叠原理,依次对它们的多个任务进行加工,各自完成规定的功能动作。
同构型多处理机系统:由多个同类型或至少担负同等功能的处理机组成,它们同时处理同一作业中能并行执行的多个任务。
堆栈型机器:CPU 中存储操作数的单元是堆栈的机器。
累加器型机器:CPU 中存储操作数的单元是累加器的机器。
通用寄存器型机器:CPU 中存储操作数的单元是通用寄存器的机器。
CISC:复杂指令集计算机
RISC:精简指令集计算机
寻址方式:指令系统中如何形成所要访问的数据的地址。一般来说,寻址方式可以指明指令中的操作数是一个常数、一个寄存器操作数或者是一个存储器操作数。
数据表示:硬件结构能够识别、指令系统可以直接调用的那些数据结构。
流水线:将一个重复的时序过程,分解成为若干个子过程,而每一个子过程都可有效地在其专用功能段上与其它子过程同时执行。单功能流水线:指流水线的各段之间的连接固定不变、只能完成一种固定功能的流水线。
多功能流水线:指各段可以进行不同的连接,以实现不同的功能的流水线。
静态流水线:指在同一时间内,多功能流水线中的各段只能按同一种功能的连接方式工作的流水线。当流水线要切换到另一种功
能时,必须等前面的任务都流出流水线之后,才能改变连接。
动态流水线:指在同一时间内,多功能流水线中的各段可以按照不同的方式连接,同时执行多种功能的流水线。它允许在某些段正在实现某种运算时,另一些段却在实现另一种运算。
部件级流水线:把处理机中的部件进行分段,再把这些部件分段相互连接而成。它使得运算操作能够按流水方式进行。这种流水线也称为运算操作流水线。
处理机级流水线:又称指令流水线。它是把指令的执行过程按照流水方式进行处理,即把一条指令的执行过程分解为若干个子过程,每个子过程在独立的功能部件中执行。
处理机间流水线:又称为宏流水线。它是把多个处理机串行连接起来,对同一数据流进行处理,每个处理机完成整个任务中的一部分。前一个处理机的输出结果存入存储器中,作为后一个处理机的输入。
线性流水线:指各段串行连接、没有反馈回路的流水线。数据通过流水线中的各段时,每一个段最多只流过一次。
非线性流水线:指各段除了有串行的连接外,还有反馈回路的流水线。
顺序流水线:流水线输出端任务流出的顺序与输入端任务流入的顺序完全相同。
乱序流水线:流水线输出端任务流出的顺序与输入端任务流入的顺序可以不同,允许后进入流水线的任务先完成。这种流水线又称为无序流水线、错序流水线、异步流水线。
吞吐率:在单位时间内流水线所完成的任务数量或输出结果的数量。
流水线的加速比:使用顺序处理方式处理一批任务所用的时间与按流水处理方式处理同一批任务所用的时间之比。
流水线的效率:即流水线设备的利用率,它是指流水线中的设备实际使用时间与整个运行时间的比值。
数据相关:考虑两条指令i和j,i在j的前面,如果下述条件之一成立,则称指令j与指令i数据相关:(1)指令j使用指令i产生的结果;
(2)指令j与指令k数据相关,而指令k又与指令i数据相关。
名相关:如果两条指令使用了相同的名,但是它们之间并没有数据流动,则称这两条指令存在名相关。
控制相关:是指由分支指令引起的相关。它需要根据分支指令的执行结果来确定后面该执行哪个分支上的指令。
反相关:考虑两条指令i和j,i在j的前面,如果指令j所写的名与指令i所读的名相同,则称指令i和j发生了反相关。
输出相关:考虑两条指令i和j,i在j的前面,如果指令j和指令i所写的名相同,则称指令i和j发生了输出相关。
换名技术:名相关的两条指令之间并没有数据的传送,只是使用了相同的名。可以把其中一条指令所使用的名换成别的,以此来消除名相关。
结构冲突:因硬件资源满足不了指令重叠执行的要求而发生的冲突。
数据冲突:当指令在流水线中重叠执行时,因需要用到前面指令的执行结果而发生的冲突。
控制冲突:流水线遇到分支指令或其它会改变PC值的指令所引起的冲突。
定向:用来解决写后读冲突的。在发生写后读相关的情况下,在计算结果尚未出来之前,后面等待使用该结果的指令并不见得是马上就要用该结果。如果能够将该计算结果从其产生的地方直接送到其它指令需要它的地方,那么就可以避免停顿。
写后读冲突:考虑两条指令i和j,且i在j之前进入流水线,指令j用到指令i的计算结果,而且在i将结果写入寄存器之前就去读该寄存器,因而得到的是旧值。
读后写冲突:考虑两条指令i和j,且i在j之前进入流水线,指令j的目的寄存器和指令i的源操作数寄存器相同,而且j在i 读取该寄存器之前就先对它进行了写操作,导致i读到的值是错误的。
写后写冲突:考虑两条指令i和j,且i在j之前进入流水线,,指令j和指令i的结果单元(寄存器或存储器单元)相同,而且j在i写入之前就先对该单元进行了写入操作,从而导致写入顺序错误。这时在结果单元中留下的是i写入的值,
而不是j写入的。
链接技术:具有先写后读相关的两条指令,在不出现功能部件冲突和V i冲突的情况下,可以把功能部件链接起来进行流水处理,以达到加快执行的目的。
分段开采:当向量的长度大于向量寄存器的长度时,必须把长向量分成长度固定的段,然后循环分段处理,每一次循环只处理一个向量段。
R的一半时所需的向量长度。
半性能向量长度:向量处理机的性能为其最大性能
向量长度临界值:向量流水方式的处理速度优于标量串行方式的处理速度时所需的向量长度的最小值。
指令级并行:简称ILP。是指指令之间存在的一种并行性,利用它,计算机可以并行执行两条或两条以上的指令。
指令调度:通过在编译时让编译器重新组织指令顺序或通过硬件在执行时调整指令顺序来消除冲突。
指令的动态调度:是指在保持数据流和异常行为的情况下,通过硬件对指令执行顺序进行重新安排,以提高流水线的利用率且减少停顿现象。是由硬件在程序实际运行时实施的。
指令的静态调度:是指依靠编译器对代码进行静态调度,以减少相关和冲突。它不是在程序执行的过程中、而是在编译期间进行代码调度和优化的。
保留站:在采用Tomasulo算法的MIPS处理器浮点部件中,在运算部件的入口设置的用来保存一条已经流出并等待到本功能部件执行的指令(相关信息)。
CDB:公共数据总线。
动态分支预测技术:是用硬件动态地进行分支处理的方法。在程序运行时,根据分支指令过去的表现来预测其将来的行为。如果分支行为发生了变化,预测结果也跟着改变。
BHT:分支历史表。用来记录相关分支指令最近一次或几次的执行情况是成功还是失败,并据此进行预测。
分支目标缓冲:是一种动态分支预测技术。将执行过的成功分支指令的地址以及预测的分支目标地址记录在一张硬件表中。在每次取指令的同时,用该指令的地址与表中所有项目的相应字段进行比较,以便尽早知道分支是否成功,尽早知道
分支目标地址,达到减少分支开销的目的。
前瞻执行:解决控制相关的方法,它对分支指令的结果进行猜测,然后按这个猜测结果继续取指、流出和执行后续的指令。只是指令执行的结果不是写回到寄存器或存储器,而是放到一个称为ROB的缓冲器中。等到相应的指令得到“确认”(即确实是应该执行的)后,才将结果写入寄存器或存储器。
ROB:ReOrder Buffer。前瞻执行缓冲器。
超标量:一种多指令流出技术。它在每个时钟周期流出的指令条数不固定,依代码的具体情况而定,但有个上限。
超流水:在一个时钟周期内分时流出多条指令。
超长指令字:一种多指令流出技术。VLIW处理机在每个时钟周期流出的指令条数是固定的,这些指令构成一条长指令或者一个指令包,在这个指令包中,指令之间的并行性是通过指令显式地表示出来的。
循环展开:是一种增加指令间并行性最简单和最常用的方法。它将循环展开若干遍后,通过重命名和指令调度来开发更多的并行性。
多级存储层次:采用不同的技术实现的存储器,处在离CPU不同距离的层次上,各存储器之间一般满足包容关系,即任何一层存储器中的内容都是其下一层(离CPU更远的一层)存储器中内容的子集。目标是达到离CPU最近的存储器的速度,
最远的存储器的容量。
全相联映象:主存中的任一块可以被放置到Cache中任意一个地方。
直接映象:主存中的每一块只能被放置到Cache中唯一的一个地方。
组相联映象:主存中的每一块可以放置到Cache中唯一的一组中任何一个地方(Cache分成若干组,每组由若干块构成)。
替换算法:由于主存中的块比Cache中的块多,所以当要从主存中调一个块到Cache中时,会出现该块所映象到的一组(或一个)Cache块已全部被占用的情况。这时,需要被迫腾出其中的某一块,以接纳新调入的块。
LRU:选择最近最少被访问的块作为被替换的块。实际实现都是选择最久没有被访问的块作为被替换的块。
写直达法:在执行写操作时,不仅把信息写入Cache中相应的块,而且也写入下一级存储器中相应的块。
写回法:只把信息写入Cache中相应块,该块只有被替换时,才被写回主存。
按写分配法:写失效时,先把所写单元所在的块调入Cache,然后再进行写入。
不按写分配法:写失效时,直接写入下一级存储器中,而不把相应的块调入Cache。
命中时间:访问Cache命中时所用的时间。
失效率:CPU访存时,在一级存储器中找不到所需信息的概率。
失效开销:CPU向二级存储器发出访问请求到把这个数据调入一级存储器所需的时间。
强制性失效:当第一次访问一个块时,该块不在Cache中,需要从下一级存储器中调入Cache,这就是强制性失效。
容量失效:如果程序在执行时,所需要的块不能全部调入Cache中,则当某些块被替换后又重新被访问,就会产生失效,这种失效就称作容量失效。
冲突失效:在组相联或直接映象Cache中,若太多的块映象到同一组(块)中,则会出现该组中某个块被别的块替换(即使别的组或块有空闲位置),然后又被重新访问的情况。
线路交换:在线路交换中,源结点和目的结点之间的物理通路在整个数据传送期间一直保持连接。
分组交换:把信息分割成许多组(又称为包),将它们分别送入互连网络。这些数据包可以通过不同的路径传送,到目的结点后再拼合出原来的数据,结点之间不存在固定连接的物理通路。
静态互连网络:各结点之间有固定的连接通路、且在运行中不能改变的网络。
动态互连网络:由交换开关构成、可按运行程序的要求动态地改变连接状态的网络。
互连网络:一种由开关元件按照一定的拓扑结构和控制方式构成的网络,用来实现计算机系统中结点之间的相互连接。在拓扑上,互连网络是输入结点到输出结点之间的一组互连或映象。
互连函数:用变量x表示输入,用函数f(x)表示输出。则f(x)表示:在互连函数f的作用下,输入端x连接到输出端f(x)。它反映了网络输入端数组和输出端数组之间对应的置换关系或排列关系,所以互连函数有时也称为置换函数或排列函数。网络直径:指互连网络中任意两个结点之间距离的最大值。
结点度:指互连网络中结点所连接的边数(通道数)。
等分带宽:把由N个结点构成的网络切成结点数相同(N/2)的两半,在各种切法中,沿切口边数的最小值。
对称网络:从任意结点来看,网络的结构都是相同的。
集中式共享多处理机:也称为对称式共享存储器多处理SMP。它一般由几十个处理器构成,各处理器共享一个集中式的物理存储器,这个主存相对于各处理器的关系是对称的,
分布式共享多处理机:它的共享存储器分布在各台处理机中,每台处理机都带有自己的本地存储器,组成一个“处理机-存储器”
单元。但是这些分布在各台处理机中的实际存储器又合在一起统一编址,在逻辑上组成一个共享存储器。
这些处理机存储器单元通过互连网络连接在一起,每台处理机除了能访问本地存储器外,还能通过互连网
络直接访问在其他处理机存储器单元中的“远程存储器”。
通信延迟:通信延迟=发送开销+跨越时间+传输时间+接收开销。
计算/通信比:反映并行程序性能的一个重要的度量。在并行计算中,每次数据通信要进行的计算与通信开销的比值。
多Cache一致性:多处理机中,当共享数据进入Cache,就可能出现多个处理器的Cache中都有同一存储器块的副本,要保证多个副本数据是一致的。
监听协议:每个Cache除了包含物理存储器中块的数据拷贝之外,也保存着各个块的共享状态信息。Cache通常连在共享存储器的总线上,各个Cache控制器通过监听总线来判断它们是否有总线上请求的数据块。
目录协议:用一种专用的存储器所记录的数据结构。它记录着可以进入Cache的每个数据块的访问状态、该块在各个处理器的共享状态以及是否修改过等信息。
写作废协议:在处理器对某个数据项进行写入之前,它拥有对该数据项的唯一的访问权。
写更新协议:当一个处理器对某数据项进行写入时,它把该新数据广播给所有其它Cache。这些Cache用该新数据对其中的副本进行更新。
栅栏同步:栅栏强制所有到达该栅栏的进程进行等待。直到全部的进程到达栅栏,然后释放全部进程,从而形成同步。
旋转锁:处理机环绕一个锁不停地旋转而请求获得该锁。
同时多线程:是一种在多流出、动态调度的处理器上同时开发线程级并行和指令级并行的技术,它是多线程技术的一种改进。
细粒度多线程技术:是一种实现多线程的技术。它在每条指令之间都能进行线程的切换,从而使得多个线程可以交替执行。通常以时间片轮转的方法实现这样的交替执行,在轮转的过程中跳过处于停顿的线程。
粗粒度多线程技术:是一种实现多线程的技术。只有线程发生较长时间的停顿时才切换到其他线程。
SMP:对称式共享存储器多处理
MPP :即大规模并行处理,按照当前的标准,具有几百台~几千台处理机的任何机器都是大规模并行处理系统。
机群:是一种价格低廉、易于构建、可扩放性极强的并行计算机系统。它由多台同构或异构的独立计算机通过高性能网络或局域网互连在一起,协同完成特定的并行计算任务。从用户的角度来看,机群就是一个单一、集中的计算资源。
单一系统映象:包含四重含义。(1)单一系统。尽管系统中有多个处理器,用户仍然把整个机群视为一个单一的计算系统来使用。
(2)单一控制。逻辑上,最终用户或系统用户使用的服务都来自机群中唯一一个位置。(3)对称性。用户可以从
任一个结点上获得机群服务,也就是说,对于所有结点和所有用户,除了那些具有特定访问权限的服务与功能外,
所有机群服务与功能都是对称的。(4)位置透明。用户不必了解真正提供服务的物理设备的具体位置。
高可用性机群:当系统中某些结点出现故障的情况下,仍能继续对外提供服务。它采用冗余机制,当系统中某个结点由于软、硬件故障而失效时,该结点上的任务将在最短的时间内被迁移到机群内另一个具有相同功能与结构的结点上继续执行。负载均衡机群:机群能够根据系统中各个结点的负载情况实时地进行任务分配。它专门设置了一个重要的监控结点,负责监控其余每个工作结点的负载和状态,并根据监控结果将任务分派到不同的结点上。
高性能计算机群:通过高速的商用互连网络,将数十台乃至上千台PC机或工作站连接在一起,可以提供接近甚至超过传统并行计算机系统的计算能力,但其价格却仅是具有相同计算能力的传统并行计算机系统的几十分之一。
Beowulf机群:使用普通的硬件加上Linux操作系统、再加上GNU开发环境以及PVM/MPI共享库所构建的机群。它一方面集中了那些相对较小的机器的计算能力,能够以很高的性能价格比提供与大型机相当的性能,另一方面也保证了软件环境的稳定性。简答题
1.2 试用实例说明计算机系统结构、计算机组成与计算机实现之间的相互关系。
答:如在设计主存系统时,确定主存容量、编址方式、寻址范围等属于计算机系统结构。确定主存周期、逻辑上是否采用并行主存、逻辑设计等属于计算机组成。选择存储芯片类型、微组装技术、线路设计等属于计算机实现。
计算机组成是计算机系统结构的逻辑实现。计算机实现是计算机组成的物理实现。一种体系结构可以有多种组成。一种组成可以有多种实现。
1.3 Flynn分类法是按照指令流和数据流的多倍性进行分类。把计算机系统的结构分为:
单指令流单数据流SISD单指令流多数据流SIMD多指令流单数据流MISD多指令流多数据流MIMD
1.4 计算机系统设计中经常使用的4个定量原理是什么?并说出它们的含义。
答:(1)以经常性事件为重点。在计算机系统的设计中,对经常发生的情况,赋予它优先的处理权和资源使用权,以得到更多的总体上的改进。(2)Amdahl定律。加快某部件执行速度所获得的系统性能加速比,受限于该部件在系统中所占的重要性。(3)CPU性能公式。执行一个程序所需的CPU时间= IC×CPI×时钟周期时间。(4)程序的局部性原理。程序在执行时所访问地址的分布不是随机的,而是相对地簇聚。
1.5 分别从执行程序的角度和处理数据的角度来看,计算机系统中并行性等级从低到高可分为哪几级?
答:从处理数据的角度来看,并行性等级从低到高可分为:
(1)字串位串:每次只对一个字的一位进行处理。这是最基本的串行处理方式,不存在并行性;
(2)字串位并:同时对一个字的全部位进行处理,不同字之间是串行的。已开始出现并行性;
(3)字并位串:同时对许多字的同一位(称为位片)进行处理。这种方式具有较高的并行性;
(4)全并行:同时对许多字的全部位或部分位进行处理。这是最高一级的并行。
从执行程序的角度来看,并行性等级从低到高可分为:
(1)指令内部并行:单条指令中各微操作之间的并行;
(2)指令级并行:并行执行两条或两条以上的指令;
(3)线程级并行:并行执行两个或两个以上的线程,通常是以一个进程内派生的多个线程为调度单位;
(4)任务级或过程级并行:并行执行两个或两个以上的过程或任务(程序段),以子程序或进程为调度单元;
(5)作业或程序级并行:并行执行两个或两个以上的作业或程序。
2.1区别不同指令集结构的主要因素是什么?根据这个主要因素可将指令集结构分为哪3类?
答:区别不同指令集结构的主要因素是CPU中用来存储操作数的存储单元。据此可将指令系统结构分为堆栈结构、累加器结构和通用寄存器结构。
2.2常见的3种通用寄存器型指令集结构的优缺点有哪些?
答:
2.3指令集应满足哪几个基本要求?
答:对指令集的基本要求是:完整性、规整性、高效率和兼容性。
完整性是指在一个有限可用的存储空间内,对于任何可解的问题,编制计算程序时,指令集所提供的指令足够使用。
规整性主要包括对称性和均匀性。对称性是指所有与指令集有关的存储单元的使用、操作码的设置等都是对称的。均匀性是指对于各种不同的操作数类型、字长、操作种类和数据存储单元,指令的设置都要同等对待。
高效率是指指令的执行速度快、使用频度高。
2.4指令集结构设计所涉及的内容有哪些?
答:(1) 指令集功能设计:主要有RISC和CISC两种技术发展方向; (2) 寻址方式的设计:设置寻址方式可以通过对基准程序进行测试统计,察看各种寻址方式的使用频率,根据适用频率设置必要的寻址方式。 (3) 操作数表示和操作数类型:主要的操作数类型和操作数表示的选择有:浮点数据类型、整型数据类型、字符型、十进制数据类型等等。 (4) 寻址方式的表示:可以将寻址方式编码于操作码中,也可以将寻址方式作为一个单独的域来表示。 (5) 指令集格式的设计:有变长编码格式、固定长度编码格式和混合型编码格式3种。
2.5简述CISC指令集结构功能设计的主要目标。从当前的计算机技术观点来看,CISC指令集结构的计算机有什么缺点?
答:主要目标是增强指令功能,把越来越多的功能交由硬件来实现,并且指令的数量也是越来越多。
缺点:(1) CISC结构的指令集中,各种指令的使用频率相差悬殊。(2)CISC结构指令的复杂性带来了计算机体系结构的复杂性,这不仅增加了研制时间和成本,而且还容易造成设计错误。(3)CISC结构指令集的复杂性给VLSI设计增加了很大负担,不利于单片集成。(4)CISC结构的指令集中,许多复杂指令需要很复杂的操作,因而运行速度慢。 (5) 在CISC结构的指令集中,由于各条指令的功能不均衡性,不利于采用先进的计算机体系结构技术(如流水技术)来提高系统的性能。
2.6简述RISC指令集结构的设计原则。
答(1)选取使用频率最高的指令,并补充一些最有用的指令;(2)每条指令的功能应尽可能简单,并在一个机器周期内完成;(3)所有指令长度均相同;(4)只有Load和Store操作指令才访问存储器,其它指令操作均在寄存器之间进行; (5) 以简单有效的方式支持高级语言。
2.7指令中表示操作数类型的方法有哪几种?
答:操作数类型有两种表示方法:(1)操作数的类型由操作码的编码指定,这是最常见的一种方法;(2)数据可以附上由硬件解释的标记,由这些标记指定操作数的类型,从而选择适当的运算。
2.8表示寻址方式的主要方法有哪些?简述这些方法的优缺点。
答:表示寻址方式有两种常用的方法:(1)将寻址方式编于操作码中,由操作码在描述指令的同时也描述了相应的寻址方式。这种方式译码快,但操作码和寻址方式的结合不仅增加了指令的条数,导致了指令的多样性,而且增加了CPU对指令译码的难度。(2)为每个操作数设置一个地址描述符,由该地址描述符表示相应操作数的寻址方式。这种方式译码较慢,但操作码和寻址独立,易于指令扩展。
2.9通常有哪几种指令格式,请简述其适用范围。
答:(1) 变长编码格式。如果系统结构设计者感兴趣的是程序的目标代码大小,而不是性能,就可以采用变长编码格式。(2)固定长度编码格式。如果感兴趣的是性能,而不是程序的目标代码大小,则可以选择固定长度编码格式。 (3) 混合型编码格式。需要兼顾降低目标代码长度和降低译码复杂度时,可以采用混合型编码格式。
2.10根据CPU性能公式简述RISC指令集结构计算机和CISC指令集结构计算机的性能特点。
答:CPU性能公式:CPU时间=IC×CPI×T
其中,IC为目标程序被执行的指令条数,CPI为指令平均执行周期数,T是时钟周期的时间。
相同功能的CISC目标程序的指令条数IC CISC少于RISC的IC RISC,但是CISC的CPI CISC和T CISC都大于RISC的CPI RISC和T RISC,因此,CISC目标程序的执行时间比RISC的更长。
3.2 指令的执行可采用顺序执行、重叠执行和流水线三种方式,它们的主要区别是什么?各有何优缺点。
答:(1)指令的顺序执行是指指令与指令之间顺序串行。即上一条指令全部执行完后,才能开始执行下一条指令
优点:控制简单,节省设备。缺点:执行指令的速度慢,功能部件的利用率低。
(2)指令的重叠指令是在相邻的指令之间,让第k条指令与取第k+l条指令同时进行。重叠执行不能加快单条指令的执行速度,但在硬件增加不多的情况下,可以加快相邻两条指令以及整段程序的执行速度。与顺序方式相比,功能部件的利用率提高了,控制变复杂了。
(3)指令的流水执行是把一个指令的执行过程分解为若干个子过程,每个子过程由专门的功能部件来实现。把多个处理过程在时间上错开,依次通过各功能段,每个子过程与其它的子过程并行进行。依靠提高吞吐率来提高系统性能。流水线中各段的时间应尽可能相等
3.3 简述先行控制的基本思想。
先行控制技术是把缓冲技术和预处理技术相结合。缓冲技术是在工作速度不固定的两个功能部件之间设置缓冲器,用以平滑它们的工作。预处理技术是指预取指令、对指令进行加工以及预取操作数等。
采用先行控制方式的处理机内部设置多个缓冲站,用于平滑主存、指令分析部件、运算器三者之间的工作。这样不仅使它们都能独立地工作,充分忙碌而不用相互等待,而且使指令分析部件和运算器分别能快速地取得指令和操作数,大幅度地提高指令的执行速度和部件的效率。这些缓冲站都按先进先出的方式工作,而且都是由一组若干个能快速访问的存储单元和相关的控制逻辑组成。采用先行控制技术可以实现多条指令的重叠解释执行。
3.4 设一条指令的执行过程分成取指令、分析指令和执行指令三个阶段,每个阶段所需的时间分别为△t、△t和2△t 。分别求出下列各种情况下,连续执行N条指令所需的时间。
(1)顺序执行方式;
(2)只有“取指令”与“执行指令”重叠;
(3)“取指令”、“分析指令”与“执行指令”重叠。
解:(1)每条指令的执行时间为:△t+△t+2△t=4△t
连续执行N条指令所需的时间为:4N△t
(2)连续执行N条指令所需的时间为:4△t+3(N-1)△t=(3N+1)△t
(3)连续执行N条指令所需的时间为:4△t+2(N-1)△t=(2N+2)△t
3.5 简述流水线技术的特点。
(1)流水线把一个处理过程分解为若干个子过程,每个子过程由一个专门的功能部件来实现。因此,流水线实际上是把一个大的处理功能部件分解为多个独立的功能部件,并依靠它们的并行工作来提高吞吐率。
(2)流水线中各段的时间应尽可能相等,否则将引起流水线堵塞和断流。
(3)流水线每一个功能部件的前面都要有一个缓冲寄存器,称为流水寄存器。
(4)流水技术适合于大量重复的时序过程,只有在输入端不断地提供任务,才能充分发挥流水线的效率。
(5)流水线需要有通过时间和排空时间。在这两个时间段中,流水线都不是满负荷工作。
3.6 解决流水线瓶颈问题有哪两种常用方法?细分瓶颈段与重复设置瓶颈段
3.7 减少流水线分支延迟的静态方法有哪些?
答:(1)预测分支失败:沿失败的分支继续处理指令,就好象什么都没发生似的。当确定分支是失败时,说明预测正确,流水线正常流动;当确定分支是成功时,流水线就把在分支指令之后取出的指令转化为空操作,并按分支目标地址重新取指令执行。
(2)预测分支成功:当流水线ID段检测到分支指令后,一旦计算出了分支目标地址,就开始从该目标地址取指令执行。
(3)延迟分支:主要思想是从逻辑上“延长”分支指令的执行时间。把延迟分支看成是由原来的分支指令和若干个延迟槽构成。不管分支是否成功,都要按顺序执行延迟槽中的指令。
3种方法的共同特点:它们对分支的处理方法在程序的执行过程中始终是不变的。它们要么总是预测分支成功,要么总是预测分支失败。
3.10 简述三种向量处理方式,它们对向量处理机的结构要求有何不同?
答 (1)横向处理方式:若向量长度为N,则水平处理方式相当于执行N次循环。若使用流水线,在每次循环中可能出现数据相关和功能转换,不适合对向量进行流水处理。 (2)纵向处理方式:将整个向量按相同的运算处理完毕之后,再去执行其他运算。适合对向量进行流水处理,向量运算指令的源/目向量都放在存储器内,使得流水线运算部件的输入、输出端直接与存储器相联,构成M-M型的运算流水线。 (3)纵横处理方式:把长度为N的向量分为若干组,每组长度为n,组内按纵向方式处理,依次处理各组,组数为「N/n」,适合流水处理。可设长度为n的向量寄存器,使每组向量运算的源/目向量都在向量寄存器中,流水线的运算部件输入、输出端与向量寄存器相联,构成R-R型运算流水线。
3.11 可采用哪些方法来提高向量处理机的性能?
设置多个功能部件,使它们并行工作;采用链接技术,加快一串向量指令的执行;
采用循环开采技术,加快循环的处理;采用多处理机系统,进一步提高性能。
4.2 简述Tomasulo算法的基本思想。
答:核心思想是:①记录和检测指令相关,操作数一旦就绪就立即执行,把发生RAW冲突的可能性减小到最少;②通过寄存器换名来消除W AR冲突和W AW冲突。寄存器换名是通过保留站来实现,它保存等待流出和正在流出指令所需要的操作数。
基本思想:只要操作数有效,就将其取到保留站,避免指令流出时才到寄存器中取数据,这就使得即将执行的指令从相应的保留站中取得操作数,而不是从寄存器中。指令的执行结果也是直接送到等待数据的其它保留站中去。因而,对于连续的寄存器写,只有最后一个才真正更新寄存器中的内容。一条指令流出时,存放操作数的寄存器名被换成为对应于该寄存器保留站的名称(编号)。
5.2简述“Cache—主存”层次与“主存—辅存”层次的区别。
答:
5.3地址映象方法有哪几种?它们各有什么优缺点?
答:(1) 全相联映象。实现查找的机制复杂,代价高,速度慢。Cache空间的利用率较高,块冲突概率较低,因而Cache的失效率也低。(2)直接映象。实现查找的机制简单,速度快。Cache空间的利用率较低,块冲突概率较高,因而Cache的失效率也高。(3)组相联映象。组相联是直接映象和全相联的一种折衷。
5.4常用的降低Cache失效率的方法有下面几种:
(1)增加Cache块大小。增加块大小利用了程序的空间局部性。
(2)增加Cache的容量。
(3)提高相联度,降低冲突失效。
(4)伪相联Cache,降低冲突失效。当对伪相联Cache进行访问时,首先是按与直接映象相同的方式进行访问。如果命中,则从相应的块中取出所访问的数据,送给CPU,访问结束。如果不命中,就将索引字段的最高位取反,然后按照新索引去寻找“伪相联组”中的对应块。如果这一块的标识匹配,则称发生了“伪命中”。否则,就访问下一级存储器。
(5)硬件预取技术。在处理器提出访问请求前预取指令和数据。
(6)由编译器控制的预取,硬件预取的替代方法,在编译时加入预取的指令,在数据被用到之前发出预取请求。
(7)编译器优化,通过对软件的优化来降低失效率。
(8)“牺牲”Cache。在Cache和其下一级存储器的数据通路之间增设一个全相联的小Cache,存放因冲突而被替换出去的那些块。每当发生不命中时,在访问下一级存储器之前,先检查“牺牲”Cache中是否含有所需的块。如果有,就将该块与Cache
中某个块做交换,把所需的块从“牺牲”Cache 调入Cache。
5.5简述减小Cache失效开销的几种方法。
答:让读失效优先于写、写缓冲合并、请求字处理技术、非阻塞Cache或非锁定Cache技术、采用二级Cache。
5.6 通过编译器对程序优化来改进Cache性能的方法有哪几种?简述其基本思想。
答:(1)数组合并。通过提高空间局部性来减少失效次数。有些程序同时用相同的索引来访问若干个数组的同一维,这些访问可能会相互干扰,导致冲突失效,可以将这些相互独立的数组合并成一个复合数组,使得一个Cache块中能包含全部所需元素。(2)内外循环交换。循环嵌套时,程序没有按数据在存储器中的顺序访问。只要简单地交换内外循环,就能使程序按数据在存储器中的存储顺序进行访问。(3)循环融合。有些程序含有几部分独立的程序段,它们用相同的循环访问同样的数组,对相同的数据作不同的运算。通过将它们融合成一个单一循环,能使读入Cache的数据被替换出去之前得到反复的使用。(4)分块。通过改进时间局部性来减少失效。分块不是对数组的整行或整列进行访问,而是对子矩阵或块进行操作。
5.7 在“Cache—主存”层次中,主存的更新算法有哪两种?它们各有什么特点?
答:(1)写直达法。易于实现,而且下一级存储器中的数据总是最新的。
(2)写回法。速度快,“写”操作能以Cache存储器的速度进行。而且对于同一单元的多个写最后只需一次写回下一级存储器,有些“写”只到达Cache,不到达主存,因而所使用的存储器频带较低。
5.8 组相联Cache的失效率比相同容量直接映象Cache的失效率低。由此能否得出结论:采用组相联一定能带来性能上的提高?为什么?
答:不一定。因为组相联命中率的提高是以增加命中时间为代价的,组相联需要增加多路选择开关。
5.9 写出三级Cache的平均访问时间的公式。
解:平均访存时间=命中时间+失效率×失效开销
只有第I层失效时才会访问第I+1。
设三级Cache的命中率分别为H L1、 H l2、 H L3,失效率分别为M l1、M l2、M L3,第三级Cache的失效开销为P L3。
平均访问时间T A =H L1+M l1{H l2+M l2(H L3+M L3×P L3)}
7.2 试比较可用于动态互连的总线、交叉开关和多级互连网络的硬件复杂度和带宽。
答:总线互连的复杂性最低,成本也是最低。其缺点是每台处理机可用的带宽较窄。
交叉开关是最昂贵的,因为其硬件复杂性以n2上升,所以其成本最高。但是交叉开关的带宽和寻径性能最好。当网络的规模较小时,它是一种理想的选择。
多级互连网络的复杂度和带宽介于总线和交叉开关之间,是一种折中方案。其主要优点是采用模块化结构,可扩展性较好。不过,其时延随网络级数的增加而上升。另外,由于其硬件复杂度比总线高很多,其成本也不低。
8.3 什么是多处理机的一致性?给出解决一致性的监听协议和目录协议的工作原理。
答:(1)对多个处理器维护一致性的协议称为Cache一致性协议。
(2)目录协议的工作原理:采用一个集中的数据结构——目录。对于存储器中的每一个可以调入Cache的数据块,在目录中设置一条目录项,用于记录该块的状态以及哪些Cache中有副本等相关信息。目录协议根据该项目中的信息以及当前要进行的访问操作,依次对相应的Cache发送控制消息,并完成对目录项信息的修改。此外,还要向请求处理器发送响应信息。
(3)监听协议的工作原理:每个Cache除了包含物理存储器中块的数据拷贝之外,也保存着各个块的共享状态信息。Cache 通常连在共享存储器的总线上,当某个Cache需要访问存储器时,它会把请求放到总线上广播出去,其他各个Cache控制器通过监听总线来判断它们是否有总线上请求的数据块。如果有,就进行相应的操作。
8.4 在标准的栅栏同步中,设单个处理器的通过时间(包括更新计数和释放锁)为C,求N个处理器一起进行一次同步所需要的时间。
解:我们忽略读写锁的时间。N个处理器中的每一个都需要C个时钟周期来锁住与栅栏相关的计数器,修改它的值,然后释放锁。考虑最坏情况,所有N个处理器都要对计数器加锁并修改它的值,由于锁只能顺序访问计数器,在同一时间,只能有一个处理器修改计数器的数据。所以,总共要花NC个时钟周期使得所有的处理器都到达数据栅栏。
8.7 有些机器实现了专门的锁广播一致性协议,实现上可能使用不同的总线。假设使用写广播协议,重新给出例8.3旋转锁的时间计算。
解:当实现了专门的锁广播一致性协议后,每当一把锁被释放的时候,和锁相关的值将被广播到所有处理器,这意味着在处理器对锁变量进行读操作的时候,未命中的情况永远不会发生。
假定每个Cache都有一个数据块保留锁变量的初值。通过下表可以知道,10次上锁/释放锁的平均时间是550个时钟周期,总时间是5500个时钟周期。
计算题:
1.6 某台主频为
求该计算机的有效CPI 、MIPS 和程序执行时间。 解:(1)CPI =(45000×1+75000×2+8000×4+1500×2) / 129500=1.776 (2)MIPS 速率=f/ CPI =400/1.776 =225.225MIPS
(3)程序执行时间= (45000×1+75000×2+8000×4+1500×2)/400=575s
1.7 将计算机系统中某一功能的处理速度加快10倍,但该功能的处理时间仅为整个系统运行时间的40%,则采用此增强功能方法后,能使整个系统的性能提高多少?
解 由题可知: 可改进比例 = 40% = 0.4 部件加速比 = 10
根据Amdahl 定律可知:()5625.110
4
.04.011
=+
-=系统加速比
采用此增强功能方法后,能使整个系统的性能提高到原来的1.5625倍。
1.8 计算机系统中有三个部件可以改进,这三个部件的部件加速比为:
部件加速比1=30; 部件加速比2=20; 部件加速比3=10
(1) 如果部件1和部件2的可改进比例均为30%,那么当部件3的可改进比例为多少时,系统加速比才可以达到10? (2) 如果三个部件的可改进比例分别为30%、30%和20%,三个部件同时改进,那么系统中不可加速部分的执行时间在总执行时间中占的比例是多少?
解:(1)在多个部件可改进情况下,Amdahl 定理的扩展:∑∑+-=
i
i
i n S F
F S )1(1
已知S 1=30,S 2=20,S 3=10,S n =10,F 1=0.3,F 2=0.3,得:
)
()(10/20/0.330/0.30.30.3-11
1033F F +++++=
得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 T
T T T n 045.010
2.020
3.0303.0'=++=
改进后整个系统的执行时间为:Tn = 0.045T+0.2T = 0.245T
那么系统中不可改进部分的执行时间在总执行时间中占的比例是:
82.0245.02.0=T
T
1.9
(1)改进后,各类操作的加速比分别是多少?
(2)各类操作单独改进后,程序获得的加速比分别是多少? (3)4类操作均改进后,整个程序的加速比是多少? 解:根据Amdahl 定律Se
Fe
Fe S n +
-=)1(1可得
4类操作均改进后,整个程序的加速比: 1.77)1(1
≈+-=
∑∑i
i
i n S F
F S
3.12 有一指令流水线如下所示
出 50ns 50ns 100ns 200ns
(1) 求连续输入10条指令,该流水线的实际吞吐率和效率; (2) 该流水线的“瓶颈”在哪一段?请采取两种不同的措施消除此“瓶颈”。对于你所给出的两种新的流水线,连续输入10条
指令时,其实际吞吐率和效率各是多少?
解:(1)
2200(ns)
2009200)10050(50t )1n (t T max
m
1
i i =?++++=?-+?=∑=流水;)(ns 220
1T n
TP 1
-==流水;45.45%11
5
4400TP m
t
TP E m
1
i i
≈=?
=??=∑= (2)瓶颈在3、4段。
? 变成八级流水线(细分)
850(ns)
50
9850t 1)(n t T max
m
1
i i =?+?=?-+?=∑=流水;)(ns 85
1
T n
TP 1-==流水
;58.82%17
10
8400TP m
ti
TP E m
1
i ≈=?
=??
=∑= ? 重复设置部件
)(ns 85
1
T n
TP 1pipeline
-==58.82%17
10
8
85010
400E ≈=??=
3.13有一个流水线由4段组成,其中每当流经第3段时,总要在该段循环一次,然后才能流到第4段。如果每段经过一次所需要的时间都是t ?,问:
(1) 当在流水线的输入端连续地每t ?时间输入任务时,该流水线会发生什么情况? (2) 此流水线的最大吞吐率为多少?如果每t ?2输入一个任务,连续处理10个任务时的实际吞吐率和效率是多少? (3) 当每段时间不变时,如何提高该流水线的吞吐率?仍连续处理10个任务时,其吞吐率提高多少? 解:(1
段
(
2)
54.35%
92
5045TP E 2310
T n
Tp 23T 21TP pipeline
pipeline max ≈=??=??==?=?=t
t
t t
(3)重复设置部件
t
t
??=??==75
1410
T n
TP pipeline
;吞吐率提高倍数=
t
t ??2310
75=1.64
3.14 有一条静态多功能流水线由5段组成,加法用1、3、4、5段,乘法用1、2、5段,第3段的时间为2△t ,其余各段的
时间均为△t ,而且流水线的输出可以直接返回输入端或
暂存于相应的流水寄存器中。现要在该流水线上计算 ,画出其时空图,并计算其吞吐率、加速比和效率。 解:(1)任务分析
(2)画时空图
乘法
加法
)
(41
i
i i
B A +∏=
段
23
段
t
? 14
18△t (3)计算流水线性能
吞吐率:t
T n Tp ?=
=187
;加速比:18
291854=??+??==
t 3t 3t 流水
串行T T Sp
效率: 90
29
54=
???+??==
t 1853t 3t 时空区总面积实际占用面积E
3.15 动态多功能流水线由6个功能段组成,如下图:
其中,S1、S4、S5、S6组成乘法流水线,S1、S2、S3、S6组成加法流水线,各个功能段时间均为50ns ,假设该流水线的输出结果可以直接返回输入端,而且设置有足够的缓冲寄存器,若以最快的方式用该流水计算:
∑=5
1
i i
i
i z
y x
(1) 画出时空图;
(2) 计算实际的吞吐率、加速比和效率。 解:机器一共要做10次乘法,4次加法。
3.18 在CRAY-1机器上,按照链接方式执行下述4条向量指令(括号中给出了相应功能部件的执行时间),如果向量寄存器和功能部件之间的数据传送需要1拍,试求此链接流水线的通过时间是多少拍?如果向量长度为64,则需多少拍才能得到全部结
乘法
加法
果?
V 0←存储器 (从存储器中取数:7拍) V 2←V 0+V 1 (向量加:3拍)