下载文档原格式
北交《计算机体系结构》在线作业一一、单选题（共 20 道试题，共 60 分。
）1. 在h存储器中常用的地址映象方式是（）。
. 全相联映象. 页表法映象. 组相联映象. 段页表映象正确答案：2. 计算机系统结构不包括( )。
. 主存速度. 机器工作状态. 信息保护. 数据表示正确答案：3. ( )属于MIM系统结构。
. 各处理单元同时受同一个控制单元的管理. 各处理单元同时接受同一个控制单元送来的指令. 松耦合多处理机和多计算机. 阵列处理机正确答案：4. 多处理机的各自独立型操作系统( )。
. 要求管理程序不必是可再入的. 适合于紧耦合多处理机. 工作负荷较平衡. 有较高的可靠性正确答案：5. 在系统结构设计中，提高软件功能实现的比例会( )。
. 提高解题速度. 减少需要的存贮容量. 提高系统的灵活性. 提高系统的性能价格比正确答案：6. 用户高级语言源程序中出现的读写 (I/O) 语句，到读写操作全部完成，需要通过 ( )共同完成。
. 编译系统和操作系统. I/O 总线、设备控制器和设备. 操作系统和 I/O 设备硬件. 编译系统、操作系统软件和 I/O 总线，设备控制器、设备硬件等正确答案：7. 对汇编语言程序员透明的是( )。
. I/0方式中的M访间方式. 浮点数据表示. 访问方式保护. 程序性中断正确答案：8. 在计算机系统设计中，比较好的方法是( )。
. 从上向下设计. 从下向上设计. 从两头向中间设计. 从中间开始向上、向下设计正确答案：9. 计算机系统中主存一辅存存储层次或 h 一主存存储层次常用的替换算法是 ( )。
. 随机算法. 近期最少使用算法. 先进后出算法. OPT 算法正确答案：10. 下列说法中不正确的是( )。
. 软件设计费用比软件重复生产费用高. 硬件功能只需实现一次，而软件功能可能要多次重复实现. 硬件的生产费用比软件的生产费用高. 硬件的设计费用比软件的设计费用低正确答案：11. 关于软硬件功能是等效的，提高硬件功能的比例以下说法中，不正确的是( )。
第一章１.６ 某台主频为４０0M Ｈz 的计算机执行标准测试程序,程序中指令类型、执行数量和平均时钟周期数如下：求该计算机的有效CPI 、ＭIP Ｓ和程序执行时间。
解：（1）C ＰＩ ＝(45000×１+75000×2＋8０00×4＋1500×2) ／ 1295０0＝１.７7６ (或259460） （2）MIPS 速率＝f/ C ＰI ＝40０/１.776 =22５．225MIPS (或2595180MIPS) (3)程序执行时间＝ (45000×1＋750０0×2+8000×4＋１500×2)/40０＝5７5μｓ 1．9 假设某应用程序中有4类操作,通过改进，各操作获得不同的性能提高。
具体数据（1)改进后，各类操作的加速比分别是多少？(2）各类操作单独改进后,程序获得的加速比分别是多少？ (３）4类操作均改进后，整个程序的加速比是多少? 解：根据Amdahl 定律SeFeFe S n +-=)1(1可得４类操作均改进后，整个程序的加速比：2.16)1(1≈+-=∑∑iii n S F F S1.10 第二章变长编码，哈夫曼编码第三章３.12 有一条指令流水线如下所示：(1）求连续输入10条指令的情况下，该流水线的实际吞吐率和效率。
(２)该流水线的瓶颈在哪一段？请采用两种不同的措施消除此瓶颈。
对于你所给出的两种新的流水线，连续输入１0条指令时,其实际吞吐率和效率各是多少? 解:(1)本题主要考察对各功能段用时不等的线性流水线的性能计算公式的掌握情况。
2200(ns)2009200)10050(50t n t T maxki i =⨯++++=∆-+∆=∑=)1(1流水 )(ns 2201T nTP 1-==流水45.45%1154400TP ktTP E k1i i≈=⋅=∆⋅=∑= 注意：对于公式不能死记硬背，需要充分理解，注意公式的适用条件。
以下习题来自《计算机系统结构》第七章存储体系。
7．1解释下列术语直接映像：每个主存地址映像到Cache中的一个指定地质的方式称为直接映像。
全相联映像：任何主存地址可映像到任何Cache地址的方式称为全相联映像。
组相联映像：组相联映像指的是将存储空间的页面分成若干组，各组之间是直接映像，而组内各块之间是全相联映像。
全写法：全写法也称直达法，即写操作将数据同时写入Cache和缓存。
写回法：写Cache时不写主存，仅当被写Cache数据块要被替换出去时才写回主存。
虚拟存储器：虚拟存储器是主存的扩展，当主存的容量不能满足要求时，数据可存放在外存中，在程序中仍然按地址访问外存空间。
大小取决于计算机的访存能力。
段式管理：把主存按段分配的存储管理方式称为段式管理。
页式管理：把虚拟存储空间和实际存储空间等分成固定大小的页，各虚拟页可装入主存中不同的实际页面位置。
段页式管理：段页式管理式段式管理和页式管理的结合，他将存储空间按逻辑模块分成段，每段又分成若干个页，访存通过一个段表和若干个页表进行。
段的长度必须是页的长度的整数倍，段的起点必须是某一页的起点。
快表：为了提高页表中常用项的访问速度，采用快速硬件构成的比全表小的多的部分表格。
慢表：存放在主存中的整个页表。
高速缓存：高速缓冲存储器是位于CPU和主存之间的高层存储子系统。
时间局部性：如果一个存储项被访问，则可能该项会很快再次被访问。
空间局部性：如果一个存储项被访问，则该项及其邻近的相也可能很快被访问。
段表：在对虚拟内存进行管理时，系统中用于指明各段在主存中的位置的表，表中包括段名或段号、段起点、装入位和段长等。
页表：在对虚拟内存进行管理时，系统中用于指明各页在主存中的位置的表，表中包括页号、每页在主存中的起始位置、表示该页是否已装入主存的装入位等。
块表：存储系统中的一个用于解决块和页的定位、标志、和寻址问题的表。
7.2 有人认为,随着存储器芯片集成度的提高，主存的容量将越来越大，虚拟存贮器将被淘汰，未来的计算机中将不采用虚拟存储器。
电脑组成原理大作业院〔系〕：物联网工程学院专业: 电脑科学与技术班级：学号:姓名：摘要1.电脑硬件系统：到目前为止，电脑电脑硬件系统。
其基本设计思想为：a.以二进制形式表示指令和数据。
b.程序和数据事先存放在存储器中，电脑在工作时能够高速地从存储器中取出指令加以执行。
c.由运算器、控制器、存储器、输入设备和输出设备等五大部件组成电脑硬件系统。
2.电脑软件系统：所谓软件，就是为了管理、维护电脑以及为完成用户的某种特定任务而编写的各种程序的总和。
电脑的工作就是运行程序，通过逐条的从存储器中取出程序中的指令并执行指令所规定的操作而实现某种特定的功能。
微型电脑的软件包括系统软件和用户〔应用〕软件。
关键词：电脑系统硬件存储器控制器运算器软件目录摘要 (2)第一章总体设计 (4)问题描述 (4)实验环境 (4)软件介绍 (4)模块介绍 (4)实验目的 (5)实验内容 (5)第二章原理图 (6)第三章管脚分配 (7)第四章微程序设计 (8)1. alu_74181 (8)2. romc (9)第一章总体设计问题描述从两个reg_74244中分别取出两数经过总线，各自分别到达两个寄存器reg_74373，再由两个寄存器到达运算器alu_74181，在运算器里经过运算得出结果，结果再由总线传输进入另外的一个寄存器reg_74373，输出。
实验环境软件介绍ISE的全称为Integrated Software Environment，即“集成软件环境”，是Xilinx公司的硬件设计工具。
它可以完成FPGA开发的全部流程，包括设计输入、仿真、综合、布局布线、生成BIT文件、配置以及在线调试等，功能非常强大。
ISE除了功能完整，使用方便外，它的设计性能也非常好，拿ISE 9.x来说，其设计性能比其他解决方案平均快30%，它集成的时序收敛流程整合了增强性物理综合优化，提供最正确的时钟布局、更好的封装和时序收敛映射，从而获得更高的设计性能。
第一章 计算机体系结构的基本概念1.6 对于一台400MHz 计算机执行标准测试程序，程序中指令类型，执行数量和平均时钟解：IC CPI IC CPI ii/)(∑⨯=45000175000280004150021.776450007500080001500CPI ⨯+⨯+⨯+⨯==+++640010225.2251.776f MIPS MIPS CPI ⨯===速率程序执行时间=64(4500017500028000415002)/(40010) 5.7510-⨯+⨯+⨯+⨯⨯=⨯s1.7 将计算机系统中某一功能的处理速度加快10倍，但该功能的处理时间仅为整个系统运行时间的40％，则采用此提高性能的方法后，能使整个系统的性能提高多少？解：部件加速比＝11，可改进比例＝40％ 系统加速比＝11 1.5714(10.4(1--＝＝0.4可改进比例）＋可改进比例）＋部件加速11比1.8 计算机系统有三个部件可以改进，这三个部件的加速比如下：部件加速比1＝30； 部件加速比2＝20； 部件加速比3＝10；(1) 如果部件1和部件2的可改进比例为30％，那么当部件3的可改进比例为多少时，系统的加速比才可以达到10？(2) 如果三个部件的可改进比例为30％、30％和20％，三个部件同时改进，那么系统中不可加速部分的执行时间在总执行时间中占的比例是多少？ 解：1）在多个部件可改进情况下Amdahl 定理的扩展:⎥⎦⎤⎢⎣⎡+-=e e e o e S f f T T )1(eee Sf f S +-=)1(1∑∑+-=iii ii S f f S )1(1式中，fi 为可加速部件i 在未优化系统中所占的比例；Si 是部件i 的加速比。
1332211321)](1[-⎭⎬⎫⎩⎨⎧+++++-=S f S fS f f f f S13330203.0303.0)]3.03.0(1[10-⎭⎬⎫⎩⎨⎧+++++-=f f36.0180653==f2）82.07.14126012602.1609.0606.02.02.0102.0203.0303.02.02.0102.0203.0303.0)]2.03.03.0(1[==+++=+++=+++++-=T TT T T p1.9 解：1).操作1加速比＝2/12= 操作2加速比＝20/154/3= 操作3加速比＝10/3 操作4加速比＝4/14=2).改进前程序执行总时间＝10×2+30×20+35×10+15×4＝1030操作1改进后，程序获得的加速比为：11.0110*2/1030(110*2/1030)2=-+操作2改进后，程序获得的加速比为：11.1630*20/1030(130*20/1030)4/3=-+操作3改进后，程序获得的加速比为：11.3135*10/1030(135*10/1030)10/3=-+操作4改进后，程序获得的加速比为：11.0515*4/1030)(115*4/1030)4=-+3).四类操作均改进后，整个程序的加速比是：10301.7810*130*1535*315*1=+++。
= 1.099（2）采用固定的2个时钟周期延迟时，程序执行的CPI = CPI基本+分支延迟= 1 + 15%×2=1.3显然采用分支目标缓冲器时程序执行时间更少，即速度更快。
4.5 假设分支目标缓冲的命中率为90%，程序中无条件转移指令的比例为5%，没有无条件转移指令的程序CPI值为1。
假设分支目标缓冲中包含分之目标指令，允许无条件转移指令进入分支目标缓冲，则程序的CPI值为多少？假设无条件分支指令不进入分支目标缓冲时程序执行的CPI为1.1解：无条件分支指令的特点是只要执行肯定分支成功。
因此，对于进入分支目标缓冲器的无条件分支指令，分支预测的精度为100%，也就不会带来分支延迟。
而没有进入分支目标缓冲器的无条件分支指令会带来一定分支延迟。
首先要求出一条无条件分支指令的分支延迟是多少，不妨设为x个时钟周期。
由题知无条件分支指令不进入分支目标缓冲时程序执行的CPI 为1.1，而程序中没有无条件转移指令的CPI为1，因此有CPI = CPI无分支指令+无条件分支延迟= 1 + 5%x = 1.1 所以x= 2因此，允许无条件分支指令进入分支目标缓冲器时，（5）伪相联Cache（6）硬件预取技术（7）由编译器控制的预取（8）编译器优化。
5.5 简述减小cache失效开销的几种方法。
答：(1) 让读失效优先于写。
(2) 写缓冲合并。
(3) 请求字处理技术。
(4) 非阻塞Cache或非锁定Cache技术。
(5) 采用二级Cache。
5.8 组相联Cache的失效率比相同容量直接映像Cache的失效率低。
由此能否得出结论：采用组相联映像一定能带来性能上的提高？为什么？答：不一定。
因为组相联命中率的提高是以增加命中时间为代价的，组相联需要增加多路选择开关。
5.10 假设对指令Cache的访问站全部访问的75%；而对数据Cache的访问占全部访问的25%。
Cache的命中时间为1个时钟周期，失效开销为50个时钟周期，在混合Cache中一次load或store操作访倍，而两路组相联Cache的平均性能比直接映象cache要高1.003倍。
第3次作业一、填空题（本大题共20分，共 5 小题，每小题 4 分）1. 流水机器处理中断处理有两种方式： ______ 和 ______ 。
2. ILLIAC IV中的一个PU为处理部件由 ______ 、 ______ 、 ______ 构成。
3. PM2I网络能实现与j号处理单元直接相连的是号为 ______ 的处理单元。
4. 在虚拟存储系统中，两级存储器的速度相差特别悬殊T2=106T１。
如果要使访问效率e=0.95，命中率为 ______ 。
5. 浮点数0.01|10…0在|处溢出，按截断法，舍入法和恒置1法进行溢出处理，其结果分别为 ______ 、 ______ 、 ______ 。
二、基本应用题（本大题共30分，共 2 小题，每小题 15 分）1. 主存容量位4MB，虚存容量位1GB，虚拟地址和物理地址各是多少？若页面大小为4KB，页表长度是多少？2. 某计算机cache采用全相联映像，已知cache容量为16kB，主存容量位2MB，每个字块有8个字，每个字32位。
问主存和cache地址多少位，如何划分？三、问答题（本大题共30分，共 5 小题，每小题 6 分）1. 浮点数设计的要点是什么？2. 简述多端口存储器的基本结构和工作原理。
3. 减少指令中地址码位数的主要方法是什么？4. 为什么说软件为基础解决cache一致适合处理机较多的场合？5. 为什么当处理机有自己的cache时，需要按二维方式构造存储器？四、简答题（本大题共20分，共 5 小题，每小题 4 分）1. 简述脉动阵列机的结构特点。
2. 简述并行性开发的途径和相关例子。
3. 简述数据表示发展。
4. 简述操作码优化的目的和基本方法。
5. 比较浮点数尾数溢出后的截断法和舍入法的特点。
答案：一、填空题（20分，共 5 题，每小题 4 分）1.参考答案：不精确断点法、精确断点法解题方案：评分标准：2.参考答案：一个64 位的算术处理单元PE、局部存贮器PEM、存贮器逻辑部件MLU解题方案：评分标准：3.参考答案：j±2i解题方案：评分标准：4.参考答案：由公式：\\10.52.27.1\ResourceFile\ProblemPool\152\StudentFiles\ExamBatch_21\2 0022a\cq142cengx\3250可知，0.95=1/H+(1-H)106，得H=0.9999999。
计算机系统结构第五版习题答案1.层次结构现代通用的计算机系统是由紧密相关的硬件和软件组成的。
从使用语言的角度，可以将系统看成是按功能划分的多层机器级组成的层次结构，由高到低分别为应用语言机器级、高级语言机器级、汇编语言机器级、操作系统机器级、传统机器语言机器级和微程序机器级。
2.计算机系统结构也称计算机体系结构，它只是系统结构中的一部分，指的是层次结构中的传统机器级的系统结构。
其界面之上包括操作系统级、汇编语言级、高级语言级和应用语言级中所有软件的功能，该界面之下包括所有硬件和固件的功能。
3.计算机实现指的是计算机组成的物理实现，包括处理机、主存等部件的物理结构，器件的集成度和速度，器件、模块、插件、底板的划分与连接，专用器件的设计，微组装技术，信号传输，电源、冷却及整机装配技术等。
它着眼于器件技术和微组装技术，其中，器件技术在实现技术中起着主导作用。
4.数据表示指的是能由机器硬件直接识别和引用的数据类型。
5.霍夫曼压缩概念霍夫曼压缩概念的基本思想时，当各种事件发生的概率不均等时，采用优化技术，对发生概率最高的事件用最短的位数来表示，而对出现概率较低的事件允许用较长的位数来表示，就会使表示的平均位数缩短。
6.RISC精简指令系统（RISC），不是简单地把指令系统进行简化，而是通过简化指令的途径使计算机的结构更加简单合理，以减少指令的执行周期数，从而提高运算速度。
7.CISC复杂指令系统（CISC），设计风格力图缩小机器语言与高级语言的语义差距，使源程序长度尽可能的短，以及尽可能少的访问存储器和执行尽可能少的指令，以求获得高性能。
8.非专用总线可以被多种功能或多个部件所分时共享，同一时间只有一对部件可使用总线进行通信。
9.数据宽度I/O设备取得I/O总线后所传送数据的总量.10.中断响应次序是在同时发生多个不同中断类的中断请求时，中断响应硬件中的排队器所决定的响应次序。
11.中断处理次序中断处理完的次序，也即中断处理程序完成中断处理的次序。
完成以下带队号的题√. 各章所占试题的比例第一章 30％第二章 10% 第三章 30%第五章10％第六章10% 第七章10％所用教材计算机系统结构张晨曦第一章计算机体系结构的基本概念√1. 解释下列术语：层次结构翻译解释体系结构透明性系列机软件兼容兼容机计算机组成计算机实现并行性时间重迭资源重复资源共享同构型多处理机异构型多处理机紧密耦合响应时间测试程序大概率事件优先系统加速比Amdahl 定律程序的局部性原理CPI√2。
传统的存储程序计算机的主要特征是什么?存在的主要问题是什么?我们目前的计算机系统是如何改进的？√3。
假设在某程序的执行过程中，浮点操作时间占整个执行时间的10% ，现希望对浮点操作加速. （1）设对浮点操作的加速比为Sf。
画出程序总加速比Sp和Sf之间的关系曲线;（2)请问程序的最大加速比可达多少?√4。
计算机系统中有三个部件可以改进方法，这三个部件的部件加速比如下：部件加速比1 = 30部件加速比2 = 20部件加速比3 = 10（1）如果部件1和部件2的可改进比例均为30％,那么当部件3的可改进比例为多少时，系统加速比才可以达到10?（2）如果三个部件的可改进比例分别为30%、30％和20%，三个部件同时改进，那么系统中不可加速部分的执行时间在总执行时间中占的比例是多少?(3）如果相对某个测试程序三个部件的可改进比例分别为20％、20%和70％，要达到最好改进效果，仅对一个部件改进时,要选择那个部件?如果允许改进两个部件，又如何选择？第二章计算机指令集结构设计1. 解释下列术语堆栈型机器累加器型机器通用寄存器型机器有效地址√CISC√RISC指令集结构的正交特性2。
堆栈型机器、累加器型机器和通用寄存器型机器各自有什么优缺点？3。
常见的三种类型的通用寄存器型机器的优缺点有哪些？4. 指令集结构设计所涉及的内容有哪些？√ 5. 简述CISC指令集结构功能设计的主要目标。
从当前的计算机技术观点来看，CISC 指令集结构的计算机有什么缺点?√6。
0 《计算机系统结构》大作业 介绍并行算法与并行程序设计 及它们的不足及发展趋势
专 业 计算机科学与技术(软件工程) 指导教师 班 级 计Y09 学 号 2009004003 姓 名 日 期 2012年 4月17日
计算机学院 1
摘要：并行算法是并行计算中非常重要的问题。这篇报告首先简要介绍并行计算，然后主要讨论并行算法研究中的问题和今后的方向，最后阐述并行计算研究中存在的问题以及今后面临的挑战。并行算法研究应该确立一个“理论－设计－实现－应用”的系统方法，形成一个完善的 “架构—算法—编程” 方法论，这样才能保证并行算法不断发展并变得更加实用。再结合例子进而介绍并行算法的基本原理，给并行算法下一个基本的定义，对并行算法进行了相关的介绍；接着根据目前并行算法的应用，提出了在计算机系统结构中以并行算法为基础的一些并行程序设计的应用，比较了目前流行的并行程序设计的方法，并通过比较指出它的不足以及并行程序设计在未来的发展趋势和前景。 关键词：计算机系统结构 并行算法 并行程序设计 引言 并行计算机从70年代的开始，到80年代蓬勃发展和百家争鸣，再到90年代体系结构框架趋于统一，近年来其快速发展，并行机技术日趋成熟。首先是市场的需求，一直是推动并行计算机发展的主要动力，大量实际应用部门，如天气预报、核武器、石油勘探、地震数据处理、飞行器数值模拟以及其他大型事务处理等，都需要每秒执行数十万亿次乃至数百万亿此浮点运算的计算机，基于这些应用问题本身的限制，并行计算是满足它们的唯一可行途径。 使用多计算机进行并行程序设计，它们之间的通信是通过发送消息来完成的，所以消息传递需要并行程序设计。并行程序设计使用多计算机或多个内部处理器的计算机来求解问题，它比使用单台计算机的计算速度要快得多。并行程序设计也为求解更大规模的问题提供了机会，前面所述问题需要更多的计算步或更大存储容量需求，并行程序设计以并行算法为核心，能满足这要求，因为多计算机和多处理机系统通常比单计算机有更大的总存储容量。 1并行算法的原理 1.1为什么要做并行计算？ 人类对计算及性能的要求是无止境的从系统的角度：集成系统资源，以满足不断增长的对性能和功能的要求；从应用的角度：适当分解应用，以实现更大规模或更细致的计算 1.2并行算法的基本原理 并行计算（Parallel Computing）是指同时使用多种计算资源解决计算问题的过程。并行计算的主要目的是快速解决大型且复杂的计算问题。此外还包括：利用非本地资源，节约成本 ― 使用多个“廉价”计算资源取代大型计算机，同时克服单个计算机上存在的存储器限制。传统地，串行计算是指在单个计算机（具有单个中央处理单元）上执行软件写操作。CPU 逐个使用一系列指令解决问题，但其中只有一种指令可提供随时并及时的使用。并行计算是在串行计算的基础上演变而来，它努力仿真自然世界中的事务状态：一个序列中众多同时发生的、复杂且相关的事件。 2
简单的说，算法就是求解问题的方法和步骤。并行算法，就是在并行机上用很多个处理器联合求解问题的方法和步骤。实际上，在自然界中并行是客观存在的普遍现象，关键问题在于能不能很好的利用。由于人们的思维能力以及思考问题的方法对并行不太习惯，且并行算法理论不成熟，所以总是出现了需求再来研究算法，不具有导向性，同时实现并行算法的并行程序性能较差，往往满足不了人们的需求。并行算法的研究历史可简单归纳为：上世纪70到80年代，并行算法研究处于高潮；到上世纪90年代跌入低谷；目前，又处于研究的热点阶段。现在，人们已经可以自己搭建PC cluster，利用学习到的理论知识来解决实际问题，不再是纸上谈兵，这也为我们提供了新的机遇和挑战。并行算法就是用多台处理机联合求解问题的方法和步骤，其执行过程是指将给定的问题首先分解成若干个尽量相互独立的子问题，然后使用多台计算机同时求解它，从而最终求得原问题的解。并行算法是并行计算中一个非常重要的问题。并行算法的研究应该确立一个“理论－设计－实现－应用”的系统方法，形成一个完善的 “架构—算法—编程” 方法论，这样才能保证并行算法不断发展并变得更加实用。简单的说，算法就是求解问题的方法和步骤。并行算法，就是在并行机上用很多个处理器联合求解问题的方法和步骤。 （1）并行计算的特点 ① 将工作分离成离散部分，有助于同时解决； ② 随时并及时地执行多个程序指令； ③ 多计算资源下解决问题的耗时要少于单个计算资源下的耗时。 并行计算是相对于串行计算来说的，所谓并行计算分为时间上的并行和空间上的并行。 时间上的并行就是指流水线技术，而空间上的并行则是指用多个处理器并发的执行计算。 （2）列举并行算法的三个基本类型 ① SIMD-SM上的非线性方程求根同步并行算法：这种计算问题无法在串行机器上很快地得出结果，我们只有把这种计算问题应用在并行计算机上才有可能在较短的时间内获得满足实际应用的需要。 ② 2.4 SIMD-SM上的同步并行求和算法：共享存储器的的容量是有限的，如果在同一时刻，多个处理器一起访问同一处理单元时就会发生冲突，所以共享存储模型根据解决冲突的能力还可以分为3类，其中的一类EREW(Exclusive-Read Exclusive-Write)计算模型是不允许有两个处理器同时读或写一个共享单。 ③ SIMD-CC超立方机器上的同步并行求和算法：假设在n-维超立方模型上，n=2m,n个原始数据为X={x0，x1，„，xn-1}，其中m为正整数，每个处理器Pi都可以存储局部变量ai，下面在此模型上构造一个并行求和算法，使得算法结束时a0就是总和，对超立方体节点用二进制进行编号，要求每相邻的结点之间只有且仅有一位不同。然后将这些结点分为两类，一类是最高位的编号为0，则另一类是最高位的编号为1，然后可以利用超立方模型中结点相邻关系可建立二类处理器集合中元素的一一对应关系，然后可以根据这种对应关系构造并行算法。算法的思想是：A.对于n个处理器，首先将最最高位编号为1的处理器的数据传送至最高位编号为0的处理器并进行局部求和；B.接着在n/2个处理器上，将次高位编号为 3
1的处理器上的数据传送至次高位编号为0的处理器并惊醒局部求和. 2．并行程序设计 并行程序设计不同于顺序程序设计，主要在于对问 题采取何种看法：顺序程序设计把事物的变化发展看成 是单线程的，按先后顺序发展。并行程序设计把一个事物的行为看成是多个事物互相作用的结果，多个事物可以并行的发展。这是一个观念上的根本转变，根据这个观点，并行程序设计的核心内容就是并行划分与算法映射。要研究并行程序设计，就需要了解并行算法的结构和设计模型。 2.1 目前流行的并行程序设计方法 隐式并行程序设计：常用传统的语言编程成顺序源编码，把“ 并行” 交给编译器实现自动并行程序的自动并行化是一个理想目标，存在难以克服的困难语言容易，编译器难；显式并行程序设计：在用户程序中出现“并行”的调度语句显式的并行程序开发则是解决并行程序开发困难的切实可行的，语言难，编译器容易。 4
2.1.1隐式并行（Implicit Parallel） （1）概况：程序员用熟悉的串行语言编程(未作明确的制定并行性)编译器和运行支持系统自动转化为并行代码。 （2）优缺点：语义简单，可移植性好，单线程，易于调试和验证正确性，细粒度并行；效率很低 2.1.2数据并行（Data Parallel） （1）概况：SIMD的自然模型局部计算和数据选路操作 （2）特点：单线程、并行操作于聚合数据结构（数组）、松散同步、单一地址空间、隐式交互作用、显式数据分布 ① 优点: 编程相对简单, 串并行程序一致. ② 缺点: 程序的性能在很大程度上依赖于所用的编译系统及用户对编译系统的了解. 并行粒度局限于数据级并行,粒度较小. 2.1.3共享变量（Shared Variable） （1）概况：PVP, SMP, DSM的自然模型 （2）特点：多线程：SPMD, MPMD、异步、单一地址空间、显式同步、隐式数据分布、隐式通信 2.1.4消息传递（Message Passing） （1）概况：MPP, COW的自然模型 （2）特点：多线程、异步、多地址空间、显式同步、显式数据映射和负载分配、显式通信 所有并行程序设计标准可分为以下三类:数据并行HPF, Fortran90用于SMP, DSM、共享编程OpenMP用于SMP, DSM、消息传递MPI, PVM用于所有并行计算机。三者可混合使用:如对以SMP为节点的Cluster 来说, 可以在节点间进行消息传递,在节点内进行共享变量编程。 接下来具体介绍一下目前最流行的MPI并行程序设计方法： 传统的串行计算，分为“指令”和“数据”两个部分，并在程序执行时“独立地申请和占有”内存空间，且所有计算均局限于该内存空间。并行计算将进程相对独立的分配于不同的节点上，由各自独立的操作系统调度，享有独立的CPU和内存资源(内存可以共享)；通过网络联接的不同计算机的多个进程，进程位于不同的计算机，消息传递是实现进程间通信的唯一方式；消息传递的实现是基于网络socket机制，用户不必关心；进程间可以相互交换信息如数据交换、同步等待，消息是这些交换信息的基本单位。消息传递操作有发送消息(send)、接受消息(receive)、进程同步(barrier)、规约(reduction)；根据应用程序对消息传递功能的需求，全球工业、应用和研究部门联合推出标准的消息传递界面函数，不考虑其具体实现，以保证并行应用程序的可移植性在当前所有的消息传递软件中，最重要最流行的是MPI，MPI表示消息传递接1：1(Message Passing Interface)，它能运行在所有的并行平台上，包括SMP和PVP。二者已经在Windows NT和Windows 9X这样的非Unix平台上实现，程序设计语言支持C，Fortran和Java。在
