并行计算__中国科学技术大学(1)--测验习题1

格式：pdf
大小：130.70 KB
文档页数：5

下载文档原格式

/ 5

并行计算试题及答案(20011.1)

计算机学院研究生《并行计算》课程考试试题（2010级研究生，2011.1）1．（12分）定义图中节点u和v之间的距离为从u到v最短路径的长度。

已知一个d维的超立方体，1）指定其中的一个源节点s，问有多少个节点与s 的距离为i，其中0≤i≤d。

证明你的结论。

2）证明如果在一个超立方体中节点u与节点v的距离为i，则存在i！条从u到v的长度为i的路径。

1)有个节点与s的距离为i。

证明：由超立方体的性质知：一个d维的超立方体的每个节点都可由d位二进制来表示，则与某个节点的距离为i的节点必定在这d位二进制中有i位与之不同，那么随机从d位中选择i位就有种选择方式，即与s的距离为i得节点就有个。

2)证明：由1）所述可知：节点u与节点v的距离为i则分别表示u、v节点的二进制位数中有i 位是不同的。

设节点u表示为：，节点v表示为：，则现在就是要求得从变换到的途径有多少种。

那么利用组合理论知识可知共有即中途径。

所以存在i！条从u到v的长度为i的路径。

2．（18分）6个并行程序的执行时间，用I-VI表示，在1-8个处理器上执行了测试。

下表表示了各程序达到的加速比。

加速比处理器数I II III IV V VI1 1.00 1.00 1.00 1.00 1.00 1.002 1.67 1.89 1.89 1.96 1.74 1.943 2.14 2.63 2.68 2.88 2.30 2.824 2.50 3.23 3.39 3.67 2.74 3.655 2.78 3.68 4.03 4.46 3.09 4.426 3.00 4.00 4.62 5.22 3.38 5.157 3.18 4.22 5.15 5.93 3.62 5.848 3.33 4.35 5.63 6.25 3.81 6.50对其中的每个程序，选出最适合描述其在16个处理器上性能的陈述。

a）在16个处理器上的加速比至少比8个处理器上的加速比高出40%。

2021年中国科学院大学计算机科学与技术专业《计算机组成原理》科目期末试卷B(有答案)

2021年中国科学院大学计算机科学与技术专业《计算机组成原理》科目期末试卷B（有答案）一、选择题1、某指令系统有200条指令，对操作码采用固定长度二进制编码时，最少需要用（）A.4B.8C.16D.322、下列关于各种寻址方式获取操作数快慢的说法中，正确的是（）。

I.立即寻址快于堆栈寻址Ⅱ.堆栈寻址快于寄存器寻址Ⅲ.寄存器一次间接寻址快于变址寻址Ⅳ.变址寻址快于一次间接寻址A. I、IVB.Ⅱ、ⅢC.I、Ⅲ、IVD.Ⅲ、Ⅳ3、假设寄存器的内容为00000000，若它等于-128，则该机器采用了（）。

A.原码B.补码C.反码D.移码4、假定变量i、f、d的数据类型分别为int、float、double（int用补码表示，float 和double用IEEE754标准中的单精度和双精度浮点数据格式表示），已知i=785，f-l.5678e3，d=1.5el00，若在32位机器中执行下列关系表达式，则结果为真的是（）。

I.i==（int）（float）i Ⅱ.f==（float）（int）fIⅡ.f==（float）（double）f Ⅳ.（d+f）-d=fA.仅I、ⅡB.仅I、ⅢC.仅Ⅱ、ⅢD.仅Ⅲ、Ⅳ5、在C语言程序中，下列表达式中值为True的有（）。

I.123456789=（int）（float）l23456789Ⅱ.123456==（int）（float）1234561Ⅲ.123456789-（int（double）123456789A.仅I、ⅡB. 仅I、ⅢC.仅Ⅱ、ⅢD. I、Ⅱ、Ⅲ、6、某计算机的存储系统由Cache一主存系统构成，Cache的存取周期为10ms，主存的存取周期为50ms。

在CPU执行一段程序时，Cache完成存取的次数为4800次，主存完成的存取次数为200次，该Cache一主存系统的效率是（）。

【注：计算机存取时，同时访问Cache和主存，Cache访问命中，则主存访问失效；Cache访问未命中，则等待主存访问】A.0.833B.0.856C.0.95 8D.0.8627、一个存储器的容量假定为M×N，若要使用I×k的芯片（I<M，k<N），需要在字和位方向上同时扩展，此时共需要（）个存储芯片。

