用单级网络互连.doc

1。共16个PE，用单级网络互连，求与PE10相连的PE号 （1）Cube3 （2）PM2+2 （3）Cube2(Shuffle) （4）B() B是蝶形变换,是位序颠倒置换. 2。2m x 2m的矩阵A(aij)，行主序存在主存中，用何种单级网络经过多少 步可以实现转置。 并证明之. 3。流水线，启动循环（1，3，1，5） ? （1）求周期、平均启动距离 （2）求启动距离集 （3）插入非计算延迟单元后，启动循环（1，1，4），求禁止集具体满足的 条件 4。unrolling展开,并求调整后的循环体的执行周期. 指令生成结果 指令利用结果 延迟周期 FPALU 另一个FPALU 3 FPALU store double 2 load double FPALU 1 load double store double 0 Bi=Ai*a+Bi,a为常数,存放在f0中. foo: ld f2,0(r1) ;load Ai into f2 multd f2,f0,f2 ;Ai*a ld f4,0(r2) ;load Bi into f4 addd f4,f2,f4 ;Ai*a+Bi sd 0(r2),f4 ;store Ai*a+Bi to Bi addi r1,r1,#8 ; addi r2,r2,#8 ; sgti r3,r1,done ;to see if done? beqz r3,foo ;go to foo if not done 将上述循环展开3次(4 copy),并进行调整,写出调整后的指令, 并求调整后的循环体的执行周期. X处理机的频率为25Mhz 指令 百分比 cpi i1 43% 1 i2 20% 2 i3 10% 2 i4 20% 2 i5 2% 2 i6 2% 2 i7 3% 2 5,6,7题均用到上述信息. 5.指令设计 采用2-4编码扩展，指令有8bits和16bits两种字长，均为双操作数指令， 8bits的为寄存器-寄存器寻址，16bits的为寄存器-变址（偏移量范围-128127） 寻址，要求编码，写出可以有多少可寻址的通用寄存器，多少变址寄存器。并且 要给出各种指令具体的位的分配. 并求操作码的平均长度. 6。CPI, Sn等等的计算 优化后,i1指令减少了50%,但主频变为22Mhz. 1)求改进前后的MIPS. 2)求加速比. 3)CPI和计算机速度的关系. 4)MIPS是衡量计算机性能的准确标准吗?至少阐明两个理由. 7。流水线的Tk计算，k有什么对性能的影响，超标量的T(m,1)计算 X处理机采用5段流水线,主频变为22MHz.执行100条指令. 1)求加速比. 2)流水线段数和其性能的关系,说明理由. 3)若上述流水线采用超标量T(4,1),重做1). 8。4x4矩阵的Tompson排序 一、填空 流水线加速比计算 指令格式编码问题 用多少次混洗和交换可以实现一个PE向互连单级网络中所有16个PE的发送 给出调度后的启动循环(1,1,4)求周期和禁止集 .1m m 二、分支预测（给BTB命中率，预测准确率，以及失效损失周期，求平均CPI) 三、给一段汇编程序，要求按ScoreBoard算法填Instruction Status表 四、给一段汇编程序和各类指令的延迟周期，要求以最少的unrolling次数使DLX流水线 执行起来无Stall 五、RISC机上给出各类指令的CPI，比较一下使用Cache和不使用Cache时的系统性能 六、给出DLX上的一段循环指令，要求填写时序表（相当于画时序图）并计算整个循环所需的时钟周期数00B 1.设计浮点数，尾数用原码表示，阶码用移码表示，要求精度 103000。 (1)给出浮点数格式 (2)写出精度、最大正数、最大负数 (3)如果该浮点数不需要设置警戒位，那么它采用何种舍入方式？试说明之，给出 正数范围内的误差范围与积累误差大小 2. 一个cache系统，T1=10ns,T2=50ns,已知cache内的访问重复次数平均为5 (1)已知效率为0.5，求系统的命中率与等效访问时间 (2)效率提高到0.94,求系统的命中率与等效访问时间 (3)如果要把效率从0.5提高到0.94,需要把cache内每块的字节从1个增加到几个？ 3.已知一页式存储管理中,有用户128,每位用户最大页数8192,每页4kB,主存16MB (1)给出虚地址的格式,位数,实地址格式,位数 (2)快表容量64个存储字,用地址散列,要几个输入,几个输出 (3)快表存储字的格式,位数 (4)快表采用相等比较,相等比较电路有多少位 4.中断屏蔽向量.(与第四章作业中的4.4很相似)给出中断屏蔽位矩阵，求 (1)D1,D2,D3,D4同时请求时各中断的响应时间与中断结束时间 (2)D3,D4在0时刻请求，10us后D1,D2请求，求各中断响应时间与结束时间 （中断处理至开中断1us，执行子过程10us） 5.静态转移预测 给出一段程序 (1)采用静态预测技术，每次预测转移不成功，化时空图，求时间、吞吐率、加速 比、译码器效率，执行部件效率 (2)采用静态预测技术，每次预测转移成功，化时空图，求时间、吞吐率、加速 比、译码器效率，执行部件效率 (3)采用指令取消技术，写出调整后的指令，画时空图，求总时间 6.超标量处理机，能同时发射两条指令，四级流水线：取指令、译码、执行、写结 果，其中执行阶段load,store,dec,要一个周期，add/sub要2个周期,mul要3个周期 指令串如下 (1)写出程序中数据相关现象 (2)顺序发射，顺序结束，读寄存器在译码阶段，写寄存器在写结果阶段，画时空图 (3)顺序发射，乱序结束，读寄存器在译码阶段，写寄存器在写结果阶段，画时空图 给出各指令结束时间 (4)顺序发射，乱序结束，流水线添加运算结果到输入的专用通路，画时空图，给出 各指令结束时间 7.写出网络函数值：E(x),S(x),B(x),PM+3(x),混洗交换网的网络直径_ 节点5到节点7的最短要几步？（E0与S各算一步）写出经过的节点。移数函数构成 的移数网的网络直径是_，与节点2距离最远的节点号是_ 8.计算(0,7)Xi+a，Xi为向量，a为标量，给出加法、乘法、读内存的时间 (1)用向量计算机计算,给出最短的方案与最短时间 (2)用SIMD计算机,环网结构,a在CU里,给出CU广播到PU的时间,求最短时间与方案 (3)用MIMD计算机,立方体结构,给出节点通信时间,求最短时间与方案 我已经不敢回忆题目了，大家凑一凑吧。 一。risc机器，主频500MHz,cache命中率99%,Tcache=2ns,Tmem=20ns,程序中有20%的load/store指令 机器性能的主要瓶颈就在访问存储器 1）理想情况下CPI 2)实际情况下CPI,MIPS 3)如果机器主频变为1GHz,求实际情况下的CPI,MIPS tmd,第一题就搞得人巨不爽。 二. 给出一系列页面流（介于p1-p6)，cache中可容纳4个页面,刚开始已经将p1,p2,p3,p4load 到了cache中，问 1）lRU,OPT的命中和替换表， 2）命中率。 3）如果要使cach失效率D2D3D4D5 各中断源屏蔽位的设置为： D1 D2 D3 D4 D5 D1 D2 D3 D4 D5 现在，有D4 D5同时来中断，并且在D5还没有处理完的时候来D1 D2 D3， 画出中断请求和服务的图。 5. Unrolling，对于一下的程序，计算yi=a*xi+yi 至少展开几次，可以没有stall LOOP: LD F0, 0(R1) MULT F0, F2 / a*xi LD F4, 0(R2) ADD F4, F0, F4/y=a*xi+yi ST F4, 0(R1) SUB R1, #8 SUB R2, #8 BEQ LOOP 其中： 指令结果来源 指令结果使用 延迟 浮点运算器 浮点运算器 3 浮点运算器 Store 2 整数运算器 分支 1 分支 1 Load 浮点运算器 1 整数运算器 0 6.几分牌，根据几分牌算法，填写各个指令状态对应的时钟周期， 有两个浮点乘法部件，一个浮点加法部件，一个浮点除法部件， 一个整数运算部件。 提示：WW冲突，后者可以在前者写周期发射 WR冲突，后者可以在前者写周期读数 资源冲突，后者可以在前者写周期发射 LOAD, STORE属于整数部件 发射 读书 执行 写数 插入stall的理由 LD MULT LD ADD STORE SUB SUB BEQ 7.针对下面三种机器，问求解(x0+y0+z0)*(x1+y1+z1)*.*(x7+y7+z7)最少时间： （1）串行机器 （2）并行机器，双向环形连接 （3）动态多功能流水线， 加法流水线: S1 - S4 乘法流水线: S1 - S2 - S3 - S4 问这个流水线需要执行的最少时间，时空图，和S1的使用效率 第一大题(35分) 1.16*16矩阵，最少几个存储体 2.集群计算机属于? 3.算一个吞吐率，100条指令 4.两个部件的使用分别占40%，20%，部件1速度提高到8倍，总的提高到2倍， 问部件2提高几倍 5.蝶式互连函数，问机器9与哪个相连,互连函数shuffle(PM2+1) 6.给一个7段流水线，dt不一样，问最高频率，执行100条指令要多少时间 7.16位长的指令，操作数字长为6，双操作数指令x条，问单操作数指令可以有几条 8.3级存储系统，T1,T2,H1,H2,T已知，求T3 9.混洗互连的东东 10.非线性流水线的问题，给预约表，求禁止向量和冲突向量，然后告诉你可以最优化， 最小启动距离看一下是3，求最大吞吐率 11.向量链接的问题，4条指令 第二大题(13分) DLX指令中，出现load和store的概率是26和9。 1.存取变量访问内存占整个访问内存的比例？ 2.增加一种变址寻址方式。 将 addi r1, r1, r2 lw rd, 0(r1) 改为 lw rd, r1, r2 /原试卷上无此行，理解上可能有困难 假设原来指令中有10的指令可以用这种方式改为新的寻址指令。 问原来和现在的指令长度比。 3.求改为新的后的加速比。 第三大题(15分) 9 计算f=(Xi+Yi)，加法需要2个时钟周期，乘法需要4个时钟周期，求计算出f的最短时间 i=0 1.串行处理器，有1个加法单元，一个乘法单元，不能同时工作，求总的时钟周期(3分) 2.SIMD处理器，PE0-PE7，单向环，每个PE向相邻的PE转移需要1个时钟周期，Xi,Yi 存储在PEk中 k = i mod 8。求总时间。(4分) 3.一个SISD流水线，S4的输出可以直接到输入。一个乘法指令顺序执行S1 S2 S3 S4 一个加法指令执行S1 S4。每个1个周期。(8分) _ _ _ _ -|S1 |-| S2 |-| S3 |-| S4 |- -|_| |_| |_| |_|- |_| 求(1)最短运行时间(4分?) (2)画时空图(1分) (3)S4的利用率(3分?) 第四大题(12分) 有一种机器指令只有7种。操作码采用24扩展编码。指令长度有8位和16位两种。 操作数有寄存器寄存器类型和寄存器变址寻址寄存器两种类型。 各种指令出现的比例和CPI： 指令 比例 CPI I1 （8位） 43% 1 I2 （8位） 21% 2 I3 （8位） 12% 2 I4 （16位） 8% 2 I5 （16位） 6% 1 I6 （16位） 6% 2 I7 （16位） 4% 2 1.求MIPS。 2.评价指令码长度。 3.该指令系统最多能有多少可以编址的通用寄存器和可以编址的变址寄存器。 4.设计指令码格式，并给出各指令的操作码。 后面数字代表有几个空，欢迎补充 张药学出题 一、填空 1。 操作系统特点 1，2，3 2。单cpu系统与cpu并行的是1 3。操作系统为程序员提供1接口，为一般用户提供2接口。 4。作业有1，2控制方式 5。Unix下0进程作用1，2 二、名词解释 同步 互斥 进程 线程 虚存 目录与i结点 三、计算优先级 公式：P152 p-pri=p-cpu/2+p-nice 活动进程每秒p_cpu+60 等待进程美妙p_cpu/2 四个进程pa,pb,pc,pd，写出0-4秒的p_pri,p_cpu值。写出执行的进程。 四、简述ifree算法过程，以及其缺点 五、Unix系统回写数据时的异步法和延迟法的区别。 六、1。为什么系统区使用分区管理。 2。写出memall(base,size)算法框图。 一选择（14分） 1.Xwin是从_传送事件到_. 2.目录结构DOS采用_, UNIX采用_. 3.磁盘I/O调度算法比较 二判断（6分） 4.系统调用与高级函数调用区别 5. 6.NT和UNIX睡眠优先级问题 三填空（10分） 7._微内核_ (不是模块) 8.重定位的方法 3 9.文件别名的实现方法 2 10.死锁的条件 4 四问答 11.页面调度、工作集策略、负载.策略算法（15分） 12.Unix磁盘空闲块成组链接法（10分） 13.读者写者算法(互斥信号量）（15分） 14.单挂起进程模型，与无挂起五状态进程模型的区别（15分） 15.64位CPU虚拟段页式存储，地址分析，cache命中率（15分） 一、简答(5分*6) 1.什么是死锁，死锁的条件。 2.写出系统调用和普通函数调用的过程，比较二者区别。 3.线程的意义和实现方法。 4.什么是改进的多级目录，为什么改进的多级目录检索比多级目录快。 5.简述SVR5的惰性分配算法。 6.外设缓冲区的访问频率置换算法 二、问答 7.写优先的读者写者的reader和writer算法。(20分) 8.给了访问内存地址的序列，写访问页序列和各种算法缺页次数：(20) （5个逻辑页(480/100)，3个物理页(300)） FIFO, OPT, LRU, Clock。 9.成组链接算法，写两个函数：(20分) int Request() if(top=0) /add your code here else top=top-1; return stacktop+1; Release (int n) if(top=MAX) /add your code here else top=top+1; stacktop=n; 10.写运行结果并说明理由。(10分) #include void main(void) int I; while(I=fork()=-1); printf(Test.); if(I!=0) printf(It is parent process.n); wait(NULL); printf(My Child process, ID %d exited.n, I); exit(); else printf(It is child process.n); printf(It is parent or child process.n); exit(); 一.简答题(5*6) 1。可变间隔采样算法的功能及算法描述 2。系统调用和普通函数调用的过程，它们的异同 3。虚拟存储空间中地局部性原理是什么 4。FAT和NTFS文件系统对外存空闲块的管理方式 5。什么是多级目录和改进多级目录 6。操作系统对I/O的控制方式有那些，这些方式适用范围 二。问答 7（20) 已知父进程号为1000，之后，系统每创建一个进程，进程号增一 1） 根据下面的代码，画出父进程和子进程之间的关系（用进程号表示） 2） 写出打印结果并说明理由 void main() int i; int A; A=0; int child; for(i=0;iappend(currentThread); currentThread-Sleep(); value-; 第二种： value-; if(valueappend(currentThread); currentThread-Sleep(); 1) 这两种实现方法的不同点 2）这两种实现方法是否满足同步机制的准则，如果不满足，请举例 10。(10) CPU对数据的读取：如果在高速缓存中，时间为20ns 如果在内存中，则先读入高速缓存，再从Cache中读出，时间为60ns 如果在硬盘上，则先从硬盘中读入内存，时间12ms,再从内存读入高速缓存 再从高速缓存中读出 其中：高速缓存命中率为90%,内存则为60% 请问存储器的平均访问时间是多少 11。(10) 虚存采用页式管理，页面的大小为2KB，物理内存1MB，进程逻辑空间64KB 1) 给出进程逻辑地址的结构 2）请问页表有多少项，如果不考虑其它标志为，请位页表项至少多少位 3) 请问如果物理空间减少一半，页表有怎样的变化 1.多级目录和改进多级目录 2.FAT和NTFS文件系统的外存空闲空间管理方式 3.I/O操作的控制方式及其适用范围 4.系统调用和普通函数调用的过程和异同 5.可变采样间隔算法的功能和原理 6.页2K，物理地址1M，进程的逻辑页表64K 求页表共有多少项，每项至少多少位 若物理地址变为原来的一半，再求以上两问 7. 8.读者写者 9.一个程序写执行结果 10.计算平均访问时间（啊！506:(） 11.两个P原语问不同点，是否符合同步机制的要求，若不符合，举例说明 时间：2003年6月26日下午2：304：30 一、简答题： 1.（10分）描述双挂起进程模块和进程状态转换，以及它与UNIX系统的状态转换的区别 2.（15分）通过算法实例说明，在虚拟存储管理系统中如何调整系统中的进程总数，每 个进程的占用物理内存大小和每个进程逻辑地址空间中哪些逻辑页放在内存中。 3.（15分）描述UNIX文件系统管理空闲空间的成组链接法，即如何组织空闲空间块，及 它的空闲空间块分配和回收过程。 4.（10分）描述磁盘I/O调度中的循环扫描算法和双队列扫描算法。 二、问答题： 5.（25分） 假设操作系统只提供了信号量机制，并没有提供管程机制。1）试基于操作系统提供的 信号量类来实现管程类。要求用C+语言并给出必要注释。操作系统提供的信号量类为 SemaphoreClass，要求实现的管理类为MonitorClass。 class SemaphoreClass public: SemaphoreClass(LONG cInitialValue); void P(void); void V(void); ; class MonitorClass public: MonitorClass(void); void MonitorEnter(void); void MonitorLeave(void); void MonitorWait(SemaphoreClass hsemCondition, int *lpConditionCount); void MonitorSignal(SemaphoreClass hsemCondition, int *lpConditionCount); ; 2) 所谓生产者消费者问题是指，若干进程通过有限的共享缓冲区交换数据，其中生 产者进程不断写入，而消费者进程不断读出，共享缓冲区共有N个，任何时刻只能有一 个进程可对共享缓冲区进行操作，试用管程机制来解决生产者-消费者问题。给出 ProducerConsumerClass类的实现。 class ProducerConsumerClass public: void BufferWrite(void); /生产者进程的写操作 void BufferRead(void); /消费者进程的读操作 ; 6.（25分） 1）为了提高处理机的存储访问速度和存储容量，通常在计算机系统中都包括了由高速缓 存、内存和磁盘等多种存储介质。试说明在一个由上述三级存储介质组成的虚拟存储系统 中处理机访问进程逻辑地址空间中存储单元的过程。 2) Windows Server 2003 操作系统在Intel x86系列处理机上的虚拟存储系统中，使用32 位地址，物理页面大小为4KB，每个页表项占4B，采用两级页表进行地址映射，约定两级 页表在逻辑地址空间中占用从0XC000 0000到0XC03F FFFF的区域。试问： A）它的页目录项（PDE）有多少个？ B）它的页表项（PTE）有多少个？ C）页目录在逻辑地址空间中起始地址是多少？ D）如果在访问逻辑地址时出现缺页，系统会分配一个物理页面，并需要修改相应的页表项。逻辑地址0X77F61016对应的页 目录项和页表项在逻辑地址空间中的起始地址分别是多少？（建议给出计算过程） 一、简答题 1. (10分)高速缓存是硬件实现的，软件无法控制它的各种策略。那操作系统可以优化它的命中率吗？如不能，说明原因；如可以，说明机理。 2. (15分)虚拟存储管理的一个重要内容是根据局部性原理确定哪些页是很久不用应该被换掉的。什么是局部性原理？描述轮转置换算法和双指针轮转置换算法的工作过程 3. (10分)磁盘I/O调度和磁盘缓冲的目的分别是什么？试各举一个算法的例子。 4. (10分)为了保证I/O响应的速度，很多操作系统让刚完成I/O等待的进程/线程优先进入运行态。叙述UNIX和Windows Server 2003是怎样实现这一点的。 5. (10分)indows Server 2003 操作系统在Intel x86系列处理机上的虚拟存储系统中，使用32位地址，物理页面大小为4KB，每个页表项占4B，采用两级页表进行地址映射，用页目录用自映射。假设两级页表在逻辑地址空间中占用从0XD000 0000开始的区域（和实际的WS03有差异）。试问： A)页目录在逻辑地址空间中起始地址是多少？ B)逻辑地址0X5C6B 7A89的页目录和页表的逻辑地址是多少？ 二、问答题 6. (20分)文件卷中保存了每一个文件占用哪些簇和这些簇的顺序信息。 1)文件存储的方式有哪些？即有哪些方式来表示这些簇和它