还剩34页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
第一章 计算机系统结构的基本概念 从处理数据的角度看,并行级别有位串字串,位并字串,位片串字并,全并行位串字串和位并字串基本上构成了SIMD位片串字并的例子有相联处理机STARAN,MPP全并行的例子有阵列处理机ILLIACIV 从__信息的角度看,并行级别有存储器操作并行,处理器操作步骤并行,处理器操作并行,指令、任务、作业并行 存储器操作并行是指可以在一个存储周期内并行读出多个CPU字的,采用单体多字、多体单字或多体多字的交叉访问主存系统,进而采用按内容访问方式,位片串字并或全并行方式,在一个主存周期内实现对存储器中大量字的高速并行操作例子有并行存储器系统,以相联存储器为核心构成的相联处理机 处理器操作步骤并行是指在并行性概念中引入时间因素,让多个处理过程在时间上错开,轮流重复地执行使用同一套设备的各个部分,加快硬件周转来赢得速度例子有流水线处理机 处理器操作并行是指一个指令部件同时控制多个处理单元,实现一条指令对多个数据的操作擅长对向量、数组进行处理例子有阵列处理机 指令、任务、作业并行是指多个__的处理机分别执行各自的指令、任务、作业例子有多处理机,计算机网络,分布处理系统 并行性的__途径有时间重叠TimeInterle__ing,资源重复Resour__Replication,资源共享Resour__Sharing 时间重叠是指在并行性概念中引入时间因素,让多个处理过程在时间上错开,轮流重复地执行使用同一套设备的各个部分,加快硬件周转来赢得速度例子有流水线处理机 资源重复是指一个指令部件同时控制多个处理单元,实现一条指令对多个数据的操作例子有阵列处理机,相联处理机 资源共享是指用软件方法让多个用户按一定时间顺序轮流使用同一套资源以提高资源的利用率,从而提高系统性能例子有多处理机,计算机网络,分布处理系统 SISD:一个指令部件控制一个操作部件,实现一条指令对一个数据的操作例子有传统的单处理机 SIMD:一个指令部件同时控制多个处理单元,实现一条指令对多个数据的操作例子有阵列处理机,相联处理机 MIMD:多个__的处理机分别执行各自的指令、任务、作业,实现指令、任务、作业并行的多机系统,是多个SISD的__,也称多倍SISD系统MSISD例子有多处理机,计算机网络,分布处理系统exercises:
1.有一台经解释实现的计算机,可以按功能划分成4级,每一级为了执行一条指令,需要下一级的N条指令来解释如果执行第1级的一条指令要Kns时间,那么执行第
2、第3和第4级的一条指令各需要用多少时间?解答 执行第
2、第3和第4级的一条指令各需要KNns、KN^2ns、KN^3ns的时间
1.有一个计算机系统可按功能分成4级,每级的指令互不相同,每一级的指令都比其下一级的指令在效能上强M倍,即第i级的一条指令能完成第i-1级的M条指令的计算量现若需第i级的N条指令解释第i+1级的一条指令,而有一段第1级的程序需要运行Ks,问在第
2、3和4级上一段等效程序各需要运行多长时间?答 第2级上等效程序需运行N/M*Ks第3级上等效程序需运行N/M*N/M*Ks第4级上等效程序需运行N/M*N/M*N/M*Ksnote: 由题意可知第i级的一条指令能完成第i-1级的M条指令的计算量而现在第i级有N条指令解释第i+1级的一条指令,那么,我们就可以用N/M来表示N/M表示第i+1级需N/M条指令来完成第i级的计算量所以,当有一段第1级的程序需要运行Ks时,在第2级就需要N/MKs,以此类推
2.硬件和软件在什么意义上是等效的?在什么意义上又是不等效的?试举例说明答软件和硬件在逻辑功能上是等效的,原理上,软件的功能可用硬件或固件完成,硬件的功能也可用软件模拟完成但是实现的性能__比,实现的难易程序不同 在DOS操作系统时代,汉字系统是一个重要问题,早期的汉字系统的字库和处理程序都固化在汉卡(硬件)上,而随着CPU、硬盘、内存技术的不断发展,UCDOS把汉字系统的所有组成部份做成一个软件
3.试以实例说明计算机系统结构、计算机组成与计算机实现之间的相互关系与影响答计算机系统结构、计算机组成、计算机实现互不相同,但又相互影响
(1)计算机的系统结构相同,但可采用不同的组成如IBM370系列有
115、
125、
135、
158、168等由低档到高档的多种型号机器从汇编语言、机器语言程序设计者看到的概念性结构相同,均是由__处理机/主存,通道、设备控制器,外设4级构成其中,__处理机都有相同的机器指令和汇编指令系统,只是指令的分析、执行在低档机上采用顺序进行,在高档机上采用重叠、流水或其它并行处理方式
(2)相同的组成可有多种不同的实现如主存器件可用双极型的,也可用MOS型的;可用VLSI单片,也可用多片小规模集成电路组搭
(3)计算机的系统结构不同,会使采用的组成技术不同,反之组成也会影响结构如为实现A:=B+CD:=E*F可采用面向寄存器的系统结构,也可采用面向主存的三地址寻址方式的系统结构要提高运行速度,可让相加与相乘并行,为此这两种结构在组成上都要求设置__的加法器和乘法器但对面向寄存器的系统结构还要求寄存器能同时被访问,而对面向主存的三地址寻址方式的系统结构并无此要求,倒是要求能同时形成多个访存操作数地址和能同时访存又如微程序控制是组成影响结构的典型通过改变控制存储器中的微程序,就可改变系统的机器指令,改变结构如果没有组成技术的进步,结构的进展是不可能的 综上所述,系统结构的设计必须结合应用考虑,为软件和算法的实现提供更多更好的支持,同时要考虑可能采用和准备采用的组成技术应避免过多地或不合理地限制各种组成、实现技术的采用和发展,尽量做到既能方便地在低档机上用简单便宜的组成实现,又能在高档机上用复杂较贵的组成实现,这样,结构才有生命力;组成设计上面决定于结构,下面受限于实现技术然而,它可与实现折衷权衡例如,为达到速度要求,可用简单的组成但却是复杂的实现技术,也可用复杂的组成但却是一般速度的实现技术前者要求高性能的器件,后者可能造成组成设计复杂化和更多地采用专用芯片 组成和实现的权衡取决于性能__比等因素;结构、组成和实现所包含的具体内容随不同时期及不同的计算机系统会有差异软件的硬化和硬件的软件都反映了这一事实VLSI的发展更使结构组成和实现融为一体,难以分开
4.什么是透明性概念?对计算机系统结构,下列哪些是透明的?哪些是不透明的?存储器的模m交叉存取;浮点数据表示;I/O系统是采用通道方式还是__处理机方式;数据总线宽度;字符行运算指令;阵列运算部件;通道是采用结合型还是__型;PDP-11系列的单总线结构;访问方式保护;程序性中断;串行、重叠还是流水控制方式;堆栈指令;存储器最小编址单位;Cache存储器答透明指的是客观存在的事物或属性从某个角度看不到 透明的有存储器的模m交叉存取;数据总线宽度;阵列运算部件;通道是采用结合型还是__型;PDP-11系列的单总线结构串行、重叠还是流水控制方式;Cache存储器 不透明的有浮点数据表示;I/O系统是采用通道方式还是__处理机方式;字符行运算指令;访问方式保护;程序性中断;;堆栈指令;存储器最小编址单位
5.从机器(汇编)语言程序员看,以下哪些是透明的?指令地址寄存器;指令缓冲器;时标发生器;条件寄存器;乘法器;主存地址寄存器;磁盘外设;先行进位链;移位器;通用寄存器;中断字寄存器答透明的有指令缓冲器、时标发生器、乘法器、先进先出链、移位器、主存地址寄存器
6.下列哪些对系统程序员是透明的?哪些对应用程序员是透明的?系列机各档不同的数据通路宽度;虚拟存储器;Cache存储器;程序状态字;“启动I/O”指令;“执行”指令;指令缓冲寄存器答对系统程序员透明的有系列机各档不同的数据通路宽度;Cache存储器;指令缓冲寄存器; 对应用程序员透明的有系列机各档不同的数据通路宽度;Cache存储器;指令缓冲寄存器;虚拟存储器;程序状态字;“启动I/O”指令note:系列机各档不同的数据通路宽度、Cache存贮器、指令缓冲寄存器属于计算机组成,对系统和程序员和应用程序员都是透明的 虚拟存贮器、程序状态字、“启动I/O”指令,对系统程序员是不透明的,而对应用程序员却是透明的 “执行”指令则对系统程序员和应用程序员都是不透明的
7.想在系列机中发展一种新型号机器,你认为下列哪些设想是可以考虑的,哪些则不行的?___?新增加字符数据类型和若干条字符处理指令,以支持事务处理程序的编译
(2)为增强中断处理功能,将中断分级由原来的4级增加到5级,并重新调整中断响应的优先次序
(3)在CPU和主存之间增设Cache存储器,以克服因主存访问速率过低而造成的系统性能瓶颈
(4)为解决计算误差较大,将机器中浮点数的下溢处理方法由原来的恒置“1”1TBYTE主存容量和1TBYTES的I/O带宽第二章 数据表示与指令系统
1.尾数的rm进制数位m和尾数的二进制数位m的关系 存在m=m/log2rm这种关系是因为,在机器中,一个rm进制的数位是用log2rm个机器数位来表示的 假设rm=8,尾数为20,则m=2八进制数20转换成二进制数为_____,其二进制数位,即机器数位m=52=5/log28 note:这里的等号并不表示纯粹数学意义上的“等于”
2.可表示的尾数个数公式 rm^mrm-1/rm 对于rm进制的数来说,每个数位均可以有0到rm-1,即rm个码m个rm进制数位共有rm^m种编码但课本中讨论的是规格化数,即尾数的小数点后第一个数位不为零的数,所以,应该去掉小数点后第一个数位是0的那些非规格化的数显然,非规格化数的个数占了全部尾数编码总数的1/rm的比例,所以可表示的浮点数规格化的尾数个数应该是rm^m(1-1/rmexercises:
1.某模型时机共有7种指令,各指令使用频率分别为
0.35,
0.25,
0.20,
0.10,
0.05,
0.03,
0.02,有8个通用数据寄存器和2个变址寄存器
(1)要__作码的平均长最短,请设计操作码的编码,并计算所设计操作码的平均长(4分)
(2)设计8位长度的寄存器-寄存器型指令3种,16位长度的寄存器-存储器变址寻址方式指令4条,变址范围不小于正、负127请写出指令格式,并给出各字段的长度和操作码编码(6分)解答 1全Huff__n编码的平均码长是可用的二进制位编码中平均码长最短的编码全Huff__n编码的平均码长=2*
0.35+
0.25+
0.20+3*
0.10+4*
0.05+5*
0.02+
0.03=
2.35 2由于有8个通用数据寄存器和2个变址寄存器,所以通用寄存器用3位表示,变址寄存器用1位表示8位的寄存器-寄存器型指令,3个操作码编码为
00、
01、10,16位的寄存器-存储器变址寻址方式指令,4个操作码编码为
1100、
1101、
1110、1111,2位3位3位OPR1R2操作码寄存器1寄存器24位3位1位8位OPR1Xd操作码寄存器1变址寄存器相对位移主存逻辑地址
1.数据结构和机器的数据表示之间是什么关系?确定和引入数据表示的基本原则是什么?答数据表示是能由硬件直接识别和引用的数据类型数据结构反映各种数据元素或信息单元之间的结构关系 数据结构要通过软件映象变换成机器所具有的各种数据表示实现,所以数据表示是数据结构的组成元素不同的数据表示可为数据结构的实现提供不同的支持,表现在实现效率和方便性不同数据表示和数据结构是软件、硬件的交界面 除基本数据表示不可少外,高级数据表示的引入遵循以下原则
(1)看系统的效率有否提高,是否养活了实现时间和存储空间
(2)看引入这种数据表示后,其通用性和利用率是否高
2.标志符数据表示与描述符数据表示有何区别?描述符数据表示与向量数据表示对向量数据结构所提供的支持有什么不同?答标志符数据表示与描述符数据表示的差别是标志符与每个数据相连,合存于同一存储单元,描述单个数据的类型特性;描述符是与数据分开存放,用于描述向量、数组等成块数据的特征 描述符数据表示为向量、数组的的实现提供了支持,有利于简化高级语言程序编译中的代码生成,可以比变址法更快地形成数据元素的地址但描述符数据表示并不支持向量、数组数据结构的高效实现而在有向量、数组数据表示的向量处理机上,硬件上设置有丰富的赂量或阵列运算指令,配有流水或阵列方式处理的高速运算器,不仅能快速形成向量、数组的元素地址,更重要的是便于实现把向量各元素成块预取到__处理机,用一条向量、数组指令流水或同时对整个向量、数组高速处理.如让硬件越界判断与元素运算并行这些比起用与向量、阵列无关的机器语言和数据表示串行实现要高效的多
3.堆栈型机器与通用寄存器型机器的主要区别是什么?堆栈型机器系统结构为程序调用的哪些操作提供了支持?答通用寄存器型机器对堆栈数据结构实现的支持是较差的表现在1堆栈操作的指令少,功能单一;2堆栈在存储器内,访问堆栈速度低;3堆栈通常只用于保存于程序调用时的返回地址,少量用堆栈实现程序间的参数传递 而堆栈型机器则不同,表现在1有高速寄存器组成的硬件堆栈,并与主存中堆栈区在逻辑上组成整体,使堆栈的访问速度是寄存器的,容量是主存的;2丰富的堆栈指令可对堆栈中的数据进行各种运算和处理;3有力地支持高级语言的编译;4有力地支持子程序的嵌套和递归调用 堆栈型机器系统结构有力地支持子程序的嵌套和递归调用在程序调用时将返回地址、条件码、关键寄存器的内容等全部压入堆栈,待子程序返回时,再从堆栈中弹出
4.设某机阶值6位、尾数48位,阶符和数符不在其内,当尾数分别以
2、
8、16为基时,在非负阶、正尾数、规格化数情况下,求出其最小阶、最大阶、阶的个数、最小尾数值、最大尾数值、可表示的最小值和最大值及可表示的规格化数的总个数解 依题意知p=6m=48rm=2816,m=m/log2rm,列下表p=6m=48rm=2m=48p=6m=48rm=8m=16p=6m=48rm=16m=12最小阶非负阶,最小为0000最大阶2^p-12^6-12^6-12^6-1最小尾数值rm^-11/21/81/16最大尾数值1-rm^-m1-2^-481-8^-16,即1-2^-481-16^-12,即1-2^-48可表示的最小值1/21/81/16可表示的最大值2^63*1-2^-488^63*1-8^-1616^63*1-16^-12阶的个数2^p2^62^62^6可表示的尾数的个数2^48*2-1/28^16*8-1/816^12*16-1/16可表示的规格化数的个数2^6*2^48*2-1/22^6*8^16*8-1/82^6*16^12*16-1/16note: 可表示的最小值=rm^最小阶*最小尾数值=rm^0*rm^-1=rm^-1; 可表示的最大值=rm^最大阶*最大尾数值=rm^2^p-1*1-rm^-m; 可表示的尾数的个数=rm^m*rm-1/rm; 可表示的规格化数的个数=阶的个数*尾数的个数=2^p*rm^m*rm-1/rm
5.
(1)浮点数系统使用的阶基rp=2阶值位数p=2尾数基值rm=10,以rm为基的尾数位数m=1按照使用的倍数来说,等价于m=4试计算在非负阶、正尾数、规格化情况下的最小尾数值、最大尾数值、最大阶值、可表示的最小值和最大值及可表示数的个数
(2)对于rp=2p=2rm=4m=2重复以上计算解 依题意列下表p=2rm=10m=1p=2rm=4m=2最小尾数值10^-1=
0.14^-1=
0.25最大尾数值1-10^-1=
0.91-4^-2=15/16最大阶值2p^-1=33可表示的最小值
0.
10.25可表示的最大值10^3*
0.9=9004^3*15/16=60可表示数的个数3648 题中“按照使用的倍数来说,等价于m=4”这个m=4因为2^3102^4等价为实际要4个二进制位,表示RM=10为基的一位
6.由4位数(其中最低位为下溢附加位)经ROM查表舍入法,下溢处理成3位结果,设计使下溢处理平均误差接近于零的ROM表,列出ROM编码表地址与内容的对应关系解 ROM编码表地址与内容的对应关系地址0000000100100011010001010110011110001001101010111100110111101111内容
0000010010100100110111001001011011101101111111117.变址寻址和基址寻址各适用于何种场合?设计一种只用6位地址码就可指向一个大地址空间中任意64个地址之一的寻址机构答基址寻址是对逻辑地址空间到物理地址空间变换的支持,以利于实现程序的动态再定位变址寻址是对数组等数据块运算的支持,以利于循环将大地址空间64个地址分块,用基址寄存器指出程序所在块号,用指令中6位地址码表示该块内64个地址之一,这样基址和变址相结合可访问大地址任意64个地址之一比如地址空间很大,为0-1023,只用6位地址码就可以指向这1024个地址中的任意64个剖析比如地址空间很大,1024,就是分成16个块,块号放在寄存器中,块__址放在地址位中,寄存器内容和地址位结合,就能达到要求了
8.经统计,某机器14条指令的使用频度分别为
0.
010.
150.
120.
030.
020.
040.
020.
040.
010.
130.
150.
140.
110.03分别求出用等长码、Huff__n码、只有两种码长的扩展操作码3种编码方式的操作码平均码长解等长操作码的平均码长=4位;Huff__n编码的平均码长=
3.38位;只有两种码长的扩展操作码的平均码长=
3.4位
9.若某机要求三地址指令4条,单地址指令255条,零地址指令16条设指令字长为12位.每个地址码长为3位问能否以扩展操作码为其编码如果其中单地址指令为254条呢说明其理由答
①不能用扩展码为其编码 ∵指令字长12位,每个地址码占3位; ∴三地址指令最多是2^12-3-3-3=8条,现三地址指令需4条 ∴可有4条编码作为扩展码, ∴单地址指令最多为4×2^3×2^3=2^8=256条, 现要求单地址指令255条,∴可有一条编码作扩展码 ∴零地址指令最多为1×2^3=8条 不满足题目要求 ∴不可能以扩展码为其编码
②若单地址指令254条,可以用扩展码为其编码 ∵依据
①中推导,单地址指令中可用2条编码作为扩展码 ∴零地址指令为2×2^3=16条,满足题目要求note:三地址指令格式操作码地址码地址码地址码3位3位3位3位单地址指令格式操作码地址码9位3位16-6-6=2^4=16条,现双地址指令有X条 ∴可有16-X条编码作为扩展码, ∴单地址指令最多为16-X×2^6=256条
11.何谓指令格式的优化简要列举包括操作码和地址码两部分的指令格式优化可采用的各种途径和思路答 指令格式的优化指如何用最短位数表示指令的操作信息和地址信息,使程序中指令的平均字长最短
①操作码的优化 采用Huff__n编码和扩展操作码编码
②对地址码的优化 采用多种寻址方式; 采用
0、
1、
2、3等多种地址制; 在同种地址制内再采用多种地址形式,如寄存器-寄存器型、寄存器-主存型、主存-主存型等; 在维持指令字在存储器内按整数边界存储的前提下,使用多种不同的指令字长度
12.某模型机9条指令使用频率为ADD加30%SUB减24%JOM按负转移6%STO存7%JMP转移7%SHR右移2%CIL循环3%CLA清加20%STP停机1%要求有两种指令字长,都按双操作数指令格式编排,采用扩展操作码,并限制只能有两种操作码码长设该机有若干通用寄存器,主存为16位宽,按字节编址,采用按整数边界存储任何指令都在一个主存周期中取得,短指令为寄存器-寄存器型,长指令为寄存器-主存型,主存地址应能变址寻址1仅根据使用频率,不考虑其它要求,设计出全Huff__n操作码,计算其平均码长;2考虑题目全部要求,设计优化实用的操作形式,并计算其操作码的平均码长;3该机允许使用多少可编址的通用寄存器?4画出该机两种指令字格式,标出各字段之位数;5指出访存操作数地址寻址的最大相对位移量为多少个字节?解 第1和2中Huff__n和扩展操作码的编码及平均码长如下表指令Ii使用频度PiHuff__n编码扩展操作码编码I1I2I3I4I5I6I7I8I930%24%20%7%7%6%3%2%1%10000111001101111011110111110111111000110110001100111010110111110011101西个马pili
2.
612.78 38个 4两种指令格式如下图所示2位3位3位OPR1R2操作码寄存器1寄存器25位3位3位5位OPR1Xd操作码寄存器1变址寄存器相对位移主存逻辑地址5访存操作数地址寻址的最大相对位移量为32个字节
13.设计RISC机器的一般原则及可采用的基本技术有那些答 一般原则 1确定指令系统时,只选择使用频度很高的指令及少量有效支持操作系统,高级语言及其它功能的指令; 2减少寻址方式种类,一般不超过两种; 3让所有指令在一个机器周期内完成; 4扩大通用寄存器个数,一般不少于32个,尽量减少访存次数; 5大多数指令用硬联实现,少数用微程序实现; 6优化编译程序,简单有效地支持高级语言实现 基本技术 1按RISC一般原则设计,即确定指令系统时,选最常用基本指令,附以少数对操作系统等支持最有用的指令,使指令精简编码规整,寻址方式种类减少到
1、2种 2逻辑实现用硬联和微程序相结合即大多数简单指令用硬联方式实现,功能复杂的指令用微程序实现 3用重叠寄存器窗口即为了减少访存,减化寻址方式和指令格式,简单有效地支持高级语言中的过程调用,在RISC机器中设有大量寄存嚣,井让各过程的寄存器窗口部分重叠 4用流水和延迟转移实现指令,即可让本条指令执行与下条指令预取在时间上重叠另外,将转移指令与其前面的一条指令对换位置,让成功转移总是在紧跟的指令执行之后发生,使预取指令不作废,节省一个机器周期 5优化设计编译系统即尽力优化寄存器分配,减少访存次数不仅要利用常规手段优化编译,还可调整指令执行顺序,以尽量减少机器周期等
14.简要比较CISC机器和RISC机器各自的结构特点,它们分别存在哪些不足和问题___说今后的发展应是CISC和RISC的结合答CISC结构特点机器指令系统庞大复杂 RISC结构特点机器指令系统简单,规模小,复杂度低 CISC的问题 1指令系统庞大,一般200条以上; 2指令操作繁杂,执行速度很低; 3难以优化生成高效机器语言程序,编译也太长,太复杂; 4由于指令系统庞大,指令的使用频度不高,降低系统性能__比,增加设计人员负担 RISC的问题; 1由于指令少,在原CISC上一条指令完成的功能现在需多条RISC指令才能完成,加重汇编语言程序设计负担,增加了机器语言程序长度,加大指令信息流量 2对浮点运算和虚拟存储支持不很强 3RISC编译程序比CISC难写 由于RISC和CISC各有优缺点在设计时,应向着两者结合,取长补短方向发展第三章 总线、中断与输入输出系统 中断嵌套的原则在处理某级中断请求时,只能比它的中断处理级别高的中断请求才能中断其处理,等呼应和处理完后再继续处理原先的那个中断请求 为了领会中断响应排队器对中断响应优先次序是用硬件固定的,以及通过由操作系统给各中断级服务程序现行程序状态字中的中断级屏蔽位设置不同的状态,可以改变中断处理完的次序这两个要点,下图给出了一个中断响应硬件部分的简单逻辑原理示意图图中略去了某些实现上的具体细节,因为这些已不是本课程要讨论的内容 中断级屏蔽位是程序状态字中的一个组成部分程序状态字是将散布于系统各部分,反映程序工作时某些关键性硬件的状态,组合在一起所构成的字,有的计算机也称其为处理器状态字或程序换道区每类程序均在主存中指定一个区域来放置其程序状态字运行一个程序或进程时,就会将其程序状态字从主存指定单元或区域取出送到分散于系统各部分的寄存器或计数器中,建立起运行此程序或进程的环境一个程序或进程在退出运行时,也会将反映该程序状态的这些寄存器或计数器内容组拼成程序状态字,存回该程序或进程在主存中的指定单元或区域里因此,程序或进程的切换,只需要通过硬件启动的交换新旧程序状态字的内容即可快速完成例如,在IBM370系列机上,程序状态字为64位,等于它的长字,交换程序状态字只需硬件启动写长字和读长字两次访存即可完成尽管中断请求是随机发出的,为了便于精确保存中断的断点以及在中断处理完后又能返回到原中断处,中断响应排队器总是在每条指令执行到最后一个机器周期的最后一个时钟周期时,对目前到达中断响应排队器入口的所有中断请求排一次队,择优进行响应在中断响应排队器相应的输出端产生出响应__此__经中断级服务程序入口地址形成硬件,生成出该级中断服务程序的程序状态字在内存区中所存放的地址同时,经中断响应控制__启动,进行新旧程序状态字的交换,完成程序的切换被中断的程序的断点地址即程序计数器的内容,由硬件自动压入返回地址堆栈,予以保存系统切换到新的程序或进程后,继续运行下去如果新的程序或进程是一个中断服务程序,在运行结束,执行到中断返回指令时,就会从堆栈中弹出所保存的返回地址,再次交换程序状态字,系统又重新返回到原被中断的程序,恢复运行
1.如何设置中断级屏蔽位寄存器中的中断屏蔽码? 设中断级屏蔽位“1”对应于开放,“0”对应于屏蔽 第i级中断处理程序级别的各级中断级屏蔽位中应有i-1位设为“1”举例来说,第1级中断处理程序级别的各级中断级屏蔽位均应设为“0” 响应级别为n的中断处理程序的n级中断级屏蔽位应设为“0” 设第i2级中断处理程序级别的中断处理级别高于第i1级中断处理程序级别,根据中断嵌套的原则,第i1级中断处理程序级别的第i2级中断级屏蔽位应设为“1”从而实现对第i2级中断处理程序级别的开放
2.对中中断级屏蔽位举例1的解释 *1,2,3,4中断同时出现,进行排队器; *按中断响应优先级,1最高,响应; *1的屏蔽字为0000,所以1中断执行到结束,回用户程序; *剩下的2优先级高,2响应,但其屏蔽字为1011,允许响应
1、
3、4,3的响应优先级高,所以; *2被中断,3响应,但其屏蔽字为1001,允许响应
1、4,所以; *4响应,执行到结束,回3; *3执行到结束,回2; *2执行到结束,回用户程序
3.怎样题目中没有说明的通道属于哪一类型? 有的题目中没有说明谈及的通道的类型,这种情况下,一般是指字节多路通道
1.简要举出集中式串行链接,定时查询和__请求3种总线控制方式的优缺点同时分析硬件产生故障时通讯的可靠性答控制方式优点缺点串行链接1选择算法简单2控制线数少,只需要3根,且不取决于部件数量3可扩充性好1对“总线可用”线及其有关电路失效敏感2灵活性差,如果高优先级的部件频繁要求使用总线,离总线控制器远的部件就难以获得总线使用权3“总线可用”__顺序脉动地通过各个部件,总线的分配速度慢4受总线长度的限制,增减和__部件受限制定时查询1灵活性强,部件的优先次序由程序控制2可靠性高,不会因某个部件失效而影响其它部件使用总线1总线的分配速度不能很高2控制较为复杂3控制线数多,需要2+log2N根4可扩充性差__请求1灵活性强,部件的优先次序由程序控制2能方便地隔离失效部件的请求3总线的分配速度快1控制较为复杂2控制线数多,要控制N个设备,需要有2N+1根控制线
2.设中断级屏蔽位“1”对应于开放,“0”对应于屏蔽,各级中断处理程序的中断级屏蔽位设置如下中断处理程序级别中断级屏蔽位1级2级3级4级第1级0000第2级1010第3级1000第4级1010 1当中断响应优先次序为1→2→3→4时,其中断处理次序是什么 2如果所有的中断处理都各需3个单位时间,中断响应和中断返回时间相对中断处理时间少得多当机器正在运行用户程序时,同时发生第2,3级中断请求,过两个单位时间,又同时发生第1,4级中断请求,试画出程序运行过程示意图答 1当中断响应优先次序为1→2→3→4时,其中断处理次序为1→3→4→2
23.若机器共有5级中断中断响应优先次序为1→2→3→4→5现要求其实际的中断处理次求序1→4→5→2→31设计各级中断处理程序的中断级屏蔽位令“1”对应于开放,“0”对应于屏蔽;2若在运行用户程序时,同时出现第4,2级中断请求,而在处理第2级中断未完成时,又同时出现第1,3,5级中断请求,请画出此程序运行过程示意图答 1中断级屏蔽位设置如下图中断处理程序级别中断级屏蔽位1级2级3级4级5级第1级11111第2级01100第3级00100第4级01111第5级01101 2中断过程示意图如图
2、4中断同时出现,进行排队器 首先响应第2级中断请求,屏蔽字为01100,表明其对第4级中断请求开放,所以转去响应第4级中断请求并进行处理 响应4,中断4运行结束,回2
1、
3、5进入排队器 第2级中断请求的处理请求被中断,转去响应第1级中断请求并进行处理 响应第5级中断请求并进行处理 继续响应并处理第2级中断处理请求,结束后返回用户程序 最后处理第3级中断请求
4.简述字节多路,数组多路和选择通道的数据传送方式答: 字节多路通道适用于连接大量的像光电机等字符类低速设备这些设备传送一个字符字节的时间很短,但字符字节间的等待时间很长通道“数据宽度”为单字节,以字节交叉方式轮流为多台设备服务,使效率提高字节多路通道可有多个子通道,同时执行多个通道程序 数组多路通道适合于连接多台象磁盘等高速设备这些设备的传送速率很高,但传送开始前的寻址辅助操作时间很长通道“数据宽度”为定长块,多台设备以成组交叉方式工作,以充分利用并尽可能重叠各台高速设备的辅助操作时间传送完K个字节数据,就重新选择下个设备数组多路通道可有多个子通道,同时执行多个通道程序 选择通道适合于连接象磁盘等优先级高的高速设备,让它独占通道,只能执行一道通道程序通道“数据宽度”为可变长块,一次将N个字节全部传送完,在数据传送期只选择一次设备
5.如果通道在数据传送期中,选择设备需
9.8μs,传送一个字节数据需
0.2μs某低速设备每隔500μs发出一个字节数据传送请求,问至多可接几台这种低速设备对于如下A~F6种高速设备,一次通讯传送的字节数不少于1024个字节,问哪些设备可以挂在此通道上哪些则不能其中A—F设备每发出一个字节数据传送请求的时间间隔分别为单位为μs 表3-5设备ABCDEF发申请间隔μs
0.
20.
250.
50.
190.
40.21答: 1至多可连接50台低速的外设剖析 根据题意可知低速设备应挂接在字节多路通道上,字节多路通道的通道极限流量为 f__x.byte=1/TS+TD=fbyte 通道极限流量应大于或等于设备对通道要求的流量fbyte 如果字节多路通道上所挂设备台数为m设备的速率为fi,为了不丢失信息,应满足 1/TS+TD=m*fi fi也就是设备发出字节传送请求间隔时间500μs的倒数,所以 m=1/TS+TD*f=500/
9.8+
0.2=50台 2设备BCEF可以挂在此通道上,设备AD则不能剖析 思路一从传送字节速率上入手 A~F是高速设备,应挂接在选择通道上,选择通道的极限流量为 f__x.select=N/TS+N*TD=1/TS/N+TD=1/
9.8/1024+
0.2=1/
0.21约 通道上所挂设备的最大速率fi.__x应小于或等于通道的极限流量 由表3-5可得出设备ABCDEF传送速率B/μs1/
0.21/
0.251/
0.51/
0.191/
0.41/
0.21 所以,B、C、E、F可挂在该通道上A、D不能 思路二从传送字节时间上入手 对于高速设备,由于一次传送字节数不少于1024byte ∴该通道一次传送数据的时间为
9.8μs+1024×
0.2μs=
214.6μs 由表3-5可得出每台设备发送1024字节的时间间隔分别为:设备ABCDEF传送时间μs
204.
8256512194.
56409.
6215.04 ∴为使数据不丢失,B、C、E、F可挂在该通道上A、D不能
6.某字节多路通道连接6台外设,某数据传送速率分别如表中所列设备123456传送速率KB/s50151002540201计算所有设备都工作时的通道实际最大流量2如果设计的通道工作周期使通道极限流量恰好与通道最大流量相等,以满足流量设计的基本要求,同时让速率越高的设备被响应的优先级越高当6台设备同时发出请求开始,画出此通道在数据传送期内响应和处理各外设请求的时间示意图由此你发现了什么问题3在2的基础上,在哪台设备内设置多少个字节的缓冲器就可以避免设备信息丢失那么,这是否说书中关于流量设计的基本要求是没有必要的了呢___解 1实际最大流量=50+15+l00+25+40+20=250KB/S 2通道响应和处理各设备请求的时间示意图 由此发现由于高速设备的响应优先级高,使低速设备2造成数据丢失3在2中各设两个字节的缓冲区即可这并不说明流量设计的基本条件是不必要的,因为若基本条件不满足,无论设备优先级如何确定总有设备的信息会丢失剖析 2由各设备的传送字节速率可解其连续发出传送请求的时间间隔分别为设备123456发申请间隔μs2067约
104025507.通道型I/O系统由一个字节多路通道A其中包括两个子通道Al和A2,两个数组多路通道B1和B2及一个选择通道C构成,各通道所接设备和设备的数据传送速率如表所示1分别求出各通道应具有多大设计流量才不会丢失信息;2设I/O系统流量占主存流量的1/2时才算流量平衡,则主存流量应达到多少通道号所接设备的数据传送速率KB/s字节多路通道子通道A15035202050352020子通道A25035202050352020数组多路通道B1500400350250数组多路通道B2500400350250选择通道C500400350250解 1要不丢失信息,各通道需要达到的流量字节多路通道子通道A1:
0.25KB/S;字节多路通道子通道A2:
0.25KB/S;数组多路通道B1:500KB/s;数组多路通道B2:500KB/s;选择通道C:500KB/s 2主存流量应达到4MB/S剖析: 1设备要求字节多路通道或其子通道的实际最大流量,是该通道所接各设备的字节传送速率之和; 设备要求数组多路通道或选择通道的实际最大流量,是该通道所接各设备的字节传送速率中的最大者 2I/O系统中,各种通道和子通道可以并行工作,因此,I/O系统的最大流量应等于各通道最大流量之和第四章 存储体系 解决Cache的透明性所带来的问题,和__处理机写Cache,使主存内容跟不上Cache内对应内容的变化造成的不一致的问题的关键是选择好更新主存内容的算法,一般有两种写直达法存直达法和写回法即抵触修改法两种 写直达法,又称存直达法,是指在CPU对Cache进行写操作时,如果命中Cache,不仅将数据写入Cache,而且写入主存,使两者的对应内容统一起来,这样,当Cache中的块被替换时,就不必再花时间写回主存了 写回法,又称抵触修改法,是指在CPU对Cache进行写操作时,如果命中Cache,就只将数据写入Cache,而暂时不写入主存,只有当变化了的Cache块被替换时,才花一个主存周期,将其写回主存相应的位置上,使两者的对应内容统一起来 Cache采用按需取进算法和预取进算法来提高Cache的命中率 按需取进算法是指在Cache块失效时才将要访问的字所在的块取进Cache预取进算法是指在用到某Cache块之前就将该块预取进Cache 预取进算法包括恒预取进算法和不命中时预取进算法 恒预取进算法是指访问主存第i块时,不论其是否在Cache中命中,恒将主存第i+1块预取进Cache不命中时预取进算法是指访问到主存第i块的信息时,只有当其不在Cache中时,才将主存第i+1块预取进Cache
1.按位编址和按字编址? 现在从内存中读数据都是按字节为单位 P86第二段第一行“目前不少机器的指令地址码已达24-32位,相当于每个用户的程序空间已达16MB-8192MB”这里有一层隐含的意思,就是地址码一般是按字节编码
2.相等比较电路的个数=组内块数? 我不知道是不是可以这么理解,遇到过一道题,其中存在这种关系,不知道是不是巧合? 一个采用位选择组相联映象方式的Cache,要求Cache的每一块在主存周期内取得主存采用4个存储体的低位交叉方式访问,每个存储体的字长为4个字节,总容量为256MB,Cache的容量为512KB每一组内有4块采用按地址访问存储器构成相联目录表,实现主存地址到Cache地址的变换,采用4个相等比较电路 1设计主存地址格式,并标出各字段的长度5分 2设计Cache的地址格式,并标出各字段的长度5分 3设计相联目录表结构,并求出该表的行数及每一行的格式5分 4画出实现位选择组相联地址变换的逻辑示意图5分
3.采用多级状态位技术、比较对法实现LRU算法时需要比较对触发器的个数 设组内有b块,每组g群,每群p对,每对l行 每组g群,组中选群需C2g个比较对触发器 每群p对,群中选对需__2p个比较对触发器 每对l行,对中选行需gpC2l个比较对触发器 共需C2g+__2p+gpC2l个比较对触发器
1.在一个页式虚拟存储器中,虚地址空间为4G字节,页大小为1K字节,页表项的大小为4字节试问 1共需要多少个页表项? 2每个页面可存放多少个页表项? 3需要几级页表构成表层次?解答 12^22个或4M个 21024/4=256个 33级 第四章 存储体系
1.设二级虚拟存储器的TA1=10-7s、TA2=10-2s为使存储层次的访问效率e达到最大值的80%以上,命中率H至少要求达到多少?实际上这样高的命中率是很难达到的,那么从存储层次上如何改进?解 e=TA1/TA=TA1/H*TA1+1-H*TA2≥80%,H≥10^5-5/4/10^5-1 这样的命中率很难达到为了降低对H的要求,可以选择高命中率的算法,可以减少相邻两级的访问速度差和容量差这样做不利于降低存储器的平均每位__,可在主、辅存储器间加一层电子磁盘,使存储体系中相邻两级的访问时间比不太大
2、程序存放在模32单字交叉存储器中,设访存申请队的转移概率λ为25%求每个存储周期能访问到的平均字数当模数为16呢?由此你可得到什么结论?解B=[1-1-λ^m]/λ解 由λ=
0.25m=32求得B=4-4*3/4^32 同理,m=16时B=4-4*3/4^16 可得出,在λ=
0.25时,m=32的平均访问字数大于m=16时的平均访问字数
3、设主存每个分体的存取周期为2μs,宽度为4个字节采用模m多分体交叉存取,但实际频宽只能达到最大频宽的
0.6倍现要求主存实际频宽为4MB/S问主存模数m应取多少方能使两者速度基本适配?其中m取2的幂解 m=4剖析 根据题意,模m多分体交叉的最大频宽为分体数*单体频宽=m*分体的宽度/分体的存取周期=m*4B/2μs,所以有
0.6*m*4/2=
44.某虚拟存储器共8个页面,每页1024个字,实际主存为4096个字,采用页表法进行地址映象映象表的内容如下表所示虚页号01234567实页号31232100装入位11001010注我把虚页号加上了1列出会发生页面失效的全部虚页号;2按以下虚地址计算主存实地址0,3728,1023,1024,2055,7800,4096,6800解: 1会发生页面失效的全部虚页号为2357 2虚地址虚页号页内位移装入位实页号页内位移实地址0001303072327836560页面失效页面失效无102301023131023409510241011010242055270页面失效页面失效无780076320页面失效页面失效无40964012020486800665610656656剖析1根据页表法列出表2,当装入位为0时,即为页面失效,再找出相对应的虚页号即可 2虚页号=虚地址/页面大小 页内位移量=虚地址-虚页号*页面大小 实地址=实页号*页面大小+页内位移量 由于可以用替换算法解决页面失效的问题,所以,发生页面失效的虚页2357仍然可以有相应的实地址,但这样要在页表中建立新的虚实地址对应关系,新的虚实地址对应关系和原来的对应关系相同的可能性就很小了
5、一个段页式虚拟存储器虚地址有2位段号、2位页号、11位页内位移(按字编址),主存容量为32K字每段可有访问方式保护,其页表和保护位如下表所示段号0123访问方式只读可读/执行可读/写/执行可读/写虚页0所在位置实页9在辅存上页表不在主存内实页14虚页1所在位置实页3实页0页表不在主存内实页1虚页2所在位置在辅存上实页15页表不在主存内实页6虚页3所在位置实页12实页8页表不在主存内在辅存上1此地址空间__有多少个虚页?2当程序中遇到下列情况时方式段页页内位移取数取数取数存数存数存数转移至此取数取数转移至此013021102311311032001102047421410050560写出由虚地址计算出实地址说明哪个会发生段失效、页面或保护失效失效解答:1该地址空间__有16个虚页 2程序中遇到上表中各情况时,是否会发生段失效、页失效或保护失效及相应的主存实地址的情况如下表所示方式段页页内位移段失效页失效实页号实地址保护失效取数取数取数存数存数存数转移至此取数取数转移至此013021102311311032001102047421410050560无无无无有无无无有无无无有无/有无有/无30无3无无8无无14614510无6184无无16484无无28732无无/有//无//有剖析 1虚地址中段号有2位,页号有2位,也就是每个程序最多只能有2^2=4个段,每个段至多只能有2^2=4页,所以该地址空间__有4*4=16个虚页 2先从题意得知 实地址15位,其中实页号4位,页内位移11位 页大小为2K字(由页内位移得知)
6.设某程序包含5个虚页,其页地址为4,5,3,2,5,1,3,2,2,5,1,3当使用LRU算法替换时,为获得最高命中率,至少应分配给该程序几个实页?其可能的最高命中率为多少?
7.采用页式管理的虚拟存储器,分时运行两道程序其中,程序X为DO50I=13 BI=AI-CI IFBI·LE·0GOTO40 DI=2*CI-AI IFDI·EQ·0GOTO5040 EI=050 CONTINUEData:A=-4+20 C=-30+1每个数组分别放在不同的页面中;而程序Y在运行过程中,其数组将依次用到程序空间的第354253132513152页如果采用LRU算法,实存却只有8页位置可供存放数组之用试问为这两首程序的数组分别分配多少个实页最为合适?___?解答 分别分配给程序X和Y的数组4个实页最为合适 根据题意,程序X依次调用数组ACBBEACBBCADDEACBBE中的数据 设程序X中的数组ABCDE分别存放于程序空间的第12345页,则程序的页地址流为1,3,2,2,5,1,3,2,2,3,1,4,4,5,1,3,2,2,5 分析使用LRU算法对程序X的页地址流进行堆栈处理的过程可知,分配给程序X的数组5个实页最为合适;分析使用LRU算法对程序Y的页地址流进行堆栈处理的过程可知,分配给程序Y的数组4个实页最为合适 但实存只有8页位置可供存放数组之用,所以,分别分配给程序X和Y的数组4个实页note: 分时运行在微观上是串行的,就是说,分时运行时把时间划分为若干时间片,每个程序轮流占用时间片;在宏观上是并行的,就是说,每个程序在一个时间片内并不能运行完总的来看,是同时运行的,所以两个程序分配的实页和不能大于8 我不了解FORTRAN,找朋友把上面的源代码转成C了__in{intA[]={-420};intC[]={-301};fori=0i0E[i]=0;};};}
8.设一个按位编址的虚拟存储器,它应可对应1K个任务,但在一段较长时间内,一般只有4个任务在使用,故用容量为4行的相联寄存器组硬件来缩短被变换的虚地址中的用户位位数;每个任务的程序空间最大可达4096页,每页为512个字节,实主存容量为2^20位;设快表用按地址访问存储器构成,行数为32,快表的地址是经散列形成;为减少散列冲突,配有两套__相等比较电路请设计该地址变换机构,内容包括1画出其虚、实地址经快表变换之逻辑结构示意图;2相联寄存器组中每个寄存器的相联比较位数;3相联寄存器组中每个寄存器的总位数;4散列变换硬件的输入位数和输出位数;5每个相等比较器的位数;6快表的总容量(以位为单位)解: 1依题意得知 虚地址为34位,其中用户号为10位(对应1K的任务)、虚页号12位(每个任务4096页)、页内位移12位(每页512字节,512字节=512*8=1024*4=2^12) 实地址为20位,其中实页号8位,页内位移12位(与虚页页内位移对应) 相联寄存器的作用把10位的用户号转换为2位的ID(因为一般只有4个任务在使用),并把ID与虚地址的虚页号合并到快表中查实页号 快表的作用相当于页表,即虚页号对实页号的对应关系但又有所简化(原因是如果用用户号和虚页号与实页号对应,前者就有22位,现改进后虚页号只有14位了)2相联寄存器组中每个寄存器的相联比较位数为10(与虚地址中的用户号宽度对应) 3相联寄存器组中每个寄存器的总数为12(用户号宽度+ID宽度) 4散列变换硬件的输入位数为14位(虚页号宽度+相联寄存器中ID的宽度),输出位数为8位(与主存中的实页号宽度对应) 5每个相等比较器的位数=ID+用户虚页号nv=2+12=14位 6快表的总容量32行*(14输入位数+8(输出位数))*2=32*22*
29.考虑一个920个字的程序,其访问虚存的地址流为20,22,208,214,146,618,370,490,492,868,916,7281若页面大小为200字,主存容量为400字,采用FIFO替换算法,请按访存的各个时刻,写出其虚页地址流,计算主存的命中率;2若页面大小为100字,再做一遍;3若页面大小为400字,再做一遍;4由
1、
2、3的结果可得出什么结论?5若把主存容量增加到800字,按第1小题再做一遍,又可得出什么结论?解 1主存容量400字,页面大小200字,所以主存实页数为2; 把地址流转换为页地址流,以第一个虚地址流转换为页地址流为例说明求模公式为INT(地址/页面大小),就是把地址整除于页面大小,得INT(20/200)=0,下同,所以页地址流为001103122443 按FIFO算法得出替换过程为0(调入),0(命中),1(调入),1(命中),0(命中),3(替换0,0比1先入队,所以被替换,下同),1(命中),2(替换1),2(命中),4(替换3),4(命中),3(替换2),所以总共命中6次 故命中率H=6/12=50% 2方法同
(1)H=25% 3H=50% 4由以上结论可得,FIFO算法的条件下,当页面大小发生变化时,其命中率变化是一开始随页面大小增大命中率(第一步与第二步比较),但当页面大小增到一定时,命中率不再增加(第一步与第三步比较) 5命中率为58%,结论是如果分配给主存容量增加时可以搞高命中率
10.在一个页式二级虚拟存储器中,采用FIFO算法进行页面替换,发现命中率H太低,因此有下列建议1增大辅存容量;2增大主存容量页数;3FIFO改为LRU;4FIFO改为LRU,并增大主存容量页数;5FIFO改为LRU,并增大页面大小试分析上述各建议对命中率的影响情况解答 1增大辅存容量,对命中率H无影响 2增大主存容量页数,可普遍提高命中率 3FIFO改为LRU,一般可提高命中率 4FIFO改为LRU,并增大主存容量页数,一般可使命中率有较大提高 5FIFO改为LRU,并增大页面大小,如果原来页面很小,则会使命中率显著上升,如果原来页面很大,则会使命中率下降
11.采用组相联映象的Cache存储器,Cache为1KB,要求Cache的每一块在一个主存周期内能从主存取得主存模4交叉,每个分体宽为32位,总容量为256KB用按地址访问存储器构成相联目录表实现主存地址到Cache地址的变换,并约定用4个外相等比较电路请设计此相联目录表,求出该表之行数、总位数及每个比较电路的位数解答 设Cache地址中的组内块号为s,相联目录表的行数是2^13-s,总位数是8+2s*2^15-s,每个比较电路的位数为8+s剖析 在一个主存周期内主存能访问到的字节数为mW=4*32/8=16Byte要求Cache的每一块在一个主存周期内能从主存取得,所以,Cache中每块的块内字数不能大于16Bytes为了加速调块,一般让每块的大小等于在一个主存周期内主存能访问到的字数,即16Bytes 设Cache地址中的组内块号为s,相联目录表的行数=Cache地址内的组数Q=Cache容量/每组块数*每块大小=1KB/S*4*32=2^13/2^s*2^7=2^6-s 主存块数/Cache块数=256=2*8,所以,主存地址中的区号nd=8每个比较电路的位数=nd+s=nd+s=8+s 相联目录表的总位数=表中子目录表的个数*每个子目录表的位数*相联目录表的行数=4*nd+s+s*Q=4*8+2s*2^6-s=8+2s*2^8-snote 若认为相等比较电路的个数=组内块数,则相联目录表的行数=2^4,每个比较电路的位数=10,相联目录表的总位数=12*2^
612.有一个Cache存储器主存共分8个块0~7Cache为4个块0~3采用组相联映象,组内块数为2块,替换算法为近期最少使用算法LRU1画出主存、Cache地址的各字段对应关系标出位数图;2画出主存、Cache空间块的映象对应关系示意图;3对于如下主存块地址流124137012546472如主存中内容一开始未装入Cache中,请列出Cache中各块随时间的使用状况;4对于3指出块失效又发生块争用的时刻;5对于3求出此期间Cache的命中率解答 1主存地址、Cache地址的各字段的位数及其对应关系如下图所示 2主存块、Cache块的映象对应关系如下图所示 3Cache中各块随时间的使用状况如下图所示图中标*号的是候选替换块的块号,H命中;R替换;L失效 4发生块失效又发生块争用的时刻有
6、
7、
9、
10、
11、
12、
14、15 5Cache的块命中率Hc=3/15=
0.2剖析 由于主存块、Cache块之间存在上述的映象对应关系,主存的第
0、
1、
4、5块只能映象装入或替换物理Cache的第
0、1块;主存的第
2、
3、
6、7块只能映象装入或替换物理Cache的第
2、3块
13.采用组相联映象,LRU替换算法的Cache存储器,发现等效访问速度不高,为此建议1增大主存容量;2增大Cache的块数块的大小不变;3增大组相联组的大小块的大小不变;4增大块的大小组的大小和Cache总容量不变;5提高Cache本身器件的访问速度解答 1增大主存容量对Cache的访问时间ta基本不影响,从而对Cache的等效访问速度基本不影响 2增大Cache的块数块的大小不变一般将使Cache的命中率Hc上升,从而使ta下降,从而提高Cache的等效访问速度 3增大组相联组的大小块的大小不变一般将使Cache的命中率Hc上升,从而使ta下降,从而提高Cache的等效访问速度 4增大块的大小组的大小和Cache总容量不变一般将使ta下降,从而提高Cache的等效访问速度 5提高Cache本身器件的访问速度一般将缩短ta,从而提高Cache的等效访问速度
14.你对Cache存储器的速度不满,于是申请到一批有限的经费,为能发挥其最大经济效益,有人建议你再买一些同样速度的Cache片子以扩充其容量;而另有人建议你干脆去买更高速的Cache片子将现有的低速Cache片子全部换掉你认为哪种建议可取?你如何做决定?___?解答 Cache本身的速度与容量都会影响Cache存储器的等效访问速度如果对Cache存储器的等效访问速度不满,需要改进的话,就要作具体分析,看看现在Cache存储器的等效访问速度是否已接近于Cache本身的速度如果差得较远,说明Cache的命中率低,应从提高Cache命中率着手,包括调整组的大小、块的大小、替换算法以及增大Cache容量等如果Cache存储器的等效访问速度已经非常接近于Cache本身的速度还不能满足需要,就应该更换更高速的Cache片子 第五章 重叠、流水和向量处理机 因机器语言程序中邻近指令之间出现了关联,为防止出错不让它们同时被解释的现象,称为相关数据相关是指相邻指令的数据地址之间有关联指令相关是因为指令在程序的执行过程中允许被修改造成的 多功能静态流水线,在同一时间段内该流水线的各功能段之间只能按一种功能进行联接,只有等流水线全部流空后,才能切换成按另一种功能进行联接 多功能动态流水线,在同一时间段内该流水线的各功能段之间可以按多种不同的功能进行联接 中断和转移一样,会引起流水线断流由于发生中断的概率远低于条件转移,且中断又是随机发生的,所以,流水机器处理中断的关键在于如何处理好断点现场的保存和恢复,而不是如何缩短流水线的断流时间 设在执行指令i时有中断,断点本应是在指令i执行结束,指令i+1尚未开始执行的地方,但由于流水机器是同时解释多条指令,后续指令i+1i+
2...可能已进入流水线并被解释对于采用异步流动方式的流水线,这些后续指令中的一些可能已经流到指令i前面去了 早期的流水机器多采用不精确断点法不论指令i在流水线的哪一段发生中断,未进入流水线的后续指令不再进入,已在流水线的指令继续流完,再转入中断处理程序这样断点就不一定是指令i,而可能是指令i+1i+
2...即断点是不精确的仅当指令i在流水线的第一段呼应中断时,断点才是精确的采用不精确断点法,硬件开销少,控制简单,不利于编程和程序的排错 后来的流水机器多采用精确断点法不论指令i在流水线的哪一段发生中断,中断处理程序的现场都是对应于指令i的如果在执行第i条指令时发生了程序性错误或故障,那么断点就是i最坏的情况是指令i执行到流水线的最后一个功能段时才发生程序性错误或故障,为此,需设置很多后援寄存器,以保证流水线中断点之后后续指令的原有现场都能被保存和恢复
1.如何画流水线的状态转移图? 一个由K段组成的非线性单功能流水线,每个任务需要N拍,利用类似画时空图的方法得到该任务使用流水线各段的情况与时间的关系图,即预约表ReservationTable如果该任务第n拍用到流水线的第k段,就在相应的第n列和第k行的交叉点画√
①由预约表得出延迟禁止表FForbiddenList 得出一个任务多次流过的流水线各功能段上,后面的拍在第一拍开始之后延迟多少拍开始 将得到的拍数汇集到一起,构成延迟禁止表FForbiddenList如果后面的任务在前一任务开始之后延迟延迟禁止表F中的时钟节拍数开始,就会发生流水线功能段的使用冲突
②由延迟禁止表得出初始冲突向量CCollisionVector
③由初始冲突向量得出第二个任务可在第一个任务之后的多少拍流入流水线
④设第二个任务可在第一个任务之后的第n1,...,nx拍流入流水线,将初始冲突向量分别右移n1,...,nx位,得到x个第二个任务的冲突向量
⑤将得到的x个第二个任务的冲突向量与初始冲突向量作“按位或”运算,得出x个第三个任务的冲突向量
⑥分别作由初始冲突向量指向第三个任务的冲突向量的带箭头的线,并在线旁分别注上n1,...,nx
⑦由第三个冲突向量得出第四个任务可在第三个任务之后的多少拍流入流水线
⑧下面的过程基本上是重复了第五章 重叠、流水和向量处理机
1.假设指令的解释分取指、分析与执行3步,每步的时间相应为t取指、t分析、t执行1分别计算下列几种情况下,执行完100条指令所需时间的一般关系式a.顺序方式;b.仅“执行k”与“取指k+1”重叠;c.仅“执行k”、“分析k+1”、“取指k+2”重叠;2分别在t取指=t分析=
2、t执行=1及t取指=t执行=
5、t分析=2两种情况下,计算出上述各结果解 1执行完100条指令所需时间 a.100*t取指+t分析+t执行; b.t取指+100*t分析+99*__xt取指+t执行+t执行; c.t取指+__xt取指+t分析+98*__xt取指+t分析+t执行+__xt分析+t执行+t执行 2在t取指=t分析=
2、t执行=1的情况下,执行完100条指令所需时间 a.500 b.401 c.203 在t取指=t执行=
5、t分析=2的情况下,执行完100条指令所需时间 a.1200 b.705 c.
5102.流水线有4个功能部件组成,每个功能部件的延迟时间为△t,当输入10个数据后间歇5△t又输入10个数据,如此周期性地工作,求此时流水线的吞吐率,并画出时空图解 TP=10/14△t=5/7△t 时空图图
5.35a图
5.35b解 按图
5.35a组织的流水线时,TP=3/13△t;η=3/11 实现A*B*C*D的时空图如图0504所示 图0504 按图
5.35a组织的流水线时,TP=3/13△t;η=3/11 实现A*B*C*D的时空图如图0504所示 图0505 剖析 为了减少运算过程中的操作数相关,A*B*C*D应改为A*B*C*D进行运算
4.一个4段的双输入端规格化浮点加法流水线,每段经过时间10ns输出可直接返回输入或将结果暂存于相应缓冲器中,问最少需经多少时间能求10∑i=1Ai,并画出时空图答: 时空图如下 求10∑i=1Ai需要的最知时间是170ns剖析 为了避免先写后读相关,使流水线性能尽可能高,需将10∑i=1Ai调整成A1+A2+A3+A4+A9+A10+A5+A6+A7+A
85.为提高流水线效率可采用哪两种主要途径来克服速度瓶颈?现有3段流水线,各段经过时间依次为△t、3△t、△t,1分别计算在连续输入3条指令时和30条指令时的吞吐率和效率2按两种途径之一改进,画出你的流水线结构示意图,同时计算连续输入3条指令和30条指令时的吞吐率3通过对
1、2两小题的计算比较可得出什么结论?解答: 为提高流水线效率可采用瓶颈希再细分和瓶颈段并联两种主要途径来克服速度瓶颈 1连续输入3条指令时的吞吐率TP3=3/11△t;效率η3=5/11 连续输入30条指令时的吞吐率TP30=15/46△t;效率η3=25/46 2改进后的流水线结构示意图大体如图
5.35a和图
5.35b 连续输入3条指令时的吞吐率TP3=3/7△t;效率η3=3/7 连续输入30条指令时的吞吐率TP30=15/17△t;效率η3=15/17 3只有当连续输入流水线的指令足够多时,流水线的实际吞吐率和效率才会提高
6.有一个双输入端的加-乘双功能静态流水线,由经过时间为△t、2△t、2△t△t的
1、
2、
3、4四个子过程构成加按1-2-4连接,乘按1-3-4连接,流水线输出设有数据缓冲器,也可将数据直接返回输入现要执行A*B+C*D+E*F+G*H的运算,请调整计算顺序画出能获得尽量高的吞吐率的流水时空图,标出流水线入、出端数的变化情况,求出完成全部运算的时间及此期间流水线的效率如对流水线瓶颈子过程再细分,最少只需多少时间可完成全部运算?若子过程3不能再细分,只能用并联方法改进,问流水线的效率为多少?解: 根据题意,画出流水线吞吐率尽可能高的时空图如图0507 图0507 在此期间的流水线效率η=6*4△t+3*4△t/4*24△t=3/8 如果将瓶颈子过程2和3均细分成两个子过程,则时空图如图0508所示 图0508 由图可见,完成全部运算最少需要18△t 若子过程3不能再细分,只能用并联方法改进,则则时空图如图0509所示 图0509 这种情况下,流水线效率η=24△t+12△t/6*18△t=1/3剖析 因为是双功能静态流水线,为了能有高的吞吐率,应减少流水线的功能切换次数因此,应将算法调整成先作一连串的乘,然后再切换成一连串的加原式展开成A*B+A*C*D+A*C*E*F+G*H,先进行乘法流水,为了减少因先写后读相关而等待的时间,应尽量安排对计算式子项数最多的乘法先进行操作,即先计算A*C*E*F,再计算A*C*D,...
7.现有长度为8的向量A和B,请分别画出下列4种结构的处理器上求点积A*B的时空图,并求完成全部结果的最少时钟拍数设处理器中每个部件的输出均可直接送到任何部件的输入或存入缓冲器中去,其间的传送延时不计,指令和源操作数均能连续提供1处理器有一个乘法部件和一个加法部件,不能同时工作,部件内也只能以顺序方式工作,完成一次加法或乘法均需5拍;2与1基本相同,只是乘法部件和加法部件可并行;3处理器有一个乘、加法双功能静态流水线,乘、加法均由5个流水段构成,各段经过时间要1拍;4处理器有乘、加法两条流水线,可同时工作,各由5段构成,每段经过时间为1拍解答 1在这种结构的处理器上求点积A*B的时空图如图0510所示 图0510 完成全部运算最少需要75拍 2在这种结构的处理器上求点积A*B的时空图如图0511所示 图0511 完成全部运算最少需要45拍 3在这种结构的处理器上求点积A*B的时空图如图0512所示 图0512 完成全部运算最少需要30拍 4在这种结构的处理器上求点积A*B的时空图如图0513所示 图0513 完成全部运算最少需要26拍剖析 向量A*B的点积为A*B=8∑i=1ai*bi=a1*b1+a2*b2+a3*b3+a4*b4+a5*b*+a6*b*+a7*b7+a8*b8共需8次乘法和7次加法
8.试总结IBM360/91解决流水线控制的一般方法、途径和特点在流水线中设置相关直接通路解决局部相关;用猜测法解决全局相关;设置向后8条检查,加快短循环程序的处理;对流水线的中断处理用不精确断点法
9.在一个5段的流水线处理机上需经9拍才能完成一个任务,其预约表为t0t1t2t3t4t5t6t7t8s1∨∨s2∨∨s3∨∨∨s4∨∨s5∨∨分别写出延迟禁止表F、冲突向量C;画出流水线状态转移图;求出最小平均延迟及流水线的最大吞吐率及其高度方案按此流水高度方案输入6个任务,求实际吞吐率解 根据预约表,延迟禁止表F={1,3,4,8} 冲突向量为C:10001101 状态转移图如图0514所示 图0514 各种方案的平均延迟表调度方案25275566677平均延迟
3.
54.
555.
566.57 最小延迟为
3.5拍,其调度方案为(2,5) 按调度方案(2,5)输入6个任务时的时空图如图0515所示 图0515 实际吞吐率TP=6/25任务/拍剖析 求延迟禁止表F={1,3,4,8},第一行间隔8,第二行间隔1,第三行间隔1,3,4,然后间隔都为1,合并 求冲突向量,写一个8位两进制数,根据禁止表倒着写 由于初始冲突向量的c2c5c6c7为0,所以第二个任务可以距第一个任务2,5,6或7拍流入流水线
10.求向量D=A*B+C,各向量元素均为N,参照CRAY-1方式分解为3条向量指令1V3<-存储器{访存取A送入V3寄存器组}2V2<-V0+V1{B+C->K}3V4<-V2+V3{K*A->D}当采用下列3种方式工作时需多少拍才能得到全部结果?
(1)
1、
2、
3、串行执行;
(2)1和2并行执行完后,再执行3;
(3)采用链接技术解:
(1)每条指令所需拍数为 指令11(启动访存)+6(访存)+1(存V3)+N-1(第一个分量后每隔1拍出一个结果)=7+N 指令21(送浮加部件)+6(浮加)+1(存V2)+N-1=7+N 指令31(送浮乘部件)+7(浮乘)+1(存V4)+N-1=8+N 串行7+N+7+N+8+N=22+3N
(2)指令1和2并行执行1(启动访存,送浮加部件)+6(访存,浮加)+1(存V3,存V2)+N-1=7+N 1,2并行7+N+8+N=15+2N
(3)1+6+1+1++7+1+N-1=16+N
11.设向量长度为64,以CRAY-1机上所用浮点功能部件的执行时间分别为相加6拍,相乘7拍,求倒数近似值14拍;从存储器读数6拍,打入寄存器及启动功能部件各1拍问下列各指令组内的哪些指令可以链接?哪些指令不能链接?不能链接的原因是什么?分别计算出各指令组全部完成所需的拍数1234V0←存储器V1←V2+V3V4←V5*V6V2←V0*V1V3←存储器V4←V2+V3V0←存储器V2←V0*V1V3←V2+V0V5←V3+V4V0←存储器V1←1/V0V3←V1*V2V5←V3+V4解 13条向量指令之间既没有发生源Vi冲突,也没有Vi的先写后读相关,又不存在功能部件的使用冲突,所以这3条向量指令可以同时并行流水__x{1+6访存+1+64-11+6浮加+1+64-11+7浮乘+1+64-1}=72拍所以向量指令组全部完成需要72拍 23条向量指令之间没有功能部件的使用冲突,但是在第
1、2两条向量指令与第3条向量指令之间有V2及V3的先写后读相关只要让第1条向量指令较第2条向量指令提前1拍启动,则第12两条向量指令的第1个结果元素就可以被同时链接到第3条向量指令中__x{1+7浮乘+1+64-11+6访存+1+64-1}+1+6浮加+1+64-1=80拍 3第1条向量指令与第2条向量指令之间有V0的先写后读相关,两者可以链接第3条向量指令与第2条向量指令之间有源向量寄存器V0的冲突,它们之间只能串行第3条向量指令与第4条向量指令之间有加__能部件的使用冲突,它们之间也只能串行1+6访存+1+1+7浮乘+1+64-1+1+6访存+1+64-11+6浮加+1+64-1=222拍 44条向量指令均依次有Vi的先写后读相关,但无源Vi冲突,也无功能部件的使用冲突,所以,这4条向量指令可以全部链接在一直,进行流水1+6访存+1+1+14求倒数+1+1+7浮乘+1+1+6浮加+1+64-1=104拍
12.设指令由取指、分析、执行三个子部件组成每个子部件经过时间为△t,连续执行12条指令请分别画出在常规标量流水处理机及度m均为4的超标量处理机、超长指令字处理机、超流水线处理机上工作的时空图,分别计算它们相对常规标量流水处理机的加速比Sp解 常规标量处理机的时空图 度m为4的超标量处理机的时空图 其相对于常规标量流水处理机的加速比Sp=14△t/5△t=
2.8 度m为4的超长指令字处理机的时空图 其相对于常规标量流水处理机的加速比Sp=14△t/5△t=
2.8 度m为4的超流水线处理机的时空图 其相对于常规标量流水处理机的加速比Sp=14△t/
5.75△t=56/23≈
2.8第六章 阵列处理机 阵列处理机ArrayPro__ssor也叫并行处理机ParallelPro__ssor,指的是由单一控制单元ControlUnit控制按一定方式互连的大量重复设置的处理单元Pro__ssingUnit,实现同一指令对各处理机所分配的不同数据的并行操作 ILLIAC4中,N=sqrtN*sqrtN个处理单元组成的阵列中,任意两个处理单元之间的最短距离不大于sqrtN-1即d_min≤sqrtN-1 单级立方体网络中各处理机间信息传送的最大距离为n,即反复使用单级立方体网络,数据传送最多经过n个处理机,就可以实现任意入、出端之间的连接 单级PM2I网络中各处理机间信息传送的最大距离为n/2,即反复使用单级PM2I网络,数据传送最多经过n/2个处理机,就可以实现任意入、出端之间的连接 单级全混洗交换网络中各处理机间信息传送的最大距离为2n-1,即反复使用单级全混洗交换网络,数据传送最多经过2n-1个处理机,就可以实现任意入、出端之间的连接 SIMD系统组成的互联网络的设计目标结构简单,降低成本;互联灵活,算法应用;传送步数,提高速度;规整、模块,VLSI,扩展性 设计互联网络时应考虑的问题拓扑结构,交换方式,控制方式,操作方式 多级立方体网络、多级PM2I网络、多级混洗交换网络可以分时实现任意一个入端与任意一个出端之间的连接,但在同时实现多对入、出端之间的连接时,可能会争用数据传送线,具有这关性质的互连网络叫做阻塞式网络(BlockingNetwork),不具有这类性质的互连网络叫做非阻塞式网络或全排列网络
1.若干个处理单元的全混连接与Shuffle函数 Shuffle互联函数的意义Shuffle(Pn-1Pn-
2...P1P0)=Pn-
2...P1P0Pn-1即将二进制位最左位移到最右的位置 8个处理单元的全混连接如下图
2.多级立方体网络的画法 以N=8为例 第i级交换单元处于交换状态时,实现的是cubei互连函数 1)把3*4=12个交换单元放好 2)在i=0级,实现cube0函数,具体就是实现
(01)
(23)
(45)
(67)交换,所以A单元要把
(01)输入放在一起,通过A单元的交换状态就可以实现
(01)交换,同样BCD分别实现
(23)
(45)
(67)的交换 3)在i=1级,我们来实现cube1函数,具体就是实现
(02)
(13)
(46)
(57)交换,很简单,假设前面所有交换网络处于直连状态,找出前级的输出端口编号,把
(02)作为输入放在一起,
(13)放在一起......完成第2级; 4)同理可以完成第3级
3.部分级控制中移数函数的功能 设3级立方体网络0~7共8个端子01234567排列,采用部分极控制,进行模4移2变换,得到的8个端子新的排列是23016745 处理过程如下01234567移20+2=21+2=32+2=43+2=54+2=65+2=76+2=87+2=9模42mod4=23mod4=34mod4=05mod4=16mod4=27mod4=38mod4=09mod4=1notes与第一组冲突,所以要加42+4=6与第二组冲突,所以要加43+4=7与第三组冲突,所以要加40+4=4与第四组冲突,所以要加41+4=5 移2就是加2第六章 阵列处理机
1.画出16台处理器仿ILLIACⅣ的模式进行互连的互连结构图,列出PE0分别只经一步、二步和三步传送能将信息传送到的各处理器号答 6台处理器仿ILLIACⅣ处理单元的互连结构如图所示 图中第个PU中包含PE、PEM和MLU PE0PU0经一步可将信息传送至PU
1、PU
4、PU
12、PU15 PE0PU0至少需经二步才能将信息传送至PU
2、PU
3、PU
5、PU
8、PU
11、PU
13、PU14 PE0PU0至少需经三步步才能将信息传送至PU
6、PU
7、PU
9、PU
102.编号为
0、
1、...、15的16个处理器,用单级互连网互连当互连函数分别为1Cube32PM2+33PM2-04Shuffle5ShuffleShuffle时,第13号处理器各连至哪一个处理器?解答 15号处理器 25号处理器 312号处理器 411号处理器 57号处理器剖析 由题意知,有16个处理器,即N=16n=log2N=log216=4 Cube313=Cube31101=0101=5 PM2+313=13+2^3mod16=5 PM2-013=13-2^0mod16=12 Shuffle13=Shuffle1101=1011=11 ShuffleShuffle=Shuffle11=Shuffle1011=0111=
73.编号分别为
0、
1、
2、...、F的16个处理器之间要求按下列配对通信B、1,
8、2,
7、D,
6、C,E、4,A、0,
9、3,
5、F试选择所用互连网络类型、控制方式,并画出该互连网络的拓补结构和各级交换开关状态图解答 采用4级立方体网络,级控制该互连网络的拓补结构和各级交换开关状态图如下图所示剖析 从处理器号的配对传送关系可以转成处理器二进制编号的配对传送关系 B110110001 8210000010 7D01111101 6C01101100 E411100100 A010100000 9310010011 5F01011111 不难得出其一般规律是二进制编号为P__2P1P0的处理器与 ̄P3P2 ̄P1P0的处理器配对交换数据由于实现的都是交换函数的功能,采用成本最低的级控制多级立方体互联网络就可以实现 N=16的多级立方体网络,由n=log216=4组成每一级均使用N/2=8个二功能交换开关多级网络各级的级号由入端到出端依次为
0、
1、
2、
3.第i级的每个交换单元的配对用的是CubeiP
3...Pi...P0=P
3... ̄Pi...P0函数根据本题的要求,应当让第
1、3级的各交换单元处于“交换”状态,第
0、2级的各交换单元处于“直连”状态
4.画出编号为
0、
1、...、F共16个处理器之间实现多级立方体互连的互连网络,采用级控制__为1100从右至左分别控制第0级至第3级时,9号处理器连向哪个处理器?解答 多级立方体互连网络的图和第3题的图基本一致,不同之处在于,第
0、1级的开关状态为直连,第
2、3级的开关状态为交换 9号处理器在经过0级和1级交换开关后,连向哪第10个处理器;在经过2级交换开关后,连向第4个处理器;在经过3级交换开关后,连向第9个处理器
5.对于采用级控制的三级立方体网络,当第i级0=i=2为直连状态时,不能实现哪些结点之间的通信?___?反之,当第i级为交换状态呢?解答 当第i级为直连状态时,不能实现入、出两端的处理器二进制编码的编号中,第Pi位取反的处理器之间的连接例如,第0级为直连状态时,入端号为××0的处理器仅能与出端号为××0的处理器进行数据传送,不能与出端号为××1的处理器进行数据传送因为交换开关的直连状态被定义为i入连i出,j入连j出,所以,反映出实现互连的入、出端号的二进制码中的Pi位是不能变反的,其它的各位可以不变,也可以变反 当第i级为交换状态时,不能实现入、出两端的处理器二进制编码的编号中,第Pi位相同的处理器之间的连接例如,第0级为交换状态时,入端号为××0的处理器仅能与出端号为××1的处理器进行数据传送,不能与出端号为××0的处理器进行数据传送因为交换开关的直连状态被定义为i入连j出,j入连i出,所以,反映出实现互连的入、出端号的二进制码中的Pi位必须变反,其它的各位可以不变,也可以变反
6.假定8*8矩阵A=aij,顺序存放在存储器的64个单元中,用什么机关报单级互连网络可实现对该矩阵的转置变换?总共需要传送多少步?解答 采用单级混洗互连网络可实现对8*8矩阵的转置变换,共需传送3步剖析 8*8矩阵中任一元素aij,它在存储器中所占的位置是i*8+j即i*2^3+j每个元素的行坐标和列坐标均用3位表示,设b5b4b3为行下标的二进制编号,b2b1b0为列下标的二进制编号,经过3次全混洗后,元素下标号b5b4b__2b1b0就变成了b2b1b0b5b4b3,即行下标的二进制编号改成了b2b1b0,列下标的二进制编号改成了b5b4b3,这样,就实现了矩阵的行列转置
7.画出0~7号共8个处理器的三级混洗交换网络,在该图上实现将6号处理器数据播送给0~4号,同时将3号处理器数据播送给其余3个处理器时的各有关交换开关的控制状态解答 8个处理器的三级混洗交换网络及其交换开关控制状态设置如下图所示
8.并行处理机有16个处理器要实现相当于先4组4元交换,然后是2组8元交换,再次是1组16元交换的交换函数功能,请写出此时各处理器之间所实现的互连函数的一般式,画出相应多级网络的拓扑结构图,标出各组交换形状的状态解答 互连函数的一般式为CubeiP__2P1P0= ̄P__2 ̄P1 ̄P0 多级立方体互连网络的拓扑结构图和第3题的图基本一致,不同之处在于,第
0、
1、3级的开关状态为直连,第2级的开关状态为交换
9.具有N=2^n个输入端的Omega网络,采用单元控制1N个输入总共可有多少种不同的排列;2该Omega网络通过一次可以实现的置换可有多少种是不同的;3若N=8计算出一次通过能实现的置换数占全部排列数的百分比解答 1N个输入总共可有N!种不同的排列 2该Omega网络通过一次可以实现的置换可有2^N/2log2N=N^N/2种是不同的 3若N=8通过Omega网络一次可以实现的不重复置换有8^4=4096种;8个输入总共可实现的不重复排列有8!=40320种所以,一次通过能实现的置换数占全部排列数的百分比为4096/40320*100%≈
10.16%
10.画出N=8的立方体全排列多级网络,标出采用单元控制,实现0→31→72→43→04→25→66→17→5的同时传送时的各交换开关的状态;说明___不会发生阻塞解答 实现N=8的立方体全排列多级网络及交换形状状态如下图所示 在一到的映射时,交换开关的状态组合有许多冗余,所以不会发生阻塞
11.在16台PE的并行处理机上,要对存放在M个分体并行存储器中的16*16二维数组实现行、列、主对角线、次对角线上各元素均无冲突访问,要求M至少为多少?此时数组在存储器中应如何存放?写出其一般规则同时,证明这样存放同时也可以无冲突访问该二维数组中任意4*4子阵的各元素解答 M至少为17 数组A中的任意一个元素Aab的存放规则体号地址j=4a+bmod17,体__址i=a, 按照对应关系将各数组元素存放到m=17的并行存储器中,如下图由图可见,这样存放同时也可以无冲突访问该二维数组中任意4*4子阵的各元素16*16二维数组在并行存储器中存放的例子m=17n=16体__址i存储体号j0123456789101112131415160a00a01a02a03a04a05a06a07a08a09a010a011a012a013a014a0151a113a___a115a10a11a12a13a14a15a16a17a18a19a110a111a1122a29a210a211a212a213a214a215a20a21a22a23a24a25a26a27a283a35a36a37a38a39a310a311a312a313a___a315a30a31a32a33a344a41a42a43a44a45a46a47a48a49a410a411a412a413a414a415a405a514a515a50a51a52a53a54a55a56a57a58a59a510a511a512a
1.多处理机在结构、程序并行性、算法、进程同步、资源分配和调试上与并行处理机有什么差别?答 多处理机与并行处理机的主要差别是并行性的等级不同
(1)结构灵活性多处理机制结构灵活性高于并行处理机
(2)程序并行性并行处理机是操作级并行,并行性仅存在于指令内部,识别比较容易,由程序员掌握程序并行性的__;多处理是指令、任务、作业并行,并行性主要存在于指令外部,另外还存在于指令内部,识别比较困难,必须利用多种途径__程序的并行性
(3)并行任务派生并行处理机工作能否并行工作由指令决定,多处理机必须有专门指令指明程序能否并行执行,派生的任务数是动态变化的
(4)进程同步并行处理机的进程同步是自然的,而多处理机必须采取同步措施
(5)资源分配和任务调度多处理机的资源分配和任务调度比并行处理机复杂得多
2.多处理机有哪些基本特点?发展这种系统的主要目的可能有哪些?多处理着重解决哪些技术问题?答 ○多处理机的基本特点 多处理机具有两台以上的处理机在操作系统控制下通过共享的主存或输入/输出子系统或高速通讯网络进行通讯.结构上多个处理机用多个指令部件分别控制通过机间互连网络通讯;算法上不只限于处理向量数组还要实现更多通用算法中的并行;系统管理上要更多地依靠软件手段有效解决资源分配和管理特别是任务分配处理机调度进程的同步和通讯等问题. ○使用多处理机的目的: 一是用多台处理进行多任务处理协同求解一个大而复杂的问题来提高速度二是依靠冗余的处理机及其重组来提高系统的可靠性适应性和可用性. ○多处理着重要解决的技术问题:
(1)硬件结构上,如何解决好处理机、存储器模块及I/O子系统间的互连
(2)如何最大限度__系统的并行性,以实现多处理要各级的全面并行
(3)如何选择任务和子任务的大小,即任务的粒度,使并行度高,辅助开销小
(4)如何协调好多处理机中各并行执行任务和进程间的同步问题
(5)如何将任务分配到多处理机上,解决好处理机调度、任务调度、任务调度和资源分配,防止死锁
(6)一旦某个处理发生故障,如何对系统进行重新组织,而不使其瘫痪
(7)多处理机机数增多后,如何能给编程者提供良好的编程环境,减轻程序的复杂性
3.分别画出4*9的一级交叉开关以及用两级2×3的交叉开关组成的4×9的Delta网络,比较一下交叉开关设备量的多少?解答 4*9的一级交叉开关如下图所示 两级2×3的交叉开关组成的4×9的Delta网络如下图所示 2^2*3^3有Delta网络由5个2*3的交叉开关组成,其交叉开关的结点数由一级网络的36个减少到现在Delta网络中的2*3*5=30个剖析 第一级有2个2*3的交叉开关,第2级有3个2*3的交叉开关,级间采用混洗拓扑
4.说明4*4交叉开关组成的两级16*16交叉开关网络虽节省了设备,但它是一个阻塞式网络答 16*16交叉开关网络需要256个开关结点,每个结点中选1的多路裁决和选择电路采用4×4的交叉开关构成的二级交叉开关网络,共需要16×8=128个开关结点,每个结点只需要4中选1的多路裁决和选择电路,节省了设备但它是一个阻塞式网络因为第1级每4个输入端中只能有一个连到第2级的一个输入端,而第2级的这个输入端本可以对应4个输出端的某一个这就意味着,当第1级4个输入端中的某一个连到了最终的某个输出端时,第1级同组内其它3个输入端由于有路径冲突,就不能同时将信息传送到第2级输出相应的另外3个输出端上,而采用16×16的一级交叉开关就不存在这种问题
5.由霍纳法则给定的表达式如下E=ab+cd+ef+gh利用减少树高的办法来加速运算,要求1画出树形流程图;2确定Tp、P、Sp、Ep诸值解答 1对于原式,单处理机串行运算树形流程图如左下图所示,多处理机并行运算树形流程图如右下图所示 2P台处理机运算的级数Tp=4 所需处理机数目P=3 加速比Sp=顺序运算的级数T1/P台处理机运算的级数Tp=7/4 效率Ep=加速比Sp/所需处理机数目P=7/
126、求A
1、A
2......A8的累加和,有如下程序S1A1=A1+A2S2A3=A3+A4S3A5=A5+A6S4A7=A7+A8S5A1=A1+A3S6A5=A5+A7S7A1=A1+A5
(1)写出用FORK、JOIN语句表示其并行任务的派生和汇合关系的程序,以假想使此程序能在多处理机上运行
(2)画出该程序在有3台处理机制系统上运行的时间关系示意图
(3)画出该程序在有2台处理机制系统上运行的时间关系示意图解答 1用FORK、JOIN语句表示其并行任务的派生和汇合关系的程序如下FORK20FORK30FORK4010A1=A1+A2JOIN4GOTO8020A3=A3+A4JOIN4GOTO8030A5=A5+A6JOIN4GOTO8040A7=A7+A8JOIN480FORK6050A1=A1+A3JOIN2GOTO7060A5=A5+A7JOIN270A1=A1+A5 2在有3台处理机制多处理机系统上运行的资源时间图如下图所示假设标号为50和60的两个并发进程中,标号为60的进程最后完成 3在有2台处理机制多处理机系统上运行的资源时间图如下图所示假设标号为50和60的两个并发进程中,标号为50的进程最后完成剖析 GOTO70语句的问题关键是70语句是在50语句还是60语句所在CPU上执行的也就是说50语句和60语句谁先执行完
7、若有如下程序V=U/BW=A*UX=W-VY=W*UZ=X/Y试用FORK、JOIN语句改写成可在多处理机上并行执行的程序假设现有两台处理机,且除法速度最慢,加、减法速度最快,请画出该程序运行时的资源时间图解答 用FORK、JOIN语句改写成可在多处理机上并行执行的程序如下S1U=A+BFORKS3S2V=U/B JOIN2GOTOS4S3W=A*UJOIN2S4FORKS5S4X=W-VJOIN2GOTOS6S5Y=W*U JOIN2S6Z=X/Y 该程序在有2台处理机的多处理机系统上运行时的资源时间图如下所示
8.分别确定下列各计算机系统中,计算点积S=8∑i=1ai*bi所需的时间尽可能给出时空图示意1通用PE的串行SISD系统;2具有一个加法器和乘法器的多功能并行流水SISD系统;3有8个处理器的SIMD系统;4有8个处理器的MIMD系统设访存取指和取数的时间可以忽略不计;加与乘分别需要2拍和4拍;在SIMD和MIMD系统中处理器机之间每进行一次数据传送的时间为1拍,而在SISD的串行或流水系统中都可忽略;在SIMD系统中PE之间采用线性环形互连拓扑,即每个PE与其左右两个相邻的PE直接相连,而在MIMD中每个PE都可以和其它PE有直接的通路解答: 1利用通用PE的串行SISD系统计算点积所需时间为46拍,时空图如下图所示 2利用具有一个加法器和乘法器的多功能并行流水SISD系统计算点积所需时间为15拍,时空图如下图所示 3利用有8个处理器的SIMD系统计算点积所需时间为14拍,时空图如下图所示 4利用有8个处理器的MIMD系统计算点积所需时间为14拍,时空图如下图所示
9.设程序有T个任务,在A、B两台处理机组成的多处理机上运行每个任务在A处理机上执行的时间为E,在B处理机上执行的时间为2E,不考虑机间通讯时间,问如何分配任务,可使系统总执行时间最短?总执行时间最短为多少?解 设为A处理机分配I个任务,为B处理机分配T-I个任务则系统总执行时间最短为IE=2T-IE解得I=2T/3所以,总执行时间最短为2TE/
310.简述多处理机操作系统3种不同类型的构形列出每种构形有优点和缺点以及设计中的问题.答:类型构型优点缺点适用场合主从型管理程序只在一台指定的处理上运行硬件结构简单,控制简单对主机的可靠性要求高,灵活性差工作负荷固定,从处理机的能力明显低于主处理机各自__型控制功能分散到多台处理机,共同完成对整个系统的控制每台处理机都有一个__的管理程序操作系统的内核在运行要求管理程序必须是可再入的适应分布处理的模块化结构,对主机依赖性小,可靠性高,系统效率较高尽管每台处理机都有专用表格,但一些共享表格会增加共享冲突,加大了开销实现复杂,输入输出结构变换需要人为干预,处理机间负荷的平衡比较困难松耦合多处理机系统浮动型管理程序在处理机间浮动集中了主从型和各自__型的优点,且灵活性高设计最困难紧耦合多处理机系统,同构多处理机系统第八章 其它计算机结构第八章 其它计算机结构
1、简述脉动阵列结构的特点答
(1)结构简单,规整,模块化强,可扩充性好;
(2)处理单元间数据通信距离短,规则,使数据流和控制流的设计,同步控制均简单规整;
(3)脉动阵列机中各处理单元同时运算,并行性极高,可通过流水获得很高的吞吐率;
(4)输入数据被多个处理单元重复使用,减轻阵列与外界I/O通信量,降低系统对主存和I/O系统频宽的要求
(5)脉动阵列结构的构形与特定任务和算法密切相关,具有专用性,限制了应用范围
2、什么叫控制驱动、数据驱动、需求驱动? 答 控制流驱动:即指令的执行是在PC程序计数器的控制下,按照事先指定的序列进行的指令的执行顺序隐含在控制流中 数据流驱动:即指令的执行是按照数据相关和资源可用性确定的序列进行的,指令的执行基本上是无序的只要一条指令所需的操作数全部就绪就可以被激发并执行 需求驱动:即指令的执行是按照数据需求确定的序列进行的
3、什么叫大规模并行处理机MPP什么叫机群系统?答 MPP是大规模并行处理机,指用数百万个高性能,低成本的RISC微处理器通过互联网络互连,组成的SIMD或MIMD系统 机群系统是将多个高性能工作站或高档微型计算机使用高速通信网络加以互连组成系统
4、用结构有向图形式画出求解 x=squareroota+b*d/e-e/d 的数据流程序图,当a=
4、b=8时,表示出该数据流程序图的执行过程
5、用常用结点画出 z:=IFX=10THENX-YELSEX+Y/Y 的数据流程序图
6、画出对应于循环语句WHILEi迭代结构的数据流程序图。