2011并行程序设计期末考试卷 - 参考答案

五、矩阵相乘的另一种并行算法是 Fox 算法（Fox Algorithm）：将待相乘的矩
阵 A 和 B 分成 p 个方块 Ai,j 和 Bi,j (0≤i,j≤ 并将它们分配给
p p
p 1 ),每块大小为(
n
p
)× ( nP0,1, … ,P
p 1 , p 1 )。开始时处理器
语句 S 流依赖于语句 T，即 T f S，满足依赖关系的偶对集合为： { <T(i), S(j)> | i = j -2 ; 6≤j≤100 }

语句 S 输出依赖于语句 U，即 U o S ，满足依赖关系的偶对集合为： { <U(i), S(j)> | i = j -1 ; 5≤j≤100 }
参考解答：依题意，主要是完成函数 MPI_Type_indexed 的参数填写工作。（1）由下三角矩阵构成的派生消息类型 lowTriangle; count=N; // 下三角矩阵包含 N 个数据块 for(i=0;i<N;i++) blocklens[i] = i+1; //每块数据含 1、2、…、N 个数据 for(i=0;i<N;i++) indices[i] = i*N; //每块首元素偏移从 0、N、2*N…、(N-1)*N MPI_Type_indexed(count,blocklens,indices,MPI_INT,&lowTriangle); MPI_Type_commit(&lowTriangle); （2）主条带派生消息类型 mainStripe count=N; // 主条带矩阵包含 N 个数据块 blocklens[0] = 2;//首个数据块包含 2 个 old_type 数据 blocklens[N-1] = 2; //最后的数据块包含 2 个 old_type 数据 for(i=1;i<N-1;i++) blocklens[i] = 3; //其余各块均包含 3 个 old_type 数据 indices[0] = 0;//首块偏移为 0； for(i=1;i<N;i++) indices[i] = i*(N+1);//其余各块偏移。 MPI_Type_indexed(count,blocklens,indices,MPI_INT,&mainStripe); MPI_Type_commit(&mainStripe); （3） 5×5 的上三角矩阵 upTriangle5 count = 5; //含 5 个数据块 for(i=0;i<5;i++) blocklens[i] = 5-i; // 每块长度依次为 5、4、3、2、1 indices[0] = 0;//首块偏移为 0； for(i=1;i<5;i++) indices[i] = i*(N+1);//其余各块偏移 MPI_Type_indexed(count,blocklens,indices,MPI_INT,&upTriangle5); MPI_Type_commit(&upTriangle5); if(rank==0){ MPI_Send(&SA[0][11],1, upTriangle5, 1,2012,MPI_COMM_WORLD); } else if(rank==1){ MPI_Recv(&SA[0][11],1,upTriangle5, 0,2012,MPI_COMM_WORLD,&status); }

中国科学技术大学期末考试试卷

一、填空题1．常用的并行算法设计的基本技术有_______ _________，___________________，_______________________，____________ ______，_____________________，_______________________等。

2．常见的并行计算模型有____________ ______，_____________________，_______________________，____________ ______等。

3．PCAM设计过程分为_________，__________，_________ 和_________四步。

4．常见的并行程序设计模型包括__ ___________，__ _____________，______________________，______________________等。

二、问答题1．请简述从上个世纪80年代至今，主流并行计算机体系结构的变化趋势。

2．基于蝶式计算原理的FFT在二维mesh连接和蝶式网络连接的处理器上均可并行实现。

（1）请问哪种实现效率较好？并给出原因。

（2）蝶式网络连接的处理器在实际的并行计算机系统并不常见，这是否会影响FFT在蝶式网络连接上的并行实现在实际中的使用？为什么？3．基本的开关技术有哪两种？各具有什么特点？三、阅读题1．阅读以下新闻报道，回答问题。

2004 年6月29日国家科技部今日在人民大会堂宣布：“863计划重点项目——曙光4000A通过鉴定验收，曙光4000A实现了对每秒10万亿次运算速度的技术和应用的双跨越，成为国内计算能力最强的商品化超级计算机”。

在今年6月22日刚刚公布的全球高性能计算机TOP500排行榜中，曙光4000A以每秒11万亿次的峰值速度和80610亿次Linpack计算值位列全球第十，这是中国超级计算机得到国际同行认可的最好成绩。

并行计算-中国科学技术大学

