第一章
1、翻译和解释的区别和联系?
区别:翻译是整个程序转换,解释是低级机器的一串语句仿真高级机器的一条语句。 联系:都是高级机器程序在低级机器上执行的必须步骤。
2、为什么将计算机系统看成是多级机器构成的层次结构?
可以调整软、硬件比例;可以用真正的实处理机代替虚拟机器;可以在1台宿主机上仿真另一台。
3、计算机系统结构用软件实现和硬件实现各自的优缺点?
硬件优点:速度快,节省存储时间;缺点:成本高,利用率低,降低灵活性、适用性。 软件优点:成本低,提高灵活性、适用性;缺点:速度慢,增加存储时间、软件设计费。
4、就目前通用机来说,计算机系统结构的属性主要包括哪些?
数据表示、寻址方式、寄存器组织、指令系统、存储系统组织、中断系统、管态目态定义与转换、
IO 结构、保护方式和机构。
5、试述由上往下、由下往上设计思路和存在的问题?
由上往下:先考虑应用要求,再逐级往下考虑怎样实现。适用于专业机
由下往上:根据已有器件,逐级往上。六七十年代通用机设计思路。
以上方法存在的问题是软、硬件脱节。
6、采用统一高级语言方法、适用场合、存在问题和应采取的策略。
定义:是指为所有程序员使用的完全通用的高级语言。
适用场合:软件移植方便。
存在问题:目前语言的语法、语义结构不同;人们的看法不同;同一语言在不同机器上不通用;程序员的习惯
应采取的策略:可一定范围内统一汇编语言,结构相同机器间搞系列机。
7、由中间开始的设计思路及优点
既考虑应用也考虑现有器件,由软硬件分界面向两端设计。
优点:并行设计,缩短周期。
8、模拟和仿真的区别
模拟:机器语言解释,在主存中;仿真:微程序解释,在控制存储器中。
9、采用系列机方法、适用场合、好处、存在问题和应采取的策略
定义:根据软硬件界面的系列结构,设计软件和不同档次的系列机器。
适用场合:同一系列内软件兼容
好处:呼应“中间开始”设计思路;缓解软件要求稳定环境和硬件发展迅速的矛盾。 存在问题:软件兼容有时会阻碍系统结构的变革。
策略:坚持这一方法,但到一定时候要发展新系列,还可采用模拟仿真。
10、为什么要进行软件移植?
软件的相对成本越来越高,应重新分配软、硬件功能。但:
成熟软件不能放弃;已有软件修改困难;重新设计软件经济上不划算。
11、除了分布处理MPP 和机群系统外,并行处理计算机按其基本结构特征可分为哪几种不同结构?例举它们要解决的问题。
流水线处理机:多个部件时间上并行执行。拥塞控制,冲突防止,流水线调度。
阵列处理机:空间上并行。处理单元灵活,规律的互连模式和互连网络设计,数据在存储器中的分布算法。
多处理机:时间和空间上的异步并行。多CPU 间互连,进程间的同步和通讯,多CPU 间调度。
数据流计算机:数据以数据令牌在指令间传递。硬件组织和结构,高效数据流语言。
12、采用模拟与仿真方法、适用场合、好处、存在问题和应采取的策略。
模拟
定义:用机器语言解释另一指令系统
适用场合:运行时间短,使用次数少,时间上无限制。
好处:可在不同系统间移植。
存在问题:结构差异大时,运行速度下降,实时性差。
策略:与仿真结合
仿真
定义:用微程序解释令一指令系统
适用场合:结构差别不大的系统
好处:运行速度快
存在问题:结构差别大时,很难仿真。
策略:与模拟结合,发展异种机连网。
13、多计算机系统和多处理机系统的区别
都属于多机系统,区别:
多处理机是多台处理机组成的单机系统,多计算机是多*立的计算机。
多处理机中各处理机逻辑上受统一的OS 控制,多计算机的OS 逻辑上独立。
多处理机间以单一数据、向量、数组、文件交互作用,多计算机经通道或通信线路以数据流形式进行。
多处理机作业、任务、指令、数据各级并行,多计算机多个作业并行。
14、各种耦合度特征
最低:无物理连接,如脱机系统。
松散:通信线路互连,适于分布处理
紧密:总线或数据开关互联,实现数据、任务、作业级并行。
15、以实例说明计算机系统结构、组成、实现的相互关系与影响。
结构相同,可用不同的组成。如系列机中不同型号的机器结构相同,但高档机往往采用重叠流水等技术。
组成相同,实现可不同。如主存可用双极型,也可用MOS 型等。
结构不同组成不同,组成的进步会促进结构的进步,如微程序控制。
结构的设计应结合应用和可能采用的组成。组成上面决定于结构,下面受限于实现。 组成与实现的权衡取决于性价比等;结构、组成、实现的内容不同时期会不同。
16、软件移植的途径,各受什么限制?
统一高级语言:只能相对统一
系列机:只能在结构相同或相近的机器间移植
模拟:机器语言差别大时,速度慢
仿真:灵活性和效率差,机器差异大时仿真困难。
17、并行处理数据的四个等级,给出简单解释,各举一例
位串字串:无并行性,如位串行计算机。
位并字串:一个字的所有位并行,如简单并行的单处理机。
位片串字并:多个字的同一位并行,如相连处理机。
全并行:同时处理多个字的多个位,如全并行阵列机。
18、设计乘法指令时,结构、组成、实现各考虑什么?
结构:是否设计乘法
组成:是否配置高速乘法器
实现:考虑器件集成度类型数量及微组装技术。
19、器件的发展对逻辑设计方法的影响
一是由逻辑化简转为采用组成技术规模生产,规模集成,并尽量采用通用器件
二是由全硬设计转为微汇编、微高级语言、CAD 等软硬结合和自动设计。
第二章
1、数据结构和机器的数据表示之间的关系?引入数据表示的基本原则?
数据结构要变换成数据表示来实现,不同的数据表示效率和方便性不同。它们是软硬件的交界面。
原则:1、是否提高效率减少时间,2、通用性和利用率。
2、简述三种面向的寻址方式的关系。
面向寄存器:速度快,增加硬件;
面向主存:速度稍慢,减少寄存器占用;
面向堆栈:速度慢,减轻编译负担。
三者各有特点,但可共同使用,不互相排斥。
3、堆栈型机器与通用寄存器型机器的主要区别?堆栈型机器对程序调用的哪些操作提供支持?
通用寄存器型对堆栈数据结构实现的支持较差:1、堆栈操作指令少;2、速度低;3、通常只用于保存返回地址。
堆栈型支持有力:1、硬件堆栈;2、堆栈指令丰富;3、支持高级语言编译;4、支持子程序嵌套和递归。可将以下信息全部压入栈:返回地址、条件码、关键寄存器内容、必要的全局
或局部参数。为子程序开辟局部变量中间结果工作区。
4、比较寻址方式在指令中的两种指明方式。
操作码中的某位。缺点:不灵活。优点:指令总长短。
设寻址方式字段。缺点:指令总长长。优点:寻址灵活。
5、“机构型”和“策略型”的含义?
机构型功能指基本的通用的功能;策略型功能指不稳定的可能会改变的功能。
6、数据描述符和向量数据表示对向量数据结构所提供的支持有什么不同?
描述方法比变址方法简便,但不能解决向量数组高速运算问题;向量处理机能快速形成元素地址,能把元素成块预取到CPU ,用一条指令同时对整个向量数组高速处理。
7、按CISC 方向改进指令系统的思路具体办法?
思路可从面向目标程序、高级语言、操作系统三个方面考虑。
面向目标程序可采用的办法:1、对高频指令增强功能加快速度,低频指令合并和取消;2、复合指令代替子程序或宏。
8、haffman 方法及优缺点?
构造方法:构造haffman 树、每个节点用01表示、从根开始01编码
优点:平均码长最短,冗余少。缺点:种类多,不易译码。
9、haffman 压缩概念的基本思想?
概率高的事件用短位数表示,低的用长位数表示。
10、以浮点数数据表示说明数的可表示精度、运算中的精度损失,尾数基值取小对哪个有利哪个不利?
数的可表示精度是数轴上数的离散程度,两个数间差越小,精度越高;运算中的精度损失指运算中尾数超长造成的损失。
尾数基值取小则可表示范围变小,个数减少,分布变密,精度提高,速度降低,对前者有利,对后者不利。
11、OS 中哪些适合硬化或固化?哪些不适合?
高频使用的机构型功能适合,策略型功能不适合。
12、什么是程序的动态再定位?
程序在主存中的实际位置可以动态移动的定位技术。可以使用基址寄存器或映象表硬件。
13、缩短地址码长度的方法
基址、变址、相对寻址、分段、寄存器寻址、寄存器间接寻址等。
14、变址和基址各适用于何种场合?设计一种只用6位地址码就可以指向一大地址空间中任意64个地址之一的寻址机构。
变址适合标量计算机中,基址主要对逻辑与物理空间进行变换,支持动态再定位。
用6位地址码表示64个地址中的任意一个,可以用隐含寻址或PC 自相对寻址形成物理地址。
15、设计RISC 机器的一般原则及可采用的基本技术?
原则:精简指令条数、格式,让指令等长,一个周期内完成,增加通用寄存器,一般指令不
可访存只能对寄存器操作,硬件实现为主,少量微程序解释,提高编译程序质量。
技术:按以上原则优化、实现指令,设置寄存器,指令采用重叠流水方式解释,采用延迟转移,提高便宜程序质量。
16、比较CISC 和RISC ,今后的发展是什么?
CISC 问题:系统庞大导致成本高可靠性低,80%指令利用率低,性价比低。
RISC 优点:简化指令系统,适合VLSI 实现,解决了CISC 的上述问题。
缺点:加重汇编语言负担,目标程序开销大,对浮点运算虚拟存储支持不强,对编译程序要求高。
发展趋势:二者互相结合,取长补短。
17、比较四种浮点数尾数下溢处理方法
截断法:将超出机器字长的部分截去,整数最大误差1,分数最大误差2^(-m),统计平均误差
舍入法:设一附加位,整数最大误差0.5,分数最大误差2^(-m-1),统计平均误差略>0,不能调节统计平均误差,实现简单增硬件少最大误差小,但速度慢需处理时间平均误差无法调节。
恒置1法:最低位恒置1,整数最大误差1,分数最大误差2^(-m),), 统计平均误差略>0,不能调节统计平均误差,实现最简单不增硬件不需处理时间,但最大误差平均误差大且无法调节。
查表舍入法:用2^k个字的ROM 或PLA 存放下溢处理表,根据查表内容处理下溢。整数、分数、统计平均误差均趋于0,能调节统计平均误差,处理速度快但需增加硬件。
1、以IBM370为例说明为什么把中断分类以及分成几类。
大型多用途机器中断源多,每个中断源单独形成入口将导致硬件实现难,代价大,因此可归类,每类给中断服务程序入口由软件转入相应处理部分。IBM370中断分为6类:机器校验,访管,程序性,外部,I/O,重新启动。
2、专用和非专用线各自的优缺点
专用线:只连接一对物理部件的总线。优点:不用争总线,控制简单,系统可靠。缺点:总线数多且长,成本高,利用率低,不易扩展。
非专用线:可被多种功能与部件共享,但同一时刻只能被一个部件使用。优点:集成度高,造价低,可扩展能力强,总线利用率高,易标准化。缺点:流量小,争用总线,部件效率低,可能成为瓶颈,可靠性差。
3、减少总线线数的方法
线的组合:减少按功能和传递方向所需的线数。
编码:对少数几根功能线进行编码取代多根单功能线。
并/串-串/并:在总线两端设置转换器,经分拆移位后在目的端形成完整的字。
4、比较几种数据宽度
单字:适合低速设备,不用指明传送信息单位,缺点是速度慢总线利用率低;
定长块:高速设备,充分利用总线宽度不用指明传送信息单位,但不灵活;
可变长块:优先级速度都高的设备,灵活需充分利用总线带宽,但需指定传送信号块大小。 单字加定长块:优先级高速度低的设备,短数据可用单字传送减少带宽浪费,信息块太小时成为单字方式总线利用率低。
单字加可变长块:普遍使用,灵活有效,但复杂开销大。
5、有通道情况下的I/O过程
a 目态程序中可安排I/O广义指令
b 运行到广义指令后,产生访管中断
cCPU 响应中断后进入管态
d 管理程序根据广义指令编写通道程序,进入通道选择设备期
e 选择通道和子通道,取出指令,选择控制器和设备,发启动命令,结束通道选择设备期 f 进入通道数据传送期,完成数据传送
g 向CPU 发I/O请求,第二次转管态,调出相应管理程序,之后CPU 返回目态。
6、比较通道的三种类型
字节多路:单字节,适于大量低速设备,字节交叉,多次选择设备,分时共享,满负荷时对通道要求的实际流量应是所连各设备的流量之和。
数组多路:定长块,适于大量高速设备,成组交叉,多次选择设备,分时共享,满负荷时对通道要求的实际流量应是所连各设备的流量最大的那个。
选择:不定长块,高优先级高速设备,独占通道,一次选择设备,独占,满负荷时对通道要求的实际流量应是所连各设备的流量最大的那个。
7、为什么中断优先级从高到低一般为:机器校验、程序性和管理程序调用、外部、I/O、重新启动?
机器校验若不及时处理,系统将无法正常工作。
程序中断若低于外部和I/O中断可能导致混乱。只有处理完机器故障后,才能进入访管中断。 重新启动一般时间并不紧迫,所以放在最后。
8、集中式串行链接的过程,优缺点,硬件故障时通讯的可靠性。
a 经公共总线向总线控制器申请
b 总线不忙时,总线控制器响应请求,送出总线可用。
c 总线可用信号在部件间串行通过,直至某个部件发生总线请求。
d 该部件获得总线使用权
e 数据传送,维持总线忙
f 传送完成,去除总线忙
g 总线请求再次建立时,重复新的分配过程。
优点:简单,线数少,可扩充性好,可靠性高。
缺点:对总线可用线及电路敏感,不灵活,速度慢。
9、集中式定时查询的过程,优缺点,硬件故障时通讯的可靠性。
a 每个部件发总线请求
b 总线不忙时,定时查询谁发的请求
c 查询到后,查询停止,该部件获得总线使用权
d 数据传送,维持总线忙
e 传送完成,去除总线忙
f 总线请求再次建立时,重复新的分配过程。
优点:灵活,可靠性高
缺点:线数多,扩展性差,控制复杂,总线分配受限计数信号。
10、集中式独立请求的优缺点,硬件故障时通讯的可靠性。
a 每个部件有总线请求和总线准许
b 总线未分配时,总线分配器根据某种算法仲裁哪个申请部件使用总线。
c 数据传送
d 传送完毕后除去总线已分配和总线准许。
优点:速度快,灵活,方便隔离失效部件
缺点:线数多,复杂。
11、在现代计算机系统中,中断系统的软硬件功能是怎样分配的,为什么这样分配? 中断响应要求快,一般用硬件实现。
中断的处理过程一般用软件,也可用硬件支持。
中断响应过程中现场的保存和恢复用硬件实现,以保证响应速度。
另一部分现场用软件实现,提高灵活性。
第四章
1、在分体交叉存储器中为什么实际频宽不随M 增大而线性增大?
M 大-数据总线长-负载重-增加门级数-增加延迟;
顺序取指效率可提高M 倍,但出现转移效率就会下降。
2、段式存储管理的地址转换过程。
程序号、段号、段内偏移量
1) 由程序号找到相应的段表基址寄存器,查到段表始址和段表长度。
2) 检查是否越界,正常转3
3) 由段表始址和段号找到装入位等相应表项
4) 装入位为1转5,否则产生缺页中断
5) 主存地址+段内偏移=物理地址
3、段页式存储管理的地址转换过程。
用户标志、段号、页号、页内偏移
1) 用户标志-段基址寄存器
2) 检查是否越界
3) 找到段表中表项
4) 检查装入位,段长
5) 找到页表中表项
6) 检查装入位
7) 实页号+页内偏移=有效地址
4、段式存储管理优缺点
优点:并行编程,缩短时间;相对独立,易于维护;实现虚拟存储;便于共享和分段保护。 缺点:主存利用率低;降低了访寸速度;空闲区管理复杂;查表速度慢。
5、分页方式的优缺点
优点:表项短,减少访表时间;零头少;速度快。
缺点:强制分页,不利于存储保护和扩充;有效地址生成慢。
6、段页式管理的优缺点
优点:具有段式、页式优点
缺点:有效地址形成慢。
7、为什么要发展存储体系
单一工艺的存储器件不能同时满足容量、速度和价格的要求;并行主存系统效果有限。所以必须使用由多种不同工艺存储器组成的存储系统,从系统结构上公斤,发展存储体系。
8、页面失效频率算法的思想
某个程序的页面失效率过高时就增加它的主存页数,过少时就减少它的主存页数,以提高总的主存利用率。
9、主存页面表实现的变形LRU 的过程
最近最久未使用算法
1) 建立主存页面表
2) 用使用位表示是否被访问过,置初值为0
3) 访问实页,则其使用位置1
4) 调入页进入占用位为0的实页,将占用位置1
5) 所有占用位为1,发生缺页时,替换使用位为0的页
6) 使用位要全1时,强制全置0。
10、页式管理中的主存页面表和页表是一张表吗?
页表是一个程序一张;主存页面表是整个主存一张。
11、比较写回法写直达法。
写回法:信息只写入CACHE ,仅需要替换时才送回主存。节省开销,但增加CACHE 复杂性。
写直达法:写入CACHE 时也写入主存。开销小,简单,但浪费时间。
12、CPU-Cache-主存层次,CPU-主存-辅存层次异同。
相同点:都需要地址映象表和地址变换机构。
不同点:
1) 前者为缩小CPU 主存速度差,后者为扩大主存容量;
2) 前者硬件后者软影结合实现地址变换;
3) 前者用页表后者用目录表实现实现地址映象表;
4) 前者CPU 与辅存之间无通路,后者缺页时CPU 采用换道办法。
13、散列法实现快表的地址变换过程
1)A=H(Nv)
2) 查找Nv 时,经同样函数变成A ,再找到Nv 内容。
3) 地址变换时先查快表再查慢表
14、有Cache 时,给出一个主存地址访存过程
1) 将主存与Cache 分成大小相同的块
2) 判断要访问的主存地址块号是否在Cache 中
3) 若在,变换为Cache 号,访问Cache
4) 若不在,将该信息由主存调入Cache 和CPU
5) 若Cache 已满,则替换Cache 信息,修改相应表格。
15、比较Cache-主存层次的几种地址变换方式
全相联映象和变换。过程:主存分为块号和块内地址;块号同目录表比较;相同则Cache 块号和块内地址形成Cache 地址;不同则缺块,调块。目录表长:Cache ;宽:主存块号+Cache块号。优点:块冲突低,空间利用率最高;缺点:映象表长,查表速度慢。
直接映象及变换。过程:区号块号块内地址;主存地址中截取Cache 地址;根据块号读出目录表中区号与主存地址区号比较;相等则命中否则访主存。目录表长:Cache ;宽:主存地址位-Cache 地址位。目录表小,成本低速度快,但冲突概率大Cache 利用率低。
组相映象及变换。区号组号块号内地址;用组号选组;对该组区号+块号全相联比较;找不到失败找到则Cache 块号组号块内地址形成Cache 地址。目录表长2^ncb,Cache表大小(区号+2块号) 位(区号+块号) 位参与比较。集中全相联和直接映象的优点弥补它们的缺点,但块冲突>全相联,Cache 利用率直接方式。
16、什么是堆栈型的替换算法
满足n
n>=Lt时,Bt(n)=Bt(n+1)
n :分配给程序的实页数
Bt(n):t 时刻在实页中的页面集合
Lt :t 时刻处理过的不同的虚页数
17、主存实际频宽与模数m 的关系是什么?原因?指令流与数据流随机时,主存实际频宽与模数m 有什么关系?
主存实际频宽随模数增大而增大,但增量会减小。这是因为程序会有转移,数据分布有随机性。完全随机时,大致成平方根关系增大。
18、CPU 写Cache 时,会发生Cache 与主存的对应副本内容不一致,如何解决?需增加什么开销?
写回法:仅Cache 替换时才写回主存。每个Cache 块需增加一个修改位的资源开销。 写直达法:同时写入Cache 和主存,需增加时间开销。
19、二级虚拟储存层次的等效访问时间与主辅存访问时间有什么关系?提高存储层次的访问
速度,可采取的措施有哪些?
主辅存的访问时间为T1和T2,等效访问时间TA=HT1+(1-H)T2,H为主存命中率。可采取的措施
TA>>主存访问周期时,可用改进替换算法、增大主存容量等办法来提高H ;
H 很高时,可降低T1;
加快地址映象和变换,如采用快慢表,增大快表命中率等。
20、解释页面失效、页面争用,什么时候同时发生,什么时候不同时发生?
虚页不在主存中,会发生页面失效。页面调入主存时,其位置被其它虚页占用,会发生页面争用。分配给程序的内存被全部占用后,会同时发生。反之不同时发生
第五章
1、试举例说明什么是“先读后写”,“写-写”,“先写后读”相关?
设有指令h,i,j,k,l,m,n 依次流入流水线,若i 要读数的单元正是k 写数的单元,正常顺序是i 先读,k 再写。但由于异步流动下,k 可能先于指令i 被解释,从而i 读到的是不正确数据(正常数据应该是k 写之前的) ,这种相关称为“先读后写”相关。若i ,k 向一单元写数据,正常情况下最后单元中应保存k 写的数据,但由于异步流动,k 可能先于i 写数据,使该单元最后结果不正确,这种相关称“写-写”相关。类似可知“先写后读”相关。
2、解决通用寄存器数相关有几种方法?试作简单比较。
方法1:
推后“分析k+1”读。可将“分析k+1”推到“执行k”结束时,也可以使它们部分重叠,只要“分析k+1”能取得正确操作数即可。缺点:它们是以牺牲速度为代价。优点:不增加设备。 方法2:
设置“相关专用通路办法”。在运算器输出到输入之间增设“相关专用通路”,保证在“执行k+1”之前输入中已获得正确信息。优点:重叠速度不下降。缺点:增加设备为代价。
3、为实现指令重叠解释可能采取哪些办法?简单分析其特点?
方法1:
让操作数和指令分别存放在两个独立编址且可同时访问的存储器中。优点:有利于实现指令的保护。缺点:主存总线控制复杂,软件设计麻烦。
方法2:
指令和操作数混存在多体交叉主存结构中,只要指令和操作数不在一个分体时就在一个主存周期取得。优点:实现上简单,开销少。缺点:当指令和操作数在同一体时无法重叠。 方法3:
增设FIFO 工作的指令缓冲寄存器。当主存空闲时预取下几条指令到指缓。优点:微操作可分成分析指令和执行指令两部分。缺点:数据相关问题。
4、试比较几种指令级高度并行的超级处理机
超标量处理机:配置多套功能部件辅助电路,靠编译程序优化指令顺序,使流水吞吐率提
高。优点:硬件不调整指令顺序、容易实现、适合矩阵计算。缺点:开销大。
超长指令字处理机:编译程序将选择可并行指令放入一条超长指令中,运行时指令中每个操作段控制一功能部件。优点:硬件结构和指令系统简单、无增加硬件开销、指令级并行性高。缺点:指令结构与一般计算机不兼容、指令结构不灵活浪费指令存储空间、不适于一般领域。
超流水线处理机:利用时间并发性,利用较短时钟周期提高流水线速度。优点:开销小。缺点:必须有高速时钟机。
5、流水线按级别分成几类?线性流水线与非线性流水线有什么区别?动态流水线和静态流水线有什么区别?
流水线按级别分部件级、处理机级和系统级三级。线性流水线段间无反馈或超过的通路,非线性流水线则有反馈回路或前越通路。静态和动态流水都是多功能的流水。其中,动态流水线按一种功能流水未完成之前,可重组开始另一种功能的流水。静态流水线必须等流水线排空之后才可进行功能切换。
6、在“一次重叠”的机器中,会出现哪些相关?如何处理?
转移指令与后续指令相关:减少使用转移指令,需要使用时可采用延迟转移技术。
指令相关:不允许程序在执行过程中修改指令,需要修改指令时可用类似于IBM370的执行指令,变指令相关为操作数相关,统一按操作相关去处理。
主存空间数相关:在存储控制器中,写数申请优先于读数申请被响应变址值二次相关,设置变址值相关专用通路。
通用寄存器组的变址值一次相关:设置变址值相关专用通路,并推后后续指令的分析。
7、为处理流水机器的全局性相关,可以加快或提前形成转移指令所需的条件码,那么可从哪两方面考虑?举例说明。
一是加快单条指令内部条件码的形成。如有的指令,象乘、除指令只要取出操作数,利用其数的符号位是同号,还是异号,就可以判定结果的正负。而是在一段程序内提前形成条件码,例如,在循环程序中,将控制循环变量改值的指令提前到循环体开始处。在硬件上设置专用的条件码寄存器,以便在判断是否循环时,已提前产生了条件码。
8、解释重叠方式中的“一次重叠”的含义。
将指令的解释分为“分析”和“执行”两个阶段,任何时刻都只是“执行k”与“分析k+1”在时间上重叠,也就是让指令分析部件与指令执行部件同时处理相邻的两条指令。
9、什么是流水线的速度瓶颈?消除流水线速度瓶颈的方法有哪两种,举例示意说明。 流水线中经过时间最长的功能段就是流水线中的速度瓶颈。清除流水线的速度瓶颈的方法,一是将瓶颈过程再细分。例如,流水线瓶颈段为2Δt,其它各段均为Δt,则可将该瓶颈段再细分成两个子段,各子段经过时间均为Δt;二是将瓶颈子过程多套并联,如上例,将瓶颈重复设置两个,任务错开一个Δt时间分配给这两个段。
10、流水机器的中断处理有哪两种方法,各有什么优缺点?
流水机器的中断处理有不精确断点法和精确断点法两种。
不精确断点法好处是控制处理简单,缺点是程序排错不利。精确断点法,中断现场准确对应于发出中断的指令,有利于程序的排错,但不利之处是需要大量后援寄存器。
11、在流水机器中,全局性相关指的是什么?处理全局性相关的方法有哪些?简要说明。 全局性相关是转移指令与其后续指令之间的相关。
处理方法有:
猜测法,猜选其中一个分支继续流入,待条件码形成后再决定是继续执行,还是作废,按另一分支重新流入。
提前形成转移所需的条件,包括指令内或程序段内条件码的提前生成。
加快短循环程序的处理,判断如属于短循环,将循环体内各指令一次取入指令缓冲器中,停止预取指令;猜选分支恒选循环分支。
12、流水处理的主要技术途径是什么?在CPU 中可以有哪两类流水?在存储系统或存储体系中举出两个应用流水的例子。
流水处理的主要技术途径是时间重叠和功能部件专用化。CPU 内部可以有指令流水线和运算操作流水线。在存储体系中CACHE 存储器的查地址映象表和访物理CACHE 可以流水。存储器系统中,主存模m 多体交叉对各分体的交叉访问也可以看成是一种流水。
第六章
1、试分析阵列处理机特点。
(1)阵列处理机提高速度是利用资源重复,利用并行性中的同时性;
(2)处理单元同等地担负起各种运算,其设备利用率可能不那么高;
(3)速度提高在硬件价格大幅度下降情况下,潜力巨大;
(4)互连网络对系统性能影响显著;
(5)互连网络使阵列处理机比固定结构的单功能流水线灵活;
(6)阵列处理机结构和所采用并行算法紧密联系;
(7)阵列处理机还必须提高标量处理速度。
总之,阵列处理机实质上是专门对付数组运算的处理单元阵列组成的处理机、专门从事处理单元阵列控制及标量处理的处理机和专门从事输入输出及操作系统管理的处理机组成的一个异构型多处理机系统。
2、试比较阵列机的两种基本形式
(1)分布式存储器阵列机。a 、各处理单元PE 有局部存储器,被分布数据只能被本处理单元直接访问。b 、在控制部件CU 内有主存储器。运行时所有指令都在CU 中,只把适合并行处理的“向量类”指令播给各PE ,并控制各PE 并行执行。c 、各PE 可通过互连网ICN 交换数据。d 、PE 通过CU 连到管理处理机SC 上,用于管理系统资源。
(2)集中式共享存储器阵列机。a 、K 个存储体集中组成,经互连网络为全部N 个处理单元共享。其中K 等于数据处理单元数。b 、互连网用于处理单元与存储分体之间进行转接构成数据通路。
3、试比较多级互连的几种网络
ATRAN----拓扑结构:第I 级交换单元处于交换方式时,实现Cubei ;控制方式:级控制分
级控制;交换单元:二功能交换单元。
间接二进制N 方体----拓扑结构:第I 级交换单元处于交换方式时,实现Cubei ;控制方式:单元控制;交换单元:二功能交换单元。
多级混洗omega----拓扑结构:每一级有一个全混拓扑和一列四功能交换单元;控制方式:单元控制;交换单元:四功能交换单元。
多级PM2I----拓扑结构:每级按PM2I 连接;控制方式:级控制或单元控制;交换单元:二功能交换单元。
全排列Benes----拓扑结构:三维立方体多级网络与它的逆网络连在一起,省去中间重复一级;控制方式:单元控制;交换单元:二功能交换单元。
4、试说明间接二进制n 方体网络是阻塞式网络
N个端要实现任意排列,应有N !种。
而单元控制的N=lnN/ln2级间接二进制方体网络中,每级有N/2个开关,N 级互连网交换开关总数为(NlnN/ln2)/2。
要实现入、出端的一一映射,每个开关只能取直接或交换两种功能。
所以开关状态总共有2^[(NlnN/ln2)/2],即N^(N/2)种。
当N>2时,N^(N/2)
所以它无法表示所有N !排列,所以当多个入出端同时连接时可能发生冲突,即间接二进制N 方体网络是阻塞式网络。
5、试比较互连网动态拓扑结构的两种形式
动态单极网络指网络只有有限几个连接,必须经循环多次通过,才能实现任意两个处理单元之间的信息传送。节省设备,但通过时间长,对网络控制要求高。
动态多极网络指由多个动态单极网络串联组成的网络。通过时间短,灵活性好,可利用不同单极互连网络组合成有不同特征和连接模式的多级互连网络。缺点是:增加设备和成本。
6、试比较单级互连的几种函数
Cube
相连的2个处理单元其二进制编号只有一位不同。Cubei, 其第i 位取反。有logN(以2为底,下同) 种函数,任意两点最大距离是logN, 最多使用logN 次函数可实现任意入出端连接,可逆。
PM2I
J号处理单元直接连接的结点是J±2^i(0≤i≤logN-1) 。PM2±i(j)=j±2^i(0≤i≤logN-1,0≤j≤N-1。有2logN-1种函数,任意两点最大距离是N/2,最多使用2次函数可实现任意端连接,可逆。 混洗
每个结点连到另一个二进制结点最低位是其最高位的结点。Shuffer(Pn-1...P1P0)=Pn-2...P1P0Pn-1。有2种函数,任意两点最大距离是2logN-1,最多使用2logN-1次函数可实现任意入出端的连接,不可逆。
7、单指令流多数据流的并行处理机在系统组成上应包含哪些部分和功能?
重复设置大量的处理单元用规整灵活的互连函数互连,组成处理单元阵列;
用专门的并行算法对数组、向量中的元素进行并行处理;
用一台高性能处理机来进行标量处理和控制互连网络的连接;
用一台管理处理机来运行系统程序和输入输出任务。
8、什么是全排列网络?实现全排列网络有哪两种方法?
可实现N 个入端的所有N !种排列的网络称全排列网络,即N 个端所有一到一的传送都不会发生传送路径使用冲突的互连网络。
实现全排列网络的出方法有:
在多级互连网络的输出端设置锁存器,使输出端的数据再一次通过多级互连网络;
将两个多级互连网络,即一个正网络和一个逆网络串接起来,合并掉中间的一级,组成2logN-1级的多级网络。
第七章
1、简述紧耦合和松耦合的多机系统结构。
各处理机之间通过互连网络共享主存的紧耦合多处理机。紧耦合系统由P 台处理机,m 个存储器模块,d 个I/O通道和3个互连网络构成。处理机-存储器网络实现处理机与各存储模块的连接。处理机中断信号网络实现多处理机之间的互连。处理机-I/O互连网络实现处理机与外设的连接。每个处理机可自带局部存储器,也可自带Cache 。存储器模块可采用流水工作方式。紧耦合系统多用于并行作业中的多任务,一般处理机是同构的。
各处理机间通过共享I/O子系统、通道或通信线路实现机间通信,不共享主存的是松耦合系统。松散耦合多处理机由P 个处理机,一个通道,一个仲裁开关和消息传送系统。每个处理机带有一个局部存储器和一组I/O设备。在仲裁开关的通道中有高速通信存储,用来缓冲传送的信息块。松散耦合多处理机较适合粗粒度的并行计算。
2、简述对树形结构进行变换的过程
首先利用交换律把相同的运算集中在一起。然后利用结合律把参加这些运算的操作数配对,尽可能并行运算,从而组成树高最小的子树。最后再把这些子树结合起来,用分配律进一步降低树高。
3、试比较3种类型的多处理机操作系统
主从型:管理程序只在一台处理机上运行。硬件结构简单,控制简单,但对主机可靠性要求高,灵活性差。为目前大多数多处理机操作系统采用,工作负荷固定,从处理机能力明显低于主处理机,或由功能差别大的多个处理机组成的异构型系统。
各自独立型:控制分散到多台处理机,共同完成对整个系统的控制工作。适合分布计算模式,对主机依赖性差,可靠性高;但实现复杂,共享表格访问冲突,处理机负荷平衡较困难。适用于松耦合处理机系统。
浮动型:管理程序在处理机间浮动。灵活性高,但发生访问表格冲突,设计较困难。适合紧耦合多处理机系统,特别是共享主存和I/O子系统的同构多处理机系统。
4、比较多处理机系统中数据相关的处理方式
并行 顺序串行 交换串行
“先读后写” 可以(有条件) 可以 不可以
“写-写” 可以(有条件) 可以 不可以
“先写后读” 不允许 可以 特殊情况可以
“先读后写”和“先写后读” 必须 不允许 不允许
无任何相关 可以 可以 可以
5、多处理机系统与并行处理机的主要差别是什么?多处理机系统主要解决的技术问题是什么?
有差别的原因是并行性等级不同,多处理机系统是任务级并行,并行处理机是操作级并行。具体讲:
1)结构灵活性不同。
2)程序并行性等级不同。软硬件支持不同。
3)并行任务派生的方式不同。并行处理机能否并行工作由指令决定;多处理机必须有专门指令指明程序段能否并行执行,派生的任务数是动态变化的。
4)进程同步。并行处理机工作同步是自然的,而多处理机必须采取同步措施。
5)资源分配和任务调度,多处理机比并行处理机任务调度复杂。
多处理机必须解决的技术问题:
1)硬件结构上多处理机、主存、I/O子系统之间应有高带宽、低价格、灵活无规则的互连,尽可能不发生信息传送的路径冲突。
2)从并行语言、并行算法、编译等上,最大限度地开发出程序的并行性,实现多处理机各级的全面并行。
3)大的任务如何细分成多个子任务、任务的粒度选择
4)从操作系统上解决好多处理机间、并行任务的分配、调度和资源分配;任务或进程间的同步死锁和竞争等问题的解决。
5)系统的重组及良好的编程环境
6、简述JOIN 语句和FORK 语句的基本功能。
FORK m的功能:
1)准备好新进程启动和执行的必须信息
2)将空闲处理机分配给派生的新进程,若没有,则排队等待
3)继续在原处理机上执行FORK m语句的原进程
JOIN n的功能:
1)JOIN语句将计数器初始化为0;
2)执行一次JOIN 语句,计数器+1,并与n 比较
3)若相等,则允许进程通过JOIN 语句,计数器清0,进程继续执行
4)若不相等,则执行JOIN 语句的进程结束,释放处理机
7、试比较机间互连的几种形式。
总线形式:处理机与外部存储器模块通过总线相连。结构简单、成本低、扩展性好;但总线失效敏感,存在总线争用。适合处理机较少、系统信息流量少、机数可扩充情况。
环形互连:各处理机点点相加成环。结构简单、成本低、不争用总线;但信息传输有延迟。
适合处理机较少、使用高宽带的光纤通信、系统流量高、机数可扩充的情况。
交叉开关:用纵横开关阵列将存储器模块、I/O通道相连。不争用开关;但开关阵列复杂,设备量较大。适合处理机数较多(但不超过16) 、系统流量大、处理机数可扩充的情况。 多端口存储器:将交叉开关移到存储器接口中。不争用总线,但存储器接口复杂,较难控制。适合处理机数少、不能扩充(一般是2台) ,系统流量高的情况。
开关枢纽结构:把交叉开关设置在各处理机或接口内部。所有开关枢纽数量少,可用较短路径与处理机连接;但开关枢纽较复杂。适合处理机数多、可扩充、分布结构情况。
8、多处理机在结构与并行性方面与阵列处理机有什么不同?
结构方面:阵列处理机的互连较规整,有一定专用性,互连的处理单元数量大;多处理机要采用更灵活多变的结构,实现复杂的互连模式,互连的处理机数量少。
并行性方面:阵列处理机是操作级并行,是并行性的同时性;多处理机是作业、程序、任务级的并行,同时包含指令内部操作间的并行,是并行性的并发性。
9、多处理机中的并行性表现在哪些方面?开发多处理机的并行性有哪些途径?
多处理机主要实现作业之间、程序段之间、任务之间的并行,也可包含有指令级、指令内部各微操作之间的并行。
多处理机的并行性可利用并行算法、并行程序设计语言、并行编译、并行操作系统以及指令硬件等多种途径来开发和实现。
第八章
1、什么脉动阵列机,其结构特点是什么?
它是具有脉动阵列结构的处理机。脉动阵列结构由一些处理单元加上若干锁存器构成。阵列内所有处理单元的数据锁存器受同一时钟控制,运算时数据在阵列结构的各个处理单元之间沿着各自的方向同步前进。就象血管液流一样,称为脉动阵列机。
脉动阵列机的结构优点是:
(1)结构简单,规则,模块化强,可扩充性好;
(2)处理单元间数据通信距离短,规则,使数据流和控制流的设计,同步控制均简单规整;
(3)脉动阵列机中各处理单元同时运算,并行性极高,可通过流水获得很高的吞吐率;
(4)输入数据被多个处理单元重复使用,减轻阵列与外界I/O通信量,降低系统对主存和I/O系统频宽的要求。
脉动阵列机的缺点是:其构形与特定任务和算法密切相关,具有专用性,限制了应用范围。
2、什么是控制流工作方式?什么是数据流工作方式?对两者进行比较。
控制流工作方式是指计算机在程序计数器集中控制下,顺次执行指令。
数据流工作方式是只要一条或一组指令所要求的操作数全部准备就绪,就可立即激发相应的指令或指令组执行,执行的结果又可能激发等待该执行结果的一些指令。下面对两者进行比较。
控制流方式:通过访问共享存储单元让数据在指令间流动;指令执行顺序隐含在控制流中,受程序计数器控制;专门使用控制操作符来实现并行处理;有程序计数器;有数组。
数据流方式:没有共享存储数据的概念,是数据的显式流动(数据令牌) ;受数据相关性的
制约,基本上无序;不需要检查和定义程序中的并行性;无程序计数器;无数组。
3、试简述数据流机的特点
对提高并发处理效能非常有利。
(1)对强相关性的程序,数据流机的效能反而比传统控制流机效率还低;
(2)在数据流机中为建立、识别、处理数据令牌标记,需时间和空间开销;
(3)数据流机不保存数据组,对数组、递归等高级操作较难管理;
(4)数据流机中变量代表数值不代表存储单元,所以程序员无法控制存储分配;
(5)数据流机中互连网络设计困难,I/O系统也不完善;
(6)数据流机中没有程序计数器,使诊断和维护较难。
4、简述规约机的结构特点
规约机是需求驱动的数据流型机器,驱动的来源是表达式的规约,所以它必须针对函数程序设计语言的特点,支持函数式程序运行。结构特点如下:
(1)面向函数式语言,或以函数式语言为机器语言非V onNeuman 机器。要有函数定义存储器和表达式存储;操作和数据合并存储。
(2)具有大容量物理存储器并采用大虚存容量的虚拟存储器,满足规约对动态存储分配和所需存储空间大的需求。
(3)处理部分应当是一种有多处理机并行的结构形式,以发挥函数式程序并行处理的特长。
(4)采用适合于函数式程序运行的多处理机互连结构。
(5)使多处理机负荷平衡。
5、试简单比较串规约机和图规约机
串规约机是使用串规约方式工作的规约机。函数定义等的存储方式是串;不能共享子表达式;多次应用共享子表达的时间开销大;要求存储衔接;存储空间利用率低;可靠性高。 图规约机是使用图规约方式工作的规约机。函数定义等的存储方式是图;能共享子表达式;多次应用共享子表达的时间开销小;不要求存储衔接;存储空间利用率高;可靠性低,存在单点瓶颈。
6、试比较静态数据流机和动态数据流机
(1)静态数据流机的数据令牌无标号;动态数据流机的数据令牌有标号。
(2)静态数据流任意给定时刻当结点操作时每条弧上只能有一个数据令牌;动态数据流机中,任何一条弧上可出现多个不带目标号的数据令牌。
(3)静态数据流机中必须设控制令牌以满足要求;动态数据流机中不必设控制令牌,因为令牌有识别时间、先后关系的标号;
(4)静态数据流机不支持递归的并发激活,只支持一般循环;动态数据流支持递归的并发激活。
(5)静态数据流机不需硬件完成标记的匹配;动态数据流机需要硬件将标记附加在数据令牌上,并完成对标记的匹配工作。
7、什么是MPP ?什么是机群系统?将机群系统与传统并行系统做比较。
MPP是大规模并行处理机,指用数百万个高性能,低成本的RISC 微处理器通过互连网络
互连,组成的SIMD 或MIMD 系统。
机群系统是将多个高性能工作站或高档微型计算机使用高速通信网络加以互连组成系统。 机群系统与传统并行处理系统相比有以下几个优点:
(1)高的性能价格比。因为工作站或微机都是批量生产,价格低;
(2)系统开发周期短,因为主机、网络、操作系统都不需要新设计;
(3)系统可扩展性好。采用通用网络,易于扩展;
(4)系统资源利用率高,工作站的不能性能相互补充,结构灵活;
(5)用户投资风险小。每个出结点既可以进行大规模并行处理也可做单机使用;
(6)用户编程方便。不需修改编程环境。
8、简单比较数据驱动方式和需求驱动方式。
相同点:都属于数据流模型
不同点:
(1)数据驱动的操作是按输入数据的可用性决定次序的。需求驱动操作是按数据需求所决定的次序进行的。
(2)数据驱动是提前求值策略,只要所要求的输入数据全部就绪,即可驱动操作进行。需求驱动是滞后求值策略。只有当某一函数需用到一自变量时,才驱动对该自变量的求值。
(3)需求驱动比数据驱动可减少许多不必要的求值,系统效率高。
(4)需求驱动比数据驱动更适合于面向函数程序设计的计算机。
9、什么是活动膜片?
活动膜片是数据流程序图的一种表示方法,它接近于机器语言。数据流程序图可看成是一组活动膜片的集合。每个活动膜片由4个域组成:操作码域、两个操作数域、目的域。实际上活动膜片就是结点在数据流机器内部具体实现时的存储器映象。
第一章
1、翻译和解释的区别和联系?
区别:翻译是整个程序转换,解释是低级机器的一串语句仿真高级机器的一条语句。 联系:都是高级机器程序在低级机器上执行的必须步骤。
2、为什么将计算机系统看成是多级机器构成的层次结构?
可以调整软、硬件比例;可以用真正的实处理机代替虚拟机器;可以在1台宿主机上仿真另一台。
3、计算机系统结构用软件实现和硬件实现各自的优缺点?
硬件优点:速度快,节省存储时间;缺点:成本高,利用率低,降低灵活性、适用性。 软件优点:成本低,提高灵活性、适用性;缺点:速度慢,增加存储时间、软件设计费。
4、就目前通用机来说,计算机系统结构的属性主要包括哪些?
数据表示、寻址方式、寄存器组织、指令系统、存储系统组织、中断系统、管态目态定义与转换、
IO 结构、保护方式和机构。
5、试述由上往下、由下往上设计思路和存在的问题?
由上往下:先考虑应用要求,再逐级往下考虑怎样实现。适用于专业机
由下往上:根据已有器件,逐级往上。六七十年代通用机设计思路。
以上方法存在的问题是软、硬件脱节。
6、采用统一高级语言方法、适用场合、存在问题和应采取的策略。
定义:是指为所有程序员使用的完全通用的高级语言。
适用场合:软件移植方便。
存在问题:目前语言的语法、语义结构不同;人们的看法不同;同一语言在不同机器上不通用;程序员的习惯
应采取的策略:可一定范围内统一汇编语言,结构相同机器间搞系列机。
7、由中间开始的设计思路及优点
既考虑应用也考虑现有器件,由软硬件分界面向两端设计。
优点:并行设计,缩短周期。
8、模拟和仿真的区别
模拟:机器语言解释,在主存中;仿真:微程序解释,在控制存储器中。
9、采用系列机方法、适用场合、好处、存在问题和应采取的策略
定义:根据软硬件界面的系列结构,设计软件和不同档次的系列机器。
适用场合:同一系列内软件兼容
好处:呼应“中间开始”设计思路;缓解软件要求稳定环境和硬件发展迅速的矛盾。 存在问题:软件兼容有时会阻碍系统结构的变革。
策略:坚持这一方法,但到一定时候要发展新系列,还可采用模拟仿真。
10、为什么要进行软件移植?
软件的相对成本越来越高,应重新分配软、硬件功能。但:
成熟软件不能放弃;已有软件修改困难;重新设计软件经济上不划算。
11、除了分布处理MPP 和机群系统外,并行处理计算机按其基本结构特征可分为哪几种不同结构?例举它们要解决的问题。
流水线处理机:多个部件时间上并行执行。拥塞控制,冲突防止,流水线调度。
阵列处理机:空间上并行。处理单元灵活,规律的互连模式和互连网络设计,数据在存储器中的分布算法。
多处理机:时间和空间上的异步并行。多CPU 间互连,进程间的同步和通讯,多CPU 间调度。
数据流计算机:数据以数据令牌在指令间传递。硬件组织和结构,高效数据流语言。
12、采用模拟与仿真方法、适用场合、好处、存在问题和应采取的策略。
模拟
定义:用机器语言解释另一指令系统
适用场合:运行时间短,使用次数少,时间上无限制。
好处:可在不同系统间移植。
存在问题:结构差异大时,运行速度下降,实时性差。
策略:与仿真结合
仿真
定义:用微程序解释令一指令系统
适用场合:结构差别不大的系统
好处:运行速度快
存在问题:结构差别大时,很难仿真。
策略:与模拟结合,发展异种机连网。
13、多计算机系统和多处理机系统的区别
都属于多机系统,区别:
多处理机是多台处理机组成的单机系统,多计算机是多*立的计算机。
多处理机中各处理机逻辑上受统一的OS 控制,多计算机的OS 逻辑上独立。
多处理机间以单一数据、向量、数组、文件交互作用,多计算机经通道或通信线路以数据流形式进行。
多处理机作业、任务、指令、数据各级并行,多计算机多个作业并行。
14、各种耦合度特征
最低:无物理连接,如脱机系统。
松散:通信线路互连,适于分布处理
紧密:总线或数据开关互联,实现数据、任务、作业级并行。
15、以实例说明计算机系统结构、组成、实现的相互关系与影响。
结构相同,可用不同的组成。如系列机中不同型号的机器结构相同,但高档机往往采用重叠流水等技术。
组成相同,实现可不同。如主存可用双极型,也可用MOS 型等。
结构不同组成不同,组成的进步会促进结构的进步,如微程序控制。
结构的设计应结合应用和可能采用的组成。组成上面决定于结构,下面受限于实现。 组成与实现的权衡取决于性价比等;结构、组成、实现的内容不同时期会不同。
16、软件移植的途径,各受什么限制?
统一高级语言:只能相对统一
系列机:只能在结构相同或相近的机器间移植
模拟:机器语言差别大时,速度慢
仿真:灵活性和效率差,机器差异大时仿真困难。
17、并行处理数据的四个等级,给出简单解释,各举一例
位串字串:无并行性,如位串行计算机。
位并字串:一个字的所有位并行,如简单并行的单处理机。
位片串字并:多个字的同一位并行,如相连处理机。
全并行:同时处理多个字的多个位,如全并行阵列机。
18、设计乘法指令时,结构、组成、实现各考虑什么?
结构:是否设计乘法
组成:是否配置高速乘法器
实现:考虑器件集成度类型数量及微组装技术。
19、器件的发展对逻辑设计方法的影响
一是由逻辑化简转为采用组成技术规模生产,规模集成,并尽量采用通用器件
二是由全硬设计转为微汇编、微高级语言、CAD 等软硬结合和自动设计。
第二章
1、数据结构和机器的数据表示之间的关系?引入数据表示的基本原则?
数据结构要变换成数据表示来实现,不同的数据表示效率和方便性不同。它们是软硬件的交界面。
原则:1、是否提高效率减少时间,2、通用性和利用率。
2、简述三种面向的寻址方式的关系。
面向寄存器:速度快,增加硬件;
面向主存:速度稍慢,减少寄存器占用;
面向堆栈:速度慢,减轻编译负担。
三者各有特点,但可共同使用,不互相排斥。
3、堆栈型机器与通用寄存器型机器的主要区别?堆栈型机器对程序调用的哪些操作提供支持?
通用寄存器型对堆栈数据结构实现的支持较差:1、堆栈操作指令少;2、速度低;3、通常只用于保存返回地址。
堆栈型支持有力:1、硬件堆栈;2、堆栈指令丰富;3、支持高级语言编译;4、支持子程序嵌套和递归。可将以下信息全部压入栈:返回地址、条件码、关键寄存器内容、必要的全局
或局部参数。为子程序开辟局部变量中间结果工作区。
4、比较寻址方式在指令中的两种指明方式。
操作码中的某位。缺点:不灵活。优点:指令总长短。
设寻址方式字段。缺点:指令总长长。优点:寻址灵活。
5、“机构型”和“策略型”的含义?
机构型功能指基本的通用的功能;策略型功能指不稳定的可能会改变的功能。
6、数据描述符和向量数据表示对向量数据结构所提供的支持有什么不同?
描述方法比变址方法简便,但不能解决向量数组高速运算问题;向量处理机能快速形成元素地址,能把元素成块预取到CPU ,用一条指令同时对整个向量数组高速处理。
7、按CISC 方向改进指令系统的思路具体办法?
思路可从面向目标程序、高级语言、操作系统三个方面考虑。
面向目标程序可采用的办法:1、对高频指令增强功能加快速度,低频指令合并和取消;2、复合指令代替子程序或宏。
8、haffman 方法及优缺点?
构造方法:构造haffman 树、每个节点用01表示、从根开始01编码
优点:平均码长最短,冗余少。缺点:种类多,不易译码。
9、haffman 压缩概念的基本思想?
概率高的事件用短位数表示,低的用长位数表示。
10、以浮点数数据表示说明数的可表示精度、运算中的精度损失,尾数基值取小对哪个有利哪个不利?
数的可表示精度是数轴上数的离散程度,两个数间差越小,精度越高;运算中的精度损失指运算中尾数超长造成的损失。
尾数基值取小则可表示范围变小,个数减少,分布变密,精度提高,速度降低,对前者有利,对后者不利。
11、OS 中哪些适合硬化或固化?哪些不适合?
高频使用的机构型功能适合,策略型功能不适合。
12、什么是程序的动态再定位?
程序在主存中的实际位置可以动态移动的定位技术。可以使用基址寄存器或映象表硬件。
13、缩短地址码长度的方法
基址、变址、相对寻址、分段、寄存器寻址、寄存器间接寻址等。
14、变址和基址各适用于何种场合?设计一种只用6位地址码就可以指向一大地址空间中任意64个地址之一的寻址机构。
变址适合标量计算机中,基址主要对逻辑与物理空间进行变换,支持动态再定位。
用6位地址码表示64个地址中的任意一个,可以用隐含寻址或PC 自相对寻址形成物理地址。
15、设计RISC 机器的一般原则及可采用的基本技术?
原则:精简指令条数、格式,让指令等长,一个周期内完成,增加通用寄存器,一般指令不
可访存只能对寄存器操作,硬件实现为主,少量微程序解释,提高编译程序质量。
技术:按以上原则优化、实现指令,设置寄存器,指令采用重叠流水方式解释,采用延迟转移,提高便宜程序质量。
16、比较CISC 和RISC ,今后的发展是什么?
CISC 问题:系统庞大导致成本高可靠性低,80%指令利用率低,性价比低。
RISC 优点:简化指令系统,适合VLSI 实现,解决了CISC 的上述问题。
缺点:加重汇编语言负担,目标程序开销大,对浮点运算虚拟存储支持不强,对编译程序要求高。
发展趋势:二者互相结合,取长补短。
17、比较四种浮点数尾数下溢处理方法
截断法:将超出机器字长的部分截去,整数最大误差1,分数最大误差2^(-m),统计平均误差
舍入法:设一附加位,整数最大误差0.5,分数最大误差2^(-m-1),统计平均误差略>0,不能调节统计平均误差,实现简单增硬件少最大误差小,但速度慢需处理时间平均误差无法调节。
恒置1法:最低位恒置1,整数最大误差1,分数最大误差2^(-m),), 统计平均误差略>0,不能调节统计平均误差,实现最简单不增硬件不需处理时间,但最大误差平均误差大且无法调节。
查表舍入法:用2^k个字的ROM 或PLA 存放下溢处理表,根据查表内容处理下溢。整数、分数、统计平均误差均趋于0,能调节统计平均误差,处理速度快但需增加硬件。
1、以IBM370为例说明为什么把中断分类以及分成几类。
大型多用途机器中断源多,每个中断源单独形成入口将导致硬件实现难,代价大,因此可归类,每类给中断服务程序入口由软件转入相应处理部分。IBM370中断分为6类:机器校验,访管,程序性,外部,I/O,重新启动。
2、专用和非专用线各自的优缺点
专用线:只连接一对物理部件的总线。优点:不用争总线,控制简单,系统可靠。缺点:总线数多且长,成本高,利用率低,不易扩展。
非专用线:可被多种功能与部件共享,但同一时刻只能被一个部件使用。优点:集成度高,造价低,可扩展能力强,总线利用率高,易标准化。缺点:流量小,争用总线,部件效率低,可能成为瓶颈,可靠性差。
3、减少总线线数的方法
线的组合:减少按功能和传递方向所需的线数。
编码:对少数几根功能线进行编码取代多根单功能线。
并/串-串/并:在总线两端设置转换器,经分拆移位后在目的端形成完整的字。
4、比较几种数据宽度
单字:适合低速设备,不用指明传送信息单位,缺点是速度慢总线利用率低;
定长块:高速设备,充分利用总线宽度不用指明传送信息单位,但不灵活;
可变长块:优先级速度都高的设备,灵活需充分利用总线带宽,但需指定传送信号块大小。 单字加定长块:优先级高速度低的设备,短数据可用单字传送减少带宽浪费,信息块太小时成为单字方式总线利用率低。
单字加可变长块:普遍使用,灵活有效,但复杂开销大。
5、有通道情况下的I/O过程
a 目态程序中可安排I/O广义指令
b 运行到广义指令后,产生访管中断
cCPU 响应中断后进入管态
d 管理程序根据广义指令编写通道程序,进入通道选择设备期
e 选择通道和子通道,取出指令,选择控制器和设备,发启动命令,结束通道选择设备期 f 进入通道数据传送期,完成数据传送
g 向CPU 发I/O请求,第二次转管态,调出相应管理程序,之后CPU 返回目态。
6、比较通道的三种类型
字节多路:单字节,适于大量低速设备,字节交叉,多次选择设备,分时共享,满负荷时对通道要求的实际流量应是所连各设备的流量之和。
数组多路:定长块,适于大量高速设备,成组交叉,多次选择设备,分时共享,满负荷时对通道要求的实际流量应是所连各设备的流量最大的那个。
选择:不定长块,高优先级高速设备,独占通道,一次选择设备,独占,满负荷时对通道要求的实际流量应是所连各设备的流量最大的那个。
7、为什么中断优先级从高到低一般为:机器校验、程序性和管理程序调用、外部、I/O、重新启动?
机器校验若不及时处理,系统将无法正常工作。
程序中断若低于外部和I/O中断可能导致混乱。只有处理完机器故障后,才能进入访管中断。 重新启动一般时间并不紧迫,所以放在最后。
8、集中式串行链接的过程,优缺点,硬件故障时通讯的可靠性。
a 经公共总线向总线控制器申请
b 总线不忙时,总线控制器响应请求,送出总线可用。
c 总线可用信号在部件间串行通过,直至某个部件发生总线请求。
d 该部件获得总线使用权
e 数据传送,维持总线忙
f 传送完成,去除总线忙
g 总线请求再次建立时,重复新的分配过程。
优点:简单,线数少,可扩充性好,可靠性高。
缺点:对总线可用线及电路敏感,不灵活,速度慢。
9、集中式定时查询的过程,优缺点,硬件故障时通讯的可靠性。
a 每个部件发总线请求
b 总线不忙时,定时查询谁发的请求
c 查询到后,查询停止,该部件获得总线使用权
d 数据传送,维持总线忙
e 传送完成,去除总线忙
f 总线请求再次建立时,重复新的分配过程。
优点:灵活,可靠性高
缺点:线数多,扩展性差,控制复杂,总线分配受限计数信号。
10、集中式独立请求的优缺点,硬件故障时通讯的可靠性。
a 每个部件有总线请求和总线准许
b 总线未分配时,总线分配器根据某种算法仲裁哪个申请部件使用总线。
c 数据传送
d 传送完毕后除去总线已分配和总线准许。
优点:速度快,灵活,方便隔离失效部件
缺点:线数多,复杂。
11、在现代计算机系统中,中断系统的软硬件功能是怎样分配的,为什么这样分配? 中断响应要求快,一般用硬件实现。
中断的处理过程一般用软件,也可用硬件支持。
中断响应过程中现场的保存和恢复用硬件实现,以保证响应速度。
另一部分现场用软件实现,提高灵活性。
第四章
1、在分体交叉存储器中为什么实际频宽不随M 增大而线性增大?
M 大-数据总线长-负载重-增加门级数-增加延迟;
顺序取指效率可提高M 倍,但出现转移效率就会下降。
2、段式存储管理的地址转换过程。
程序号、段号、段内偏移量
1) 由程序号找到相应的段表基址寄存器,查到段表始址和段表长度。
2) 检查是否越界,正常转3
3) 由段表始址和段号找到装入位等相应表项
4) 装入位为1转5,否则产生缺页中断
5) 主存地址+段内偏移=物理地址
3、段页式存储管理的地址转换过程。
用户标志、段号、页号、页内偏移
1) 用户标志-段基址寄存器
2) 检查是否越界
3) 找到段表中表项
4) 检查装入位,段长
5) 找到页表中表项
6) 检查装入位
7) 实页号+页内偏移=有效地址
4、段式存储管理优缺点
优点:并行编程,缩短时间;相对独立,易于维护;实现虚拟存储;便于共享和分段保护。 缺点:主存利用率低;降低了访寸速度;空闲区管理复杂;查表速度慢。
5、分页方式的优缺点
优点:表项短,减少访表时间;零头少;速度快。
缺点:强制分页,不利于存储保护和扩充;有效地址生成慢。
6、段页式管理的优缺点
优点:具有段式、页式优点
缺点:有效地址形成慢。
7、为什么要发展存储体系
单一工艺的存储器件不能同时满足容量、速度和价格的要求;并行主存系统效果有限。所以必须使用由多种不同工艺存储器组成的存储系统,从系统结构上公斤,发展存储体系。
8、页面失效频率算法的思想
某个程序的页面失效率过高时就增加它的主存页数,过少时就减少它的主存页数,以提高总的主存利用率。
9、主存页面表实现的变形LRU 的过程
最近最久未使用算法
1) 建立主存页面表
2) 用使用位表示是否被访问过,置初值为0
3) 访问实页,则其使用位置1
4) 调入页进入占用位为0的实页,将占用位置1
5) 所有占用位为1,发生缺页时,替换使用位为0的页
6) 使用位要全1时,强制全置0。
10、页式管理中的主存页面表和页表是一张表吗?
页表是一个程序一张;主存页面表是整个主存一张。
11、比较写回法写直达法。
写回法:信息只写入CACHE ,仅需要替换时才送回主存。节省开销,但增加CACHE 复杂性。
写直达法:写入CACHE 时也写入主存。开销小,简单,但浪费时间。
12、CPU-Cache-主存层次,CPU-主存-辅存层次异同。
相同点:都需要地址映象表和地址变换机构。
不同点:
1) 前者为缩小CPU 主存速度差,后者为扩大主存容量;
2) 前者硬件后者软影结合实现地址变换;
3) 前者用页表后者用目录表实现实现地址映象表;
4) 前者CPU 与辅存之间无通路,后者缺页时CPU 采用换道办法。
13、散列法实现快表的地址变换过程
1)A=H(Nv)
2) 查找Nv 时,经同样函数变成A ,再找到Nv 内容。
3) 地址变换时先查快表再查慢表
14、有Cache 时,给出一个主存地址访存过程
1) 将主存与Cache 分成大小相同的块
2) 判断要访问的主存地址块号是否在Cache 中
3) 若在,变换为Cache 号,访问Cache
4) 若不在,将该信息由主存调入Cache 和CPU
5) 若Cache 已满,则替换Cache 信息,修改相应表格。
15、比较Cache-主存层次的几种地址变换方式
全相联映象和变换。过程:主存分为块号和块内地址;块号同目录表比较;相同则Cache 块号和块内地址形成Cache 地址;不同则缺块,调块。目录表长:Cache ;宽:主存块号+Cache块号。优点:块冲突低,空间利用率最高;缺点:映象表长,查表速度慢。
直接映象及变换。过程:区号块号块内地址;主存地址中截取Cache 地址;根据块号读出目录表中区号与主存地址区号比较;相等则命中否则访主存。目录表长:Cache ;宽:主存地址位-Cache 地址位。目录表小,成本低速度快,但冲突概率大Cache 利用率低。
组相映象及变换。区号组号块号内地址;用组号选组;对该组区号+块号全相联比较;找不到失败找到则Cache 块号组号块内地址形成Cache 地址。目录表长2^ncb,Cache表大小(区号+2块号) 位(区号+块号) 位参与比较。集中全相联和直接映象的优点弥补它们的缺点,但块冲突>全相联,Cache 利用率直接方式。
16、什么是堆栈型的替换算法
满足n
n>=Lt时,Bt(n)=Bt(n+1)
n :分配给程序的实页数
Bt(n):t 时刻在实页中的页面集合
Lt :t 时刻处理过的不同的虚页数
17、主存实际频宽与模数m 的关系是什么?原因?指令流与数据流随机时,主存实际频宽与模数m 有什么关系?
主存实际频宽随模数增大而增大,但增量会减小。这是因为程序会有转移,数据分布有随机性。完全随机时,大致成平方根关系增大。
18、CPU 写Cache 时,会发生Cache 与主存的对应副本内容不一致,如何解决?需增加什么开销?
写回法:仅Cache 替换时才写回主存。每个Cache 块需增加一个修改位的资源开销。 写直达法:同时写入Cache 和主存,需增加时间开销。
19、二级虚拟储存层次的等效访问时间与主辅存访问时间有什么关系?提高存储层次的访问
速度,可采取的措施有哪些?
主辅存的访问时间为T1和T2,等效访问时间TA=HT1+(1-H)T2,H为主存命中率。可采取的措施
TA>>主存访问周期时,可用改进替换算法、增大主存容量等办法来提高H ;
H 很高时,可降低T1;
加快地址映象和变换,如采用快慢表,增大快表命中率等。
20、解释页面失效、页面争用,什么时候同时发生,什么时候不同时发生?
虚页不在主存中,会发生页面失效。页面调入主存时,其位置被其它虚页占用,会发生页面争用。分配给程序的内存被全部占用后,会同时发生。反之不同时发生
第五章
1、试举例说明什么是“先读后写”,“写-写”,“先写后读”相关?
设有指令h,i,j,k,l,m,n 依次流入流水线,若i 要读数的单元正是k 写数的单元,正常顺序是i 先读,k 再写。但由于异步流动下,k 可能先于指令i 被解释,从而i 读到的是不正确数据(正常数据应该是k 写之前的) ,这种相关称为“先读后写”相关。若i ,k 向一单元写数据,正常情况下最后单元中应保存k 写的数据,但由于异步流动,k 可能先于i 写数据,使该单元最后结果不正确,这种相关称“写-写”相关。类似可知“先写后读”相关。
2、解决通用寄存器数相关有几种方法?试作简单比较。
方法1:
推后“分析k+1”读。可将“分析k+1”推到“执行k”结束时,也可以使它们部分重叠,只要“分析k+1”能取得正确操作数即可。缺点:它们是以牺牲速度为代价。优点:不增加设备。 方法2:
设置“相关专用通路办法”。在运算器输出到输入之间增设“相关专用通路”,保证在“执行k+1”之前输入中已获得正确信息。优点:重叠速度不下降。缺点:增加设备为代价。
3、为实现指令重叠解释可能采取哪些办法?简单分析其特点?
方法1:
让操作数和指令分别存放在两个独立编址且可同时访问的存储器中。优点:有利于实现指令的保护。缺点:主存总线控制复杂,软件设计麻烦。
方法2:
指令和操作数混存在多体交叉主存结构中,只要指令和操作数不在一个分体时就在一个主存周期取得。优点:实现上简单,开销少。缺点:当指令和操作数在同一体时无法重叠。 方法3:
增设FIFO 工作的指令缓冲寄存器。当主存空闲时预取下几条指令到指缓。优点:微操作可分成分析指令和执行指令两部分。缺点:数据相关问题。
4、试比较几种指令级高度并行的超级处理机
超标量处理机:配置多套功能部件辅助电路,靠编译程序优化指令顺序,使流水吞吐率提
高。优点:硬件不调整指令顺序、容易实现、适合矩阵计算。缺点:开销大。
超长指令字处理机:编译程序将选择可并行指令放入一条超长指令中,运行时指令中每个操作段控制一功能部件。优点:硬件结构和指令系统简单、无增加硬件开销、指令级并行性高。缺点:指令结构与一般计算机不兼容、指令结构不灵活浪费指令存储空间、不适于一般领域。
超流水线处理机:利用时间并发性,利用较短时钟周期提高流水线速度。优点:开销小。缺点:必须有高速时钟机。
5、流水线按级别分成几类?线性流水线与非线性流水线有什么区别?动态流水线和静态流水线有什么区别?
流水线按级别分部件级、处理机级和系统级三级。线性流水线段间无反馈或超过的通路,非线性流水线则有反馈回路或前越通路。静态和动态流水都是多功能的流水。其中,动态流水线按一种功能流水未完成之前,可重组开始另一种功能的流水。静态流水线必须等流水线排空之后才可进行功能切换。
6、在“一次重叠”的机器中,会出现哪些相关?如何处理?
转移指令与后续指令相关:减少使用转移指令,需要使用时可采用延迟转移技术。
指令相关:不允许程序在执行过程中修改指令,需要修改指令时可用类似于IBM370的执行指令,变指令相关为操作数相关,统一按操作相关去处理。
主存空间数相关:在存储控制器中,写数申请优先于读数申请被响应变址值二次相关,设置变址值相关专用通路。
通用寄存器组的变址值一次相关:设置变址值相关专用通路,并推后后续指令的分析。
7、为处理流水机器的全局性相关,可以加快或提前形成转移指令所需的条件码,那么可从哪两方面考虑?举例说明。
一是加快单条指令内部条件码的形成。如有的指令,象乘、除指令只要取出操作数,利用其数的符号位是同号,还是异号,就可以判定结果的正负。而是在一段程序内提前形成条件码,例如,在循环程序中,将控制循环变量改值的指令提前到循环体开始处。在硬件上设置专用的条件码寄存器,以便在判断是否循环时,已提前产生了条件码。
8、解释重叠方式中的“一次重叠”的含义。
将指令的解释分为“分析”和“执行”两个阶段,任何时刻都只是“执行k”与“分析k+1”在时间上重叠,也就是让指令分析部件与指令执行部件同时处理相邻的两条指令。
9、什么是流水线的速度瓶颈?消除流水线速度瓶颈的方法有哪两种,举例示意说明。 流水线中经过时间最长的功能段就是流水线中的速度瓶颈。清除流水线的速度瓶颈的方法,一是将瓶颈过程再细分。例如,流水线瓶颈段为2Δt,其它各段均为Δt,则可将该瓶颈段再细分成两个子段,各子段经过时间均为Δt;二是将瓶颈子过程多套并联,如上例,将瓶颈重复设置两个,任务错开一个Δt时间分配给这两个段。
10、流水机器的中断处理有哪两种方法,各有什么优缺点?
流水机器的中断处理有不精确断点法和精确断点法两种。
不精确断点法好处是控制处理简单,缺点是程序排错不利。精确断点法,中断现场准确对应于发出中断的指令,有利于程序的排错,但不利之处是需要大量后援寄存器。
11、在流水机器中,全局性相关指的是什么?处理全局性相关的方法有哪些?简要说明。 全局性相关是转移指令与其后续指令之间的相关。
处理方法有:
猜测法,猜选其中一个分支继续流入,待条件码形成后再决定是继续执行,还是作废,按另一分支重新流入。
提前形成转移所需的条件,包括指令内或程序段内条件码的提前生成。
加快短循环程序的处理,判断如属于短循环,将循环体内各指令一次取入指令缓冲器中,停止预取指令;猜选分支恒选循环分支。
12、流水处理的主要技术途径是什么?在CPU 中可以有哪两类流水?在存储系统或存储体系中举出两个应用流水的例子。
流水处理的主要技术途径是时间重叠和功能部件专用化。CPU 内部可以有指令流水线和运算操作流水线。在存储体系中CACHE 存储器的查地址映象表和访物理CACHE 可以流水。存储器系统中,主存模m 多体交叉对各分体的交叉访问也可以看成是一种流水。
第六章
1、试分析阵列处理机特点。
(1)阵列处理机提高速度是利用资源重复,利用并行性中的同时性;
(2)处理单元同等地担负起各种运算,其设备利用率可能不那么高;
(3)速度提高在硬件价格大幅度下降情况下,潜力巨大;
(4)互连网络对系统性能影响显著;
(5)互连网络使阵列处理机比固定结构的单功能流水线灵活;
(6)阵列处理机结构和所采用并行算法紧密联系;
(7)阵列处理机还必须提高标量处理速度。
总之,阵列处理机实质上是专门对付数组运算的处理单元阵列组成的处理机、专门从事处理单元阵列控制及标量处理的处理机和专门从事输入输出及操作系统管理的处理机组成的一个异构型多处理机系统。
2、试比较阵列机的两种基本形式
(1)分布式存储器阵列机。a 、各处理单元PE 有局部存储器,被分布数据只能被本处理单元直接访问。b 、在控制部件CU 内有主存储器。运行时所有指令都在CU 中,只把适合并行处理的“向量类”指令播给各PE ,并控制各PE 并行执行。c 、各PE 可通过互连网ICN 交换数据。d 、PE 通过CU 连到管理处理机SC 上,用于管理系统资源。
(2)集中式共享存储器阵列机。a 、K 个存储体集中组成,经互连网络为全部N 个处理单元共享。其中K 等于数据处理单元数。b 、互连网用于处理单元与存储分体之间进行转接构成数据通路。
3、试比较多级互连的几种网络
ATRAN----拓扑结构:第I 级交换单元处于交换方式时,实现Cubei ;控制方式:级控制分
级控制;交换单元:二功能交换单元。
间接二进制N 方体----拓扑结构:第I 级交换单元处于交换方式时,实现Cubei ;控制方式:单元控制;交换单元:二功能交换单元。
多级混洗omega----拓扑结构:每一级有一个全混拓扑和一列四功能交换单元;控制方式:单元控制;交换单元:四功能交换单元。
多级PM2I----拓扑结构:每级按PM2I 连接;控制方式:级控制或单元控制;交换单元:二功能交换单元。
全排列Benes----拓扑结构:三维立方体多级网络与它的逆网络连在一起,省去中间重复一级;控制方式:单元控制;交换单元:二功能交换单元。
4、试说明间接二进制n 方体网络是阻塞式网络
N个端要实现任意排列,应有N !种。
而单元控制的N=lnN/ln2级间接二进制方体网络中,每级有N/2个开关,N 级互连网交换开关总数为(NlnN/ln2)/2。
要实现入、出端的一一映射,每个开关只能取直接或交换两种功能。
所以开关状态总共有2^[(NlnN/ln2)/2],即N^(N/2)种。
当N>2时,N^(N/2)
所以它无法表示所有N !排列,所以当多个入出端同时连接时可能发生冲突,即间接二进制N 方体网络是阻塞式网络。
5、试比较互连网动态拓扑结构的两种形式
动态单极网络指网络只有有限几个连接,必须经循环多次通过,才能实现任意两个处理单元之间的信息传送。节省设备,但通过时间长,对网络控制要求高。
动态多极网络指由多个动态单极网络串联组成的网络。通过时间短,灵活性好,可利用不同单极互连网络组合成有不同特征和连接模式的多级互连网络。缺点是:增加设备和成本。
6、试比较单级互连的几种函数
Cube
相连的2个处理单元其二进制编号只有一位不同。Cubei, 其第i 位取反。有logN(以2为底,下同) 种函数,任意两点最大距离是logN, 最多使用logN 次函数可实现任意入出端连接,可逆。
PM2I
J号处理单元直接连接的结点是J±2^i(0≤i≤logN-1) 。PM2±i(j)=j±2^i(0≤i≤logN-1,0≤j≤N-1。有2logN-1种函数,任意两点最大距离是N/2,最多使用2次函数可实现任意端连接,可逆。 混洗
每个结点连到另一个二进制结点最低位是其最高位的结点。Shuffer(Pn-1...P1P0)=Pn-2...P1P0Pn-1。有2种函数,任意两点最大距离是2logN-1,最多使用2logN-1次函数可实现任意入出端的连接,不可逆。
7、单指令流多数据流的并行处理机在系统组成上应包含哪些部分和功能?
重复设置大量的处理单元用规整灵活的互连函数互连,组成处理单元阵列;
用专门的并行算法对数组、向量中的元素进行并行处理;
用一台高性能处理机来进行标量处理和控制互连网络的连接;
用一台管理处理机来运行系统程序和输入输出任务。
8、什么是全排列网络?实现全排列网络有哪两种方法?
可实现N 个入端的所有N !种排列的网络称全排列网络,即N 个端所有一到一的传送都不会发生传送路径使用冲突的互连网络。
实现全排列网络的出方法有:
在多级互连网络的输出端设置锁存器,使输出端的数据再一次通过多级互连网络;
将两个多级互连网络,即一个正网络和一个逆网络串接起来,合并掉中间的一级,组成2logN-1级的多级网络。
第七章
1、简述紧耦合和松耦合的多机系统结构。
各处理机之间通过互连网络共享主存的紧耦合多处理机。紧耦合系统由P 台处理机,m 个存储器模块,d 个I/O通道和3个互连网络构成。处理机-存储器网络实现处理机与各存储模块的连接。处理机中断信号网络实现多处理机之间的互连。处理机-I/O互连网络实现处理机与外设的连接。每个处理机可自带局部存储器,也可自带Cache 。存储器模块可采用流水工作方式。紧耦合系统多用于并行作业中的多任务,一般处理机是同构的。
各处理机间通过共享I/O子系统、通道或通信线路实现机间通信,不共享主存的是松耦合系统。松散耦合多处理机由P 个处理机,一个通道,一个仲裁开关和消息传送系统。每个处理机带有一个局部存储器和一组I/O设备。在仲裁开关的通道中有高速通信存储,用来缓冲传送的信息块。松散耦合多处理机较适合粗粒度的并行计算。
2、简述对树形结构进行变换的过程
首先利用交换律把相同的运算集中在一起。然后利用结合律把参加这些运算的操作数配对,尽可能并行运算,从而组成树高最小的子树。最后再把这些子树结合起来,用分配律进一步降低树高。
3、试比较3种类型的多处理机操作系统
主从型:管理程序只在一台处理机上运行。硬件结构简单,控制简单,但对主机可靠性要求高,灵活性差。为目前大多数多处理机操作系统采用,工作负荷固定,从处理机能力明显低于主处理机,或由功能差别大的多个处理机组成的异构型系统。
各自独立型:控制分散到多台处理机,共同完成对整个系统的控制工作。适合分布计算模式,对主机依赖性差,可靠性高;但实现复杂,共享表格访问冲突,处理机负荷平衡较困难。适用于松耦合处理机系统。
浮动型:管理程序在处理机间浮动。灵活性高,但发生访问表格冲突,设计较困难。适合紧耦合多处理机系统,特别是共享主存和I/O子系统的同构多处理机系统。
4、比较多处理机系统中数据相关的处理方式
并行 顺序串行 交换串行
“先读后写” 可以(有条件) 可以 不可以
“写-写” 可以(有条件) 可以 不可以
“先写后读” 不允许 可以 特殊情况可以
“先读后写”和“先写后读” 必须 不允许 不允许
无任何相关 可以 可以 可以
5、多处理机系统与并行处理机的主要差别是什么?多处理机系统主要解决的技术问题是什么?
有差别的原因是并行性等级不同,多处理机系统是任务级并行,并行处理机是操作级并行。具体讲:
1)结构灵活性不同。
2)程序并行性等级不同。软硬件支持不同。
3)并行任务派生的方式不同。并行处理机能否并行工作由指令决定;多处理机必须有专门指令指明程序段能否并行执行,派生的任务数是动态变化的。
4)进程同步。并行处理机工作同步是自然的,而多处理机必须采取同步措施。
5)资源分配和任务调度,多处理机比并行处理机任务调度复杂。
多处理机必须解决的技术问题:
1)硬件结构上多处理机、主存、I/O子系统之间应有高带宽、低价格、灵活无规则的互连,尽可能不发生信息传送的路径冲突。
2)从并行语言、并行算法、编译等上,最大限度地开发出程序的并行性,实现多处理机各级的全面并行。
3)大的任务如何细分成多个子任务、任务的粒度选择
4)从操作系统上解决好多处理机间、并行任务的分配、调度和资源分配;任务或进程间的同步死锁和竞争等问题的解决。
5)系统的重组及良好的编程环境
6、简述JOIN 语句和FORK 语句的基本功能。
FORK m的功能:
1)准备好新进程启动和执行的必须信息
2)将空闲处理机分配给派生的新进程,若没有,则排队等待
3)继续在原处理机上执行FORK m语句的原进程
JOIN n的功能:
1)JOIN语句将计数器初始化为0;
2)执行一次JOIN 语句,计数器+1,并与n 比较
3)若相等,则允许进程通过JOIN 语句,计数器清0,进程继续执行
4)若不相等,则执行JOIN 语句的进程结束,释放处理机
7、试比较机间互连的几种形式。
总线形式:处理机与外部存储器模块通过总线相连。结构简单、成本低、扩展性好;但总线失效敏感,存在总线争用。适合处理机较少、系统信息流量少、机数可扩充情况。
环形互连:各处理机点点相加成环。结构简单、成本低、不争用总线;但信息传输有延迟。
适合处理机较少、使用高宽带的光纤通信、系统流量高、机数可扩充的情况。
交叉开关:用纵横开关阵列将存储器模块、I/O通道相连。不争用开关;但开关阵列复杂,设备量较大。适合处理机数较多(但不超过16) 、系统流量大、处理机数可扩充的情况。 多端口存储器:将交叉开关移到存储器接口中。不争用总线,但存储器接口复杂,较难控制。适合处理机数少、不能扩充(一般是2台) ,系统流量高的情况。
开关枢纽结构:把交叉开关设置在各处理机或接口内部。所有开关枢纽数量少,可用较短路径与处理机连接;但开关枢纽较复杂。适合处理机数多、可扩充、分布结构情况。
8、多处理机在结构与并行性方面与阵列处理机有什么不同?
结构方面:阵列处理机的互连较规整,有一定专用性,互连的处理单元数量大;多处理机要采用更灵活多变的结构,实现复杂的互连模式,互连的处理机数量少。
并行性方面:阵列处理机是操作级并行,是并行性的同时性;多处理机是作业、程序、任务级的并行,同时包含指令内部操作间的并行,是并行性的并发性。
9、多处理机中的并行性表现在哪些方面?开发多处理机的并行性有哪些途径?
多处理机主要实现作业之间、程序段之间、任务之间的并行,也可包含有指令级、指令内部各微操作之间的并行。
多处理机的并行性可利用并行算法、并行程序设计语言、并行编译、并行操作系统以及指令硬件等多种途径来开发和实现。
第八章
1、什么脉动阵列机,其结构特点是什么?
它是具有脉动阵列结构的处理机。脉动阵列结构由一些处理单元加上若干锁存器构成。阵列内所有处理单元的数据锁存器受同一时钟控制,运算时数据在阵列结构的各个处理单元之间沿着各自的方向同步前进。就象血管液流一样,称为脉动阵列机。
脉动阵列机的结构优点是:
(1)结构简单,规则,模块化强,可扩充性好;
(2)处理单元间数据通信距离短,规则,使数据流和控制流的设计,同步控制均简单规整;
(3)脉动阵列机中各处理单元同时运算,并行性极高,可通过流水获得很高的吞吐率;
(4)输入数据被多个处理单元重复使用,减轻阵列与外界I/O通信量,降低系统对主存和I/O系统频宽的要求。
脉动阵列机的缺点是:其构形与特定任务和算法密切相关,具有专用性,限制了应用范围。
2、什么是控制流工作方式?什么是数据流工作方式?对两者进行比较。
控制流工作方式是指计算机在程序计数器集中控制下,顺次执行指令。
数据流工作方式是只要一条或一组指令所要求的操作数全部准备就绪,就可立即激发相应的指令或指令组执行,执行的结果又可能激发等待该执行结果的一些指令。下面对两者进行比较。
控制流方式:通过访问共享存储单元让数据在指令间流动;指令执行顺序隐含在控制流中,受程序计数器控制;专门使用控制操作符来实现并行处理;有程序计数器;有数组。
数据流方式:没有共享存储数据的概念,是数据的显式流动(数据令牌) ;受数据相关性的
制约,基本上无序;不需要检查和定义程序中的并行性;无程序计数器;无数组。
3、试简述数据流机的特点
对提高并发处理效能非常有利。
(1)对强相关性的程序,数据流机的效能反而比传统控制流机效率还低;
(2)在数据流机中为建立、识别、处理数据令牌标记,需时间和空间开销;
(3)数据流机不保存数据组,对数组、递归等高级操作较难管理;
(4)数据流机中变量代表数值不代表存储单元,所以程序员无法控制存储分配;
(5)数据流机中互连网络设计困难,I/O系统也不完善;
(6)数据流机中没有程序计数器,使诊断和维护较难。
4、简述规约机的结构特点
规约机是需求驱动的数据流型机器,驱动的来源是表达式的规约,所以它必须针对函数程序设计语言的特点,支持函数式程序运行。结构特点如下:
(1)面向函数式语言,或以函数式语言为机器语言非V onNeuman 机器。要有函数定义存储器和表达式存储;操作和数据合并存储。
(2)具有大容量物理存储器并采用大虚存容量的虚拟存储器,满足规约对动态存储分配和所需存储空间大的需求。
(3)处理部分应当是一种有多处理机并行的结构形式,以发挥函数式程序并行处理的特长。
(4)采用适合于函数式程序运行的多处理机互连结构。
(5)使多处理机负荷平衡。
5、试简单比较串规约机和图规约机
串规约机是使用串规约方式工作的规约机。函数定义等的存储方式是串;不能共享子表达式;多次应用共享子表达的时间开销大;要求存储衔接;存储空间利用率低;可靠性高。 图规约机是使用图规约方式工作的规约机。函数定义等的存储方式是图;能共享子表达式;多次应用共享子表达的时间开销小;不要求存储衔接;存储空间利用率高;可靠性低,存在单点瓶颈。
6、试比较静态数据流机和动态数据流机
(1)静态数据流机的数据令牌无标号;动态数据流机的数据令牌有标号。
(2)静态数据流任意给定时刻当结点操作时每条弧上只能有一个数据令牌;动态数据流机中,任何一条弧上可出现多个不带目标号的数据令牌。
(3)静态数据流机中必须设控制令牌以满足要求;动态数据流机中不必设控制令牌,因为令牌有识别时间、先后关系的标号;
(4)静态数据流机不支持递归的并发激活,只支持一般循环;动态数据流支持递归的并发激活。
(5)静态数据流机不需硬件完成标记的匹配;动态数据流机需要硬件将标记附加在数据令牌上,并完成对标记的匹配工作。
7、什么是MPP ?什么是机群系统?将机群系统与传统并行系统做比较。
MPP是大规模并行处理机,指用数百万个高性能,低成本的RISC 微处理器通过互连网络
互连,组成的SIMD 或MIMD 系统。
机群系统是将多个高性能工作站或高档微型计算机使用高速通信网络加以互连组成系统。 机群系统与传统并行处理系统相比有以下几个优点:
(1)高的性能价格比。因为工作站或微机都是批量生产,价格低;
(2)系统开发周期短,因为主机、网络、操作系统都不需要新设计;
(3)系统可扩展性好。采用通用网络,易于扩展;
(4)系统资源利用率高,工作站的不能性能相互补充,结构灵活;
(5)用户投资风险小。每个出结点既可以进行大规模并行处理也可做单机使用;
(6)用户编程方便。不需修改编程环境。
8、简单比较数据驱动方式和需求驱动方式。
相同点:都属于数据流模型
不同点:
(1)数据驱动的操作是按输入数据的可用性决定次序的。需求驱动操作是按数据需求所决定的次序进行的。
(2)数据驱动是提前求值策略,只要所要求的输入数据全部就绪,即可驱动操作进行。需求驱动是滞后求值策略。只有当某一函数需用到一自变量时,才驱动对该自变量的求值。
(3)需求驱动比数据驱动可减少许多不必要的求值,系统效率高。
(4)需求驱动比数据驱动更适合于面向函数程序设计的计算机。
9、什么是活动膜片?
活动膜片是数据流程序图的一种表示方法,它接近于机器语言。数据流程序图可看成是一组活动膜片的集合。每个活动膜片由4个域组成:操作码域、两个操作数域、目的域。实际上活动膜片就是结点在数据流机器内部具体实现时的存储器映象。