w w 员工 w p p p ppp 经理 w w w
非集中模式
国家高性能计算中心（合肥）
2013-6-28
46
7.5 映射
7.5.1 方法描述 7.5.2 负载平衡算法 7.5.3 任务调度算法 7.5.4 映射判据
映射判据
采用集中式负载平衡方案，是否存在通讯瓶颈？采用动态负载平衡方案，调度策略的成本如何？
7.5 映射
7.5.1 方法描述 7.5.2 负载平衡算法 7.5.3 任务调度算法 7.5.4 映射判据
方法描述
每个任务要映射到具体的处理器，定位到运行机器上；任务数大于处理器数时，存在负载平衡和任务调度问题；映射的目标：减少算法的执行时间
并发的任务不同的处理器任务之间存在高通讯的同一处理器
组合判据
增加粒度是否减少了通讯成本？重复计算是否已权衡了其得益？是否保持了灵活性和可扩放性？组合的任务数是否与问题尺寸成比例? 是否保持了类似的计算和通讯？有没有减少并行执行的机会？
国家高性能计算中心（合肥）
2013-6-28
39
第七章并行算法的一般设计过程
7.1 PCAM设计方法学 7.2 划分 7.3 通讯 7.4 组合 7.5 映射 7.6 小结
划分方法描述
充分开拓算法的并发性和可扩放性；先进行数据分解(称域分解)，再进行计算功能的分解(称功能分解)；使数据集和计算集互不相交；划分阶段忽略处理器数目和目标机器的体系结构；能分为两类划分：
域分解(domain decomposition) 功能分解(functional decomposition)
国家高性能计算中心（合肥）

并行计算习题(全)

第二章习题例题：
1.
当代并行计算机系统介绍
请尽可能访问以下有关高性能并行计算的网址： IEEE/CS ParaScope (/parascope/)，world-wide parallel computing sites High Performance Computing Lists (/homes/mcbryan/public_html/bb/2/summary.html) The Language List (http://cuiwww.unige.ch/langlist) enumerate programming languages TOP 500 (/benchmark/top500.html) World's TOP 500 most powerful computing sites (at Netlib，University of Tennessee) Myrinet () DSM bibliography (http://www.cs.ualberta.ca/~rasit/dsmbiblio.html) Berkeley Active Message page (/AM/active_messages.html) The Cray Research system page (/products/systems/) SGI/Cray Origin 2000 (/Products/hardware/servers/index.html) Cray T3E (/products/systems/crayt3e/) PetaFLOPS web site (/hpcc/) NASA HPCC Program (/hpcc/) Cray T3E (/products/systems/crayt3e/) IBM SP (/hardware/largescale/) Intel Paragon (/Services/ Consult/Paragon/paragon.html) Kai Li (/~li/) SP2 at MHPCC (/doc/SP2.general/SP2.general.html) MPI Standard site (/mpi/index.html) MIT Parallel and Distributed Operating Systems Group (/). National Center for Supercomputer Applications at UIUC (NCSA) (/) Cornell Theory Center (CTC) (/ctc.html) Argonne Natl Laboratory，Mathematics & Computer Science Div. (/) Army Research Lab (/) Lawrence Livermore National Laboratory (/comp/comp.html) Los Alamos Natl Laboratory (LANL) Advanced Computing Laboratory (/). Maui High Performance Computing Center (MHPCC) (/mhpcc.html) San Diego Supercomputer Center (/SDSCHome.html) Sandia National Laboratories (/) Massively Parallel Comp. Res. Lab. Parallel Processing in Japan (/papers/ppij.html) Cray Research (/) IBM High-Performance Computing (/) ParaSoft Corporation (/)

并行计算第一章课后习题

第一章1.通过对本章所讲内容的理解，结合自身的认识论述学习并行计算及编程的重要性及意义.并行计算及编程是计算机专业本科生核心专业提升课程。

并行计算可以提高计算机的性能。

越来越多的研究和应用领域将需要使用并行计算技术，并行计算技术将对传统计算技术产生革命性的影响2.通过访问超级计算TOP500网站，了解最新的世界超级计算机排名，列出排名前10的超级计算机系统及其基本配置参数，试述你对超级计算机作用、意义的理解和认识.2019年11月①Summit;处理器：2,397,824 个；峰值速度：200795 TFlop/s②Sierra;处理器：1,572,480 个；峰值速度：125,712 TFlop/s③神威太湖之光；处理器：10,649,600 个；峰值速度： 125,436 TFlop/s④TH-2天河二号；处理器：4,981,760个；峰值速度：100,679 TFlop/s⑤Frontera；处理器：448,448 个；峰值速度：38746 TFlop/s⑥Piz Daint 代恩特峰；处理器：387,872 个；峰值速度：27154 TFlop/s⑦Trinity三一；处理器：979,968 个；峰值速度：41,461 TFlop/s⑧ABCI；处理器：391,680 个；峰值速度：32,576 TFlop/s⑨SuperMUC-NG；处理器：305,856个；峰值速度：26873 TFlop/s⑩Lassen;处理器：288,288 个；峰值速度：23047 TFlop/s 超级计算机：能够执行一般个人电脑无法处理的大资料量与高速运算的电脑。

其基本组成组件与个人电脑的概念无太大差异，但规格与性能则强大许多，是一种超大型电子计算机。

具有很强的计算和处理数据的能力，主要特点表现为高速度和大容量，配有多种外部和外围设备及丰富的、高功能的软件系统；超级计算机是计算机中功能最强、运算速度最快、存储容量最大的一类计算机，多用于国家高科技领域和尖端技术研究，是一个国家科研实力的体现，它对国家安全，经济和社会发展具有举足轻重的意义，是国家科技发展水平和综合国力的重要标志。

中科大计算机考研真题

中科大计算机考研真题中科大计算机考研是众多计算机科学与技术专业学生追求的目标之一。

在这道真题中，我们将回顾一些历年的考题，并提供一些解析和思路，以帮助考生更好地准备考试。

本文共分为三个主题部分：操作系统、数据库和算法与数据结构。

一、操作系统1. 多道批处理系统是怎样实现作业调度的？请简要描述操作系统的作业调度过程。

解析：多道批处理系统是指一台计算机同时处理多个作业，而不需要人工干预。

作业调度是指操作系统根据一定的算法，决定当前执行哪个作业。

作业调度过程一般包括以下几个步骤：首先，操作系统根据作业的优先级和提交时间等信息，为每个作业分配一个初始的调度优先级。

其次，对于多个处于就绪状态的作业，操作系统根据调度算法，选择一个作业进行执行。

常见的调度算法有先来先服务（FCFS）、短作业优先（SJF）、最高响应比优先（HRRN）等。

最后，当一个作业执行完成或者处于阻塞状态时，操作系统会根据调度算法重新选择一个作业进行执行，直到所有作业完成。

2. 请解释死锁的概念，并说明死锁的产生条件和解决方法。

解析：死锁是指多个进程在竞争有限资源时，由于彼此之间的互斥和请求资源的非预期顺序等原因，导致都在等待对方释放资源，从而导致系统无法继续执行。

死锁的产生条件主要包括：互斥条件：进程对所请求的资源进行排他性控制，即一次只能有一个进程使用该资源。

持有和等待条件：进程已经持有了一个资源，但又请求额外的资源，而这些资源又被其他进程所占有。

不剥夺条件：其他进程不能强行剥夺一个进程已经持有的资源，只能由进程自己释放。

环路等待条件：多个进程之间形成了一个循环等待资源的关系。

死锁的解决方法主要有以下几种：鸵鸟算法：忽略死锁的存在，不进行处理。

适用于死锁发生概率极低的系统。

死锁检测与恢复：通过系统资源分配图等方法，检测死锁的发生，并进行资源回收和进程终止等操作，使系统恢复正常状态。

死锁预防：通过破坏死锁产生的四个条件之一，预防死锁的发生。

南开大学20秋《并行程序设计》在线作业-1(参考答案)

1.SSE指令移动单精度浮点数，不能实现()。

A.将64位数据移动到SSE寄存器高位B.将64位数据移动到SSE寄存器低位C.将32位数据移动到SSE寄存器指定位置D.在两个SSE寄存器高/低64位间移动答案：C2.以下超级计算机中，()不是SIMD架构。

A.CDCSTAR-100B.757C.银河D.天河1号答案：D3.下列指令集中()不是SIMD指令集。

A.SSEB.NeonC.AVXD.EMT64答案：D4.SSE寄存器A和B中元素分别为A1 A2 A3 A4和B1 B2 B3 B4(均为由低到高)，则执行C=blend(A，B，0x05)后，C中元素为()。

A.A1 A2 B3 B4B.B1 B2 A3 A4C.A1 B2 A3 B4D.B1 A2 B3 A4答案：D5.以下哪条不是推动并行计算发展的因素?()A.存储是系统瓶颈B.单CPU发展已能满足应用需求C.利用标准硬件构造并行机令升级容易D.编程环境标准化逐步发展答案：B6.在使用互斥量之前必须对其进行()。

A.初始化B.加锁C.解锁D.销毁答案：A7.全球500强超算在CPU、网络等硬件上越来越体现出采用()的趋势。

A.特殊硬件B.通用硬件C.非公开硬件D.廉价硬件答案：B8.有大量分支指令的程序不适合下面哪种体系结构上进行并行化?()A.SISDB.SIMDC.SPMDD.MIMD答案：B9.Pthread不支持()。

A.创建并发执行线程B.同步C.非显式通信D.自动并行化答案：D10.在超市的顾客购买商品记录中统计一些商品组合的购买频率，将购买频率(商品组合)划分给不同进程，这是一种划分()的数据并行策略。

A.输入数据B.中间结果C.输出数据D.临时数据答案：C11.当处理器数量不变时，随着问题规模增大，加速比()。

A.所有算法都增大B.所有算法都减小C.代价最优算法都增大D.代价最优算法都减小答案：C12.两个矩阵相乘，若矩阵总规模小于cache大小，则优化访存的最佳方法是()。

并行计算的一体化研究现状与发展趋势

134 •电子技术与软件工程 Electronic Technology & Software Engineering 计算机技术应用 • the Application of Computer Technology【关键词】并行计算一体化研究发展趋势云计算我国计算科学的快速发展，使得计算科学研究领域以及与我国传统的理论科学研究领域，还有实验科学研究领域，成为了当今推动科技发展的重要三大科学领域。

而中国科技大学的技术团队所提出的并行计算在当今的科学领域发展过程当中属于研究工具，设计出来的研究工具现如今已经逐渐融入到传统的理论科学和实验科学的工作开展过程当中，并行计算一体化研究方法的诞生，推动了我国目前科学技术的快速发展，同样也为我国的科学技术在发展过程当中提供了更好的研究工具，研究方法，真正为我国科学技术发展领域提供了更好的发展平台。

1 并行计算概述及现状1.1 并行计算的概念并行计算从理论角度进行定义就是在并行计算机上进行计算，而与我国目前人们常说的高性能计算以及超级计算属于同种含义，而且我国现如今所应用的高性能计算和超级计算工作开展过程当中离不开并行技术的应用。

串行计算指的就是在单个计算机上面进行软件应用和操作读写，运用描写指令来进行问题解决。

而并行计算方法是根据串行计算理论基础与实践基础发展而来。

并行计算方式在进行问题计算过程当中拥有以下特征：（1）在计算任务开展过程当中，将计算任务分解成多个部分同时解决；（2）在同一时间范围内由不同的软件来执行不同的程序指令。

1.2 并行计算的一体化研究现状并行计算方法在应用过程当中涉及的内并行计算的一体化研究现状与发展趋势文/甘云志容十分广泛，在进行研究过程当中，研究内容包括以下几部分第一并行计算的硬件平台，第二部分则是并行程序整体设计，第三部分则为并行计算的理论基础应用，第四部分则是并行计算的具体使用情况。

我国的并行计算在发展过程当中由于长期缺乏人有方法导致我国现如今的并行计算在研究过程当中出现了参差不齐的格局，目前我国的并行计算再进研究过程中主要存在以下几个问题，并行算法不完善，并行应用效率低，无法充分利用计算机资源，并行编程语言难度较高，缺乏相应专业人才运用，并行计算机在进行构建和应用过程当中，能耗过大，管理困难。

1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

并行分布式试卷1
姓名____________________
学号____________________ 分数_____________
1．填空（每空1分，共30分）
1．在并行机系统中，常用的静态互联网络有__ ___________，__ _____________，_
_____________________，______________________，___________________等。

2．在并行机系统中，常用的动态互联网络有___________________________________，
_____________________________________和______________________________。

3．近代并行计算机体系结构模型包括_______ _________，___________________，_
______________________，____________ ______，_____________________等。

4．常用的并行存储访问模型（又叫并行存储结构）包括_______________________，
________________________________，_____________________________等。

5．常用的并行程序设计模型有____________ _______，__ _ _______________，___
_________________________等。

6．大型稀疏线性方程常用迭代解法有____________________，_ _________________，
_________________________，__________________________等。

7．常用的并行计算（或算法）模型有___________________，___ ________________
_，________________________，______________________等。

8．我国自行研制的并行计算机三大系列是___________________________，________
_____________________，_____________________________。

2．简要回答（每题5分，共20分）
1．试述并行算法基本的设计技术。

2．何谓X-Y 选路算法何E-cube 选路算法（可以例明之）?3．何谓Amdahle 和Gustfson 加速定律及其推导过程？
4．何谓等效率、等速度和平均延迟可扩放性度量标准？并推导他们之间的等效性。

三．综合题（每题10分，共50分）
1．假定44⨯A 和44⨯B 都已加载到44⨯处理器阵列上，试图示Cannon 矩阵乘法的具体
过程。

2．已知⎥⎦⎤⎢⎣⎡=4331A ，⎥⎦
⎤
⎢⎣⎡--=8765B ，试用DNS 方法，逐步求出矩阵乘积
?22211211
=⎥⎦
⎤
⎢
⎣⎡=c c c c C 。

3．欲求解Ax=b ，则构造二次函数b x Ax x x q T T -=2
1
)(，试证明
0)
(=∂∂x
x q 是Ax=b 的解。

4．假定∑-==
1
n k k jk
j a w
b ，10-≤≤n j ，以n=8为例，推导FFT 递归计算公式。

5．参照下图，对于一个8点的蝶式网络，假定：① 相应的处理器p(r, i)中已保存了倍
数矩阵元素),exp(i r w ，70≤≤i ，31≤≤r 。

② 输入序列)0,0,,1,0,1,,2(i i i A -=。

试按下述SIMD-BF 模型上算法，计算出i r d ,和j r d ,之值。

SIMD-BF 模型上的FFT 算法输入：),...,(10-=n a a A 输出：i r d ,和j r d ,Begin
(1)for i=0 to n-1 par-do
i
i a d =,0endfor
(2)for r=1 to n log do
for 所有仅第r 位不同且i 在第r 位为零的每对(i,j) par-do
(2.1) j
r i r i r i r d d d ,1)
,exp(,1,--+=ω
4
6
77
d 30
d 31
d 32
d 33
d 34
d 35
d 36
d 37
r 0
r 1
r 2r 3
(2.2) j
r j r i r j r d d d ,1)
,exp(,1,--+=ωendfor endfor
End
并行分布式试卷2
姓名____________________学号____________________ 分数_____________
1、填空选择题(20分)
1.对于高性能计算的需要是广泛的，比如在__ ___________，__ _________
____，______________________，______________________等领域中应用广泛。

2. 在并行系统中，系统互联网络有___________________________________，
_______________________________和______________________________三类。

3. 近代常见的五种并行计算机体系结构模型包括_______ _________，____
_______________，_______________________，____________ ______，__ ___________________。

4.常用的并行计算模型有____________ _______，__ _ _______________，
____________________________，__ _ ______________等。

5．中国工程院院士金怡濂研究员被授予2002年度国家最高科学技术奖。

由他担任总设计师主持研制的并行计算机系统为 _________ 系列。

A. 曙光 B 神威 C. 银河 D 以上都不对
6．关于加速比，下面的论述不对的是_________
A. 严格的线性加速比是难以达到的；
B. 在某些算法或程序中，可能出现超线性加速现象；
C. 通信密集类的应用问题，加速比往往不是很高
D. 加速比仅由算法决定，与应用问题的规模无关
2、简答题（20分）
1．何谓SMP结构？简述该结构的特性。

2．试推导Gustafson定律。

3．何谓并行计算的可扩放性？有哪三种典型的扩放性度量方法？
4．何谓PRAM模型？简述该模型的优缺点。

5．请举例说明并行算法的三种一般设计方法（策略）。

3、综合题（60分）
1.试画出基于Batcher比较器的双调序列(8，6，4，2，0，1，3，5)的双调归
并排序网络，并在标出每个Batcher比较器的输入和输出数据。

2.使用指针跳跃技术求出下面森林的根，给出求解过程。

9
3.给出环上一到多(one-to-all)的CT 选路算法描述，并在下图中画出选路步骤。

根据单一信包的通讯时间h w s one to one lt mt t CT t ++=--)(，试推导环上的通讯时
间)(CT t all to one --。

4.先写出矩阵乘法n n n n B A ⨯⨯⨯的Fox 算法形式描述，然后分析Fox 算法在p 个处理器组成的超立方上、使用CT 选路的运行时间(注：p -超立方上的p mt t CT t w s all to one log )()(+=-- )。

5.离散富里叶变换∑-==1
0n k kj
k j a b ω，10-≤≤n j 。

对于n =8，试完成下面的蝶式
计算图中的列1到列3的相应标记，并求出b 3和b 6。