并行计算(陈国良版)课后答案

并行计算期末试题及答案1. 基础概念部分并行计算是一种计算模式，它使用多个处理单元同时执行计算操作，以加快计算速度。

在现代计算机系统中，我们常常使用多核处理器、图形处理器（GPU）或者分布式系统来实现并行计算。

1.1 并行计算的优势并行计算具有以下几个优势：加速计算速度：通过同时执行多个计算任务，可以极大地提高计算效率。

解决大规模问题：并行计算可以处理大规模和复杂的问题，提供更精确的结果。

降低能耗：通过合理利用处理器资源，可以降低计算任务的能耗。

应用广泛：并行计算可以应用于各个领域，如科学计算、大数据分析、机器学习等。

1.2 并行计算的分类并行计算按照任务之间的关系可以分为两类：数据并行：将数据划分为多个子集，同时在不同的处理器上进行计算，然后将计算结果汇总。

常见的应用包括矩阵运算、图像处理等。

任务并行：将任务划分为多个子任务，每个子任务由一个独立的处理器执行，最后将各个子任务的结果合并。

常见的应用包括并行搜索算法、并行排序等。

2. 并行计算的算法设计2.1 并行算法设计要点在设计并行算法时，需要考虑以下几个要点：任务划分：将计算任务划分为多个子任务，确保各个子任务之间的计算工作均衡，并保持任务之间的独立性。

任务调度：合理安排各个处理器上的任务执行顺序和时间，最大程度地减少通信开销和等待时间。

数据通信：处理器之间需要进行数据交换和通信，应选择合适的通信方式，并考虑通信延迟和带宽等因素。

数据同步：在多个处理器之间，可能需要进行数据同步操作，确保各个处理器之间的数据一致性。

2.2 并行算法实例：并行矩阵乘法并行矩阵乘法是一个常见的数据并行算法，可以有效地利用多核处理器加速大规模矩阵运算。

具体算法如下：步骤1：将输入矩阵划分为若干个小矩阵，每个小矩阵分配给一个处理器。

步骤2：每个处理器计算相应小矩阵的部分结果。

步骤3：将各个处理器计算得到的部分结果进行求和，得到最终的矩阵乘积结果。

3. 并行计算的应用举例3.1 科学计算在科学计算领域，有大量的计算任务需要处理大规模的数据和复杂的数学模型。

并行计算习题答案并行计算习题答案在计算机科学领域，随着技术的不断发展，计算速度的提升成为了一个重要的课题。

并行计算作为一种有效的解决方案，被广泛应用于各个领域。

本文将通过回答一些并行计算习题，来探讨并行计算的原理和应用。

1. 什么是并行计算？并行计算是指同时执行多个计算任务的一种计算模式。

它通过将一个大问题分解为多个小问题，并在多个处理单元上同时执行这些小问题，从而加快计算速度。

并行计算可以应用于各种领域，包括科学计算、图像处理、人工智能等。

2. 并行计算的优势是什么？并行计算具有以下几个优势：- 加速计算速度：通过同时执行多个任务，可以大大提高计算速度，从而节省时间和资源。

- 处理大规模问题：并行计算可以处理大规模问题，将问题分解为多个小问题，分别在不同处理单元上计算，从而提高计算效率。

- 提高系统可靠性：并行计算中的多个处理单元可以相互协作，当一个处理单元发生故障时，其他处理单元可以继续工作，从而提高系统的可靠性。

3. 并行计算的模型有哪些？并行计算的模型有多种，常见的包括：- SIMD（单指令流多数据流）模型：所有处理单元执行相同的指令，但可以处理不同的数据。

- MIMD（多指令流多数据流）模型：每个处理单元可以执行不同的指令，处理不同的数据。

- SPMD（单程序多数据流）模型：所有处理单元执行相同的程序，但可以处理不同的数据。

4. 并行计算中的通信方式有哪些？并行计算中的通信方式包括：- 共享内存：多个处理单元共享同一块物理内存，通过读写内存来实现数据的传递和共享。

- 消息传递：处理单元之间通过发送和接收消息来进行通信，可以通过直接通信或者通过中间件来实现。

5. 如何评估并行计算的性能？评估并行计算的性能可以从以下几个方面考虑：- 加速比：加速比是指并行计算相对于串行计算的速度提升比例，可以通过计算并行计算时间与串行计算时间的比值得到。

- 效率：效率是指并行计算的实际加速比与理论加速比之间的比值，可以反映并行计算的利用率。

第一章绪论1.1 什么是并行计算机？答：简单地讲，并行计算机就是由多个处理单元组成的计算机系统，这些处理单元相互通信和协作，能快速高效求解大型的复杂的问题。

1.2 简述Flynn分类法：答：根据指令流和数据流的多重性将计算机分为：1）单指令单数据流SISD2）单指令多数据流SIMD3）多指令单数据流MISD4）多指令多数据流MIMD1.3 简述当代的并行机系统答：当代并行机系统主要有：1）并行向量机（PVP）2）对称多处理机（SMP）3）大规模并行处理机（MPP）4）分布式共享存储（DSM）处理机5）工作站机群（COW）1.4 为什么需要并行计算机？答：1）加快计算速度2）提高计算精度3）满足快速时效要求4）进行无法替代的模拟计算1.5 简述处理器并行度的发展趋势答：1）位级并行2）指令级并行3）线程级并行1.6 简述SIMD阵列机的特点答：1）它是使用资源重复的方法来开拓计算问题空间的并行性。

2）所有的处理单元（PE）必须是同步的。

3）阵列机的研究必须与并行算法紧密结合，这样才能提高效率。

4）阵列机是一种专用的计算机，用于处理一些专门的问题。

1.7 简述多计算机系统的演变答：分为三个阶段：1）1983-1987年为第一代，代表机器有：Ipsc/1、Ameteks/14等。

2）1988-1992年为第二代，代表机器有：Paragon、Intel delta等。

3）1993-1997年为第三代，代表机器有：MIT的J-machine。

1.8 简述并行计算机的访存模型答：1）均匀存储访问模型（UMA）2）非均匀存储访问模型（NUMA）3）全高速缓存存储访问模型（COMA）4）高速缓存一致性非均匀访问模型（CC-NUMA）1.9 简述均匀存储访问模型的特点答：1）物理存储器被所有处理器均匀共享。

2）所有处理器访问任何存储字的时间相同。

3）每台处理器可带私有高速缓存。

4）外围设备也可以一定的形式共享。

1.10简述非均匀存储访问模型的特点答：1）被共享的存储器在物理上分布在所有的处理器中，其所有的本地存储器的集合构成了全局的地址空间。

并行计算课程的教学方法
陈国良;孙广中;徐云;吴俊敏
【期刊名称】《中国大学教学》
【年(卷),期】2004(000)002
【摘要】教育部高等学校计算机科学与技术教学指导委员会，曾于1998年将并行计算课程定位在高等学校计算机专业高年级本科生或研究生以及面向计算学科的非计算机专业的研究生层次上。

设置该课程的宗旨是为了我国培养面向21世纪的厚基础、宽口径、强能力、高素质具有时代性多样化人才的需要。

为此在编写此课程的教材时着重强调专业知识的宽广和内容的先进。

【总页数】3页(P35-37)
【作者】陈国良;孙广中;徐云;吴俊敏
【作者单位】中国科学技术大学;中国科学技术大学;中国科学技术大学;中国科学技术大学
【正文语种】中文
【中图分类】G64
【相关文献】
1.变革高中历史教学方法适应新课程改革要求——浅谈在新课程下高中历史教学方法的改革与创新
2.变革高中历史教学方法适应新课程改革要求——浅谈在新课程下高中历史教学方法的改革与创新
3.以国家精品课程建设推动教学方法改革--国家精品课程＂天气学＂教学方法探索实践
4.“并行计算”课程中课程思政教育研究与实践
5.多核时代"并行计算"课程教学模式研究与实践
因版权原因，仅展示原文概要，查看原文内容请购买。

计算机学院研究生《并行计算》课程考试试题（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)有id C 个节点与s 的距离为i 。

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

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

设节点u 表示为：121D .........j j i j i d D D D D D +-+，节点v 表示为：''121D .........j j i j i dD D D D D +-+，则现在就是要求得从121D .........j j i j i d D D D D D +-+变换到''121D .........j j i j i d D D D D D +-+ 的途径有多少种。

那么利用组合理论知识可知共有*(1)*(2)*...*2*1i i i --即!i 中途径。

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

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

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

对其中的每个程序，选出最适合描述其在16个处理器上性能的陈述。

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

b ） 由于程序中的串行程序比例很大，在16个处理器上的加速比不会比8个处理器上的加速比高出40%。

并行计算——结构.算法.编程 陈国良（第3版）2.1 对于一颗K 级二叉树（根为0级，叶为k-1级），共有N=2^k-1个节点，当推广至m-元树时（即每个非叶节点有m 个子节点）时，试写出总节点数N 的表达式。

答：推广至M 元树时，k 级M 元树总结点数N 的表达式为：N=1+m 1+m 2+...+m （k-1）=(1-m k )*1/(1-m);4.11 一个在p 个处理器上运行的并行程序加速比是p-1，根据Amdahl 定律，串行分量为多少?答：p/(1+f(p-1))=p-1, f=1/(p-1)25.5假定开始时P i (1《i 《n)存有数据 d i ，所谓累加求和是指用∑=i j i d 1，来代替中的原始值d i ，算法5.3给出了在PRAM 模型上累加求和算法。

Input: di are kept in Pi, whereOutput: replaces di in processor PiBeginfor j=0 to logn-1 dofor i=2j +1 to n par-do(i) di= d i + d i –2j(ii) Pi=diend forend forEnd(1）试用n=8为例子，按照上述算法逐步计算出累加和。

(2）分析算法的时间复杂度。

6.333215413 33 8240 727.2（1）例:A={1,3,6,8,11,13} p=6;B={2,4,5,7,10,12,14} ,q=7p=3, q=3A={1,3,6*,8,11,13*}B={2,4,5*,7,10 ,12*,14},B’={2,4,5,6*,7,10 12,13*,14}A11={1,3} , A12={8,11} , A13={} B11={2,4,5} , B12={7,10 12} , B13={14} A11={1,3*} , A12={8,11*} ,B11={2,4*,5} , B12={7,10* , 12} ,B11’={2, 3* , 4,5} , B12’={7,10 , 11* , 12} ,A111={1},A112={} A121={8},A122={}B111={2},B112={4,5} B121={7,10 },B122={12}A111={1 *} A121={8 *}B111={2 *} B121={7,10 * }B111’={1 *,2 } B121’={7, 8 *,10 }A1111={}, A1112={} A1211={}, A1212={}B1111={}, B1111={} B1211={7}, A1212={}6.7（1）pat = abaababa(m = 8)WIT[1] = 0，WIT[2] = 1，w=1,j=2,s=2-1+1=2 pat[w] = a pat[s]=bWIT[3] = 2，w=1,j=3,s=3-1+1=3 pat[w] = pat[s]=aw=2,j=3,s=3-1+2=4 pat[w] = b pat[s]=aWIT[4] = 4 w=1,j=4,s=4-1+1=4 pat[w] = pat[s]=aw=2,j=4,s=4-1+2=5 pat[w] = pat[s]=bw=3,j=4,s=4-1+3=6 pat[w] = pat[s]=aw=4,j=4,s=4-1+4=7 pat[w] = a pat[s]=b 为非周期串6.8 (2)p=6,q=9j=q-p+1=9-6+1=4w=wit[j]=wit[4]=4T(q+w-1)=t(9+4-1)=b<>P(4)=awit[q]= wit[9]=w=4duel=p=6。

并⾏计算题⽬答案汇总第１题（1）什么是并⾏计算？（2）它的优点有哪些？（3）可以通过哪些结构完成并⾏计算？1．并⾏计算就是在并⾏计算或分布式计算机等⾼性能计算系统上所做的超级计算。

（P3）2．计算极⼤地增强了⼈们从事科学研究的能⼒，⼤⼤地加速了把科技转化为⽣产⼒的过程，深刻地改变着⼈类认识世界和改造世界的⽅法和途径。

计算科学的理论和⽅法，作为新的研究⼿段和新的设计与创造技术的理论基础，正推动着当代科学与技术向纵深发展。

（P4）3．单指令多数据流SIMD、对称多处理机SMP、⼤规模并⾏处理机MPP、⼯作站机群COW、分布共享存储DSM多处理机。

（P22）第2题什么是⽹络计算？它的特点？它与分布式计算、集群计算的关系？（P104）⽹络计算：在⼯作站机群COW环境下进⾏的计算称为⽹络计算。

特点：⽹络计算结合了客户机/服务器结构的健壮性、Internet⾯向全球的简易通⽤的数据访问⽅式和分布式对象的灵活性，提供了统⼀的跨平台开发环境，基于开放的和事实上的标准，把应⽤和数据的复杂性从桌⾯转移到智能化的⽹络和基于⽹络的服务器，给⽤户提供了对应⽤和信息的通⽤、快速的访问⽅式。

与分布式计算、集群计算的关系：分布式计算是⼀门计算机科学，它研究如何把⼀个需要⾮常巨⼤的计算能⼒才能解决的问题分成许多⼩的部分，然后把这些部分分配给许多计算机进⾏处理，最后把这些计算结果综合起来得到最终的结果。

集群计算是使⽤多个计算机，如典型的个⼈计算机或UNIX⼯作站；多个存储设备；冗余互联，来组成⼀个对⽤户来说单⼀的⾼可⽤性的系统。

因此，⽹络计算与分布式计算和集群计算都是属于计算密集型，数据密集型和⽹络密集型应⽤。

第3题表征并⾏系统的性能指标有哪些？并⾏系统的加速⽐如何定义？它能否完全确定系统的性能？为什么？a.表征并⾏系统的性能指标主要有：CPU和存储器的基本性能指标，通信开销以及系统机器的成本、价格与性价⽐，还有系统加速⽐和系统可扩放性（p88页3.3）；其中CPU和存储器的基本性能指标包括：⼯作负载，并⾏执⾏时间，存储器的层次结构和存储器的带宽。

第十二章 并行程序设计基础习题例题：1、假定有n 个进程P(0)，P(1)，…，P(n -1)，数组元素][i a 开始时被分配给进程P(i )。

试写出求归约和]1[]1[]0[-+++n a a a 的代码段，并以8=n 示例之。

2、假定某公司在银行中有三个账户X 、Y 和Z ，它们可以由公司的任何雇员随意访问。

雇员们对银行的存、取和转帐等事务处理的代码段可描述如下：/*从账户X 支取￥100元*/atomic {if (balance[X] > 100) balance[X] = balance[X]-100； }/*从账户Y 存入￥100元*/atomic {balance[Y] = balance[Y]-100；}/*从账户X 中转￥100元到帐号Z*/atomic {if (balance[X] > 100){balance[X] = balance[X]-100；balance[Z] = balance[Z]+100；} }其中，atomic {}为子原子操作。

试解释为什么雇员们在任何时候（同时）支、取、转帐时，这些事务操作总是安全有效的。

3、考虑如下使用lock 和unlock 的并行代码：parfor (i = 0；i < n ；i++){noncritical sectionlock(S)；critical sectionunlock(S)；}假定非临界区操作取T ncs时间，临界区操作取T cs时间，加锁取t lock时间，而去锁时间可忽略。

则相应的串行程序需n( T ncs + T cs )时间。

试问：①总的并行执行时间是多少？②使用n个处理器时加速多大？③你能忽略开销吗？4、计算两整数数组之内积的串行代码如下：Sum = 0；for(i = 0；i < N；i++)Sum = Sum + A[i]*B[i]；试用①相并行；②分治并行；③流水线并行；④主-从行并行；⑤工作池并行等五种并行编程风范，写出如上计算内积的并行代码段。

例题习题讲解例1 SIMD-SM上求最大值算法Beginfor k=m-1 to 0 dofor j=2k to 2k+1-1 par-doA[j]=max{A[2j], A[2j+1]}end forend forend时间分析t(n)=m×O(1)=O(logn)p(n)=n/2c(n)=O(nlogn) 非成本最优例2 令n=2k(k>=0)，求n个数和的并行算法算法运行时间：t(n)=O(logn)总运算量: W(n)=W(1)(n)+W(2)(n)+W(3)(n)=n+∑n/2h+1=O(n)由Brent定理知: t(n)=O(n/p+logn)例3 设A为矩阵，有如下串行程序段：f o r i=1t o n d of o r j=1t o n d oa[3i,2j]=a[3i-2,2j-1]e n df o re n df o r其相关方向向量为，可知行和列间同时存在数据相关。

在此我们可以试用行划分、列划分和方块划分.在行划分的情况下令m=┌n/p┐,例1的串行程序段可以转化为如下的并行程序段：f o r k=1t o P P a r-d of o r i1=1t o m d of o r j=1t o n d oa[3(k-1)m+3i1,2j]=a[3(k-1)m+3i1-2,2j-1]e n df o re n df o re n df o r例4 设A为一个n阶方阵，有如下串行程序段：f o r i=1t o n d of o r j=1t o n d oa[i,j]=a[i-1,j]e n df o re n df o r分析矩阵A的元素下标i和j，则i和j的相关方向向量为，各列之间数据无任何相关关系。

因此对矩阵A可按列划分。

串行程序段可转化为如下并行程序段：f o r k=1t o P P a r-d of o r j1=1t o m d of o r i=1t o n d oa[i,(k-1)m+j1]=a[i-1,(k-1)m+j1] e n d f o re n df o re n df o r例5注：本例无链路竞争和死锁现象例6 E立方选路0110(S)1101(D)1011(R)例7 DNS乘法示例C00=1×(-5)+2×7=9C01=1×(-6)+2×8=10C10=3×(-5)+4×7=13C11=3×(-6)+4×8=14例8 上三角方程组的回代解法并行化(1)SISD上的回代算法Begin(1)for i=n downto 1 do(1.1)x i=b i/a ii(1.2)for j=1 to i-1 dob j=b j-a ji x ia ji=0endforendforEnd(2)SIMD-CREW上的并行回代算法- 划分: p个处理器行循环带状划分- 算法Beginfor i=n downto 1 dox i=b i/a iifor all P j, where 1≤j≤p do for k=j to i-1 step p do b k=b k-a ki x ia ki=0endforendforendforEnd // p(n)=n, t(n)=n例9 n=8的BF网络表示P r,i与上层P r-1,i, P r-1,j相连, 这里j与i仅在第r位不同例10 一个在MPI中创建新通信域的例子M P I_C o m m M y W o r l d,S p l i t W o r l d;i n t m y_r a n k,g r o u p_s i z e,C o l o r,K e y;M P I_I n i t(&a r g c,&a r g v);M P I_C o m m_d u p(M P I_C O M M_W O R L D,&M y W o r l d);M P I_C o m m_r a n k(M y W o r l d,&m y_r a n k);M P I_C o m m_s i z e(M y W o r l d,&g r o u p_s i z e);C o l o r=m y_r a n k%3;K e y=m y_r a n k/3;M P I_C o m m_s p l i t(M y W o r l d,C o l o r,K e y,&S p l i t W o r l d);例11 考虑如下程序段：L1:f o r I=1t o50d o...S:X(2*I)=......T:...=...X(3*I+1)......e n df o r这里：f1(I)=2*I；g1(J)=3*J+1。

第三章 互连网络3.1 对于一颗K 级二叉树（根为0级，叶为k-1级）,共有N=2^k —1个节点，当推广至m —元树时（即每个非叶节点有m 个子节点)时,试写出总节点数N 的表达式。

答:推广至M 元树时，k 级M 元树总结点数N 的表达式为：N=1+m^1+m^2+。

.。

+m^（k —1）=(1—m^k)*1/(1-m);3.2二元胖树如图3.46所示，此时所有非根节点均有2个父节点.如果将图中的每个椭圆均视为单个节点，并且成对节点间的多条边视为一条边，则他实际上就是一个二叉树。

试问：如果不管椭圆，只把小方块视为节点，则他从叶到根形成什么样的多级互联网络？ 答：8输入的完全混洗三级互联网络.3.3 四元胖树如图3.47所示，试问：每个内节点有几个子节点和几个父节点?你知道那个机器使用了此种形式的胖树？答:每个内节点有4个子节点，2个父节点。

CM —5使用了此类胖树结构.3.4 试构造一个N=64的立方环网络,并将其直径和节点度与N=64的超立方比较之,你的结论是什么?答：A N=64的立方环网络,为4立方环（将4维超立方每个顶点以4面体替代得到），直径d=9，节点度n=4B N=64的超立方网络,为六维超立方(将一个立方体分为8个小立方，以每个小立方作为简单立方体的节点，互联成6维超立方)，直径d=6，节点度n=63.5 一个N=2^k 个节点的 de Bruijin 网络如图3。

48。

个节点的二进制表示，。

试问:该网络的直径和对剖宽度是多少？答：N=2^k 个节点的 de Bruijin 网络 直径d=k 对剖宽带w=2^(k-1）3.6 一个N=2^n 个节点的洗牌交换网络如图3.49所示.试问：此网络节点度==?网络直径==？网络对剖宽度==？答：N=2^n 个节点的洗牌交换网络,网络节点度为=2 ，网络直径=n —1 ,网络对剖宽度=43.7 一个N=（k+1)2^k 个节点的蝶形网络如图3.50所示.试问:此网络节点度=？网络直径=?网络对剖宽度=?答：N=（k+1）2^k 个节点的蝶形网络,网络节点度=4 ，网络直径=2＊k ，网络对剖宽度=2^k3。

第一章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 超级计算机：能够执行一般个人电脑无法处理的大资料量与高速运算的电脑。

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

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

第三章互连网络3.1 对于一颗K级二叉树（根为0级，叶为k-1级），共有N=2^k-1个节点，当推广至m-元树时（即每个非叶节点有m个子节点）时，试写出总节点数N的表达式。

答：推广至M元树时，k级M元树总结点数N的表达式为：N=1+m^1+m^2+...+m^（k-1）=(1-m^k)*1/(1-m);3.2二元胖树如图3.46所示，此时所有非根节点均有2个父节点。

如果将图中的每个椭圆均视为单个节点，并且成对节点间的多条边视为一条边，则他实际上就是一个二叉树。

试问：如果不管椭圆，只把小方块视为节点，则他从叶到根形成什么样的多级互联网络？答：8输入的完全混洗三级互联网络。

3.3 四元胖树如图3.47所示，试问：每个内节点有几个子节点和几个父节点？你知道那个机器使用了此种形式的胖树？答：每个内节点有4个子节点，2个父节点。

CM-5使用了此类胖树结构。

3.4 试构造一个N=64的立方环网络，并将其直径和节点度与N=64的超立方比较之，你的结论是什么？答：A N=64的立方环网络,为4立方环（将4维超立方每个顶点以4面体替代得到），直径d=9，节点度n=4B N=64的超立方网络，为六维超立方（将一个立方体分为8个小立方，以每个小立方作为简单立方体的节点，互联成6维超立方），直径d=6，节点度n=63.5 一个N=2^k个节点的de Bruijin 网络如图3.48。

试问：该网络的直径和对剖宽度是多少？答：N=2^k个节点的de Bruijin网络直径d=k 对剖宽带w=2^(k-1)3.6 一个N=2^n个节点的洗牌交换网络如图3.49所示。

试问：此网络节点度==？网络直径==？网络对剖宽度==？答：N=2^n个节点的洗牌交换网络，网络节点度为=2 ，网络直径=n-1 ，网络对剖宽度=43.7 一个N=（k+1）2^k个节点的蝶形网络如图3.50所示。

试问：此网络节点度=？网络直径=？网络对剖宽度=？答：N=（k+1）2^k个节点的蝶形网络，网络节点度=4 ，网络直径=2*k ，网络对剖宽度=2^k3.9 对于如下列举的网络技术，用体系结构描述，速率范围，电缆长度等填充下表中的各项。

分布式系统笫一章分布式系统概述1・一个有256个CPU的多计算机系统被组织成16X16的网格。

在最坏的情况尺-•条消息的传输延迟为多少？(以跳为单位) 假定路由是最优的.那么最长的优化(理想)路径是从网格的一・角到相对的•角，即沿着对角线的路径。

这个路径的长度是3()跳。

如果在单行或单列上的终端处理器是互联起來的，那么路径长度变成15^2・考虑一256个CPU的超立方休.在最坏的情况下，一个消息延迟是多少？(以跳为单位)对于256个CPU的超立方体，每个节点有一个二进制地址.范围从OOOOOO(M)到11111111•从一个机器到另一个的一•跳，耍改变二进制地址中的一位,因此地址从00000000变到00000001就是一跳,从00000001到0(X)00011又是另外一跳。

因此总共需耍八跳。

3・一个冬计算机系统有4096个50-MIPS的CPU,通过omega网络连接到内存。

为了使一个内存请求能在-•条指令的时间内到达内存并返回结果.转换的速度需要有影快？5O-MIPS=5纳秒.需耍【(4096的对数)=12】层开关.就有这么卷延迟•因为有来回.所以乘以2.转换速度就是5/24=0.208纳秒。

4 •一台试验文件服务器由于错误的原因.3/4的时间正常工作,1/4的时间由于故障停止工作。

为了达到99%的可用性，这一文件服务誥需耍复制多少次？设k是服务器的数则由题意知(l/4)k<0.01・这是最坏的情况.即所有的服务器都出故障的时间至名为1%的时间的情况。

这k = 4。

5 •假设有一个包含m个待编详文件的大源程序。

这个编译工作将在一个拥有！1个处理器的系统上进行.其中：n»m。

希望这种方法的速度嚴好达到单处理器的m倍。

哪些因素导致实际的速度达不到该值？答：可能由于总线容量限制从而引起总线过载，或者交换开关延时。

6・举例说明名核并行计算机的结构和性能计算方法。

(网上找的答案.参考)多核并行计算机的结构多核即在一・个单芯片上而集成两个捷至更多个处理器内核.其中每个内核都有自己的逻辑单元.控制单元.中断处理器、运算单元, -级cache.二级cache共享或独有.其部件的完整性和单核处理器内核相比完全一•致。

1.并行算法设计主要有哪些方法，各种方法的特点是什么？①串行程序的直接并行化：检查和开拓现有串行算法中固有的并行性，直接将其并行化。

一个显著优点是：算法的稳定性，收敛性等问题在串行算法中已有结论②从问题描述开始设计并行算法：从问题本身的描述出发，从头设计一个全新的并行算法③借用已有的算法求解新问题：借助已有的并行算法求解新问题，方法描述：找出求解问题和某个已解决问题之间的联系；改造或利用已知算法应用到求解问题上。

2.并行算法的设计过程主要分为哪几个阶段，各阶段主要完成什么工作，各阶段之间的有什么关系？设计过程分为四步：任务划分(Partitioning 划分) 、通信分析(Communication 通信) 、任务组合(Agglomeration 组合) 、处理器映射(Mapping 映射)。

各阶段的任务：划分：将计算任务分解成小任务，以尽量开拓并行执行的可能性；通信：确定小任务需要进行的通信，为组合做准备；组合：将一些小任务组合成大任务以减少通信开销；映射：将组合后的任务分配到处理器上，其目标是使总执行时间和通信开销尽量小，使处理器的利用率尽量高3.并行算法设计技术要有哪些？并说明各种技术主要的设计思想划分设计技术、分治设计技术、平衡树设计技术、倍增设计技术、流水线设计技术、破对称技术划分设计技术：划分技术的基本出发点是有效利用空闲处理器、大问题求解需要提高求解速度。

具体划分方法包括均匀划分、平方根划分、对数划分、功能划分等。

分治技术：分治技术是一种问题求解的方法学，其思想是将原来的大问题分解成若干个特性相同的子问题分而治之。

流水线技术：设计思想是将算法流程划分成p个前后衔接的任务片断，每个任务片断的输出作为下一个任务片断的输人;所有任务片断按同样的速率产生出结果。

倍增技术：又称指针跳跃技术，适用于处理以链表或树之类表示的数据结构。

每当递归调用时，要处理的数据之间的距离将逐步加倍，经过k步后就可完成距离为2*的所有数据的计算。

教学大纲课程名称：并行计算预修课程：计算机体系结构、数据结构等开课学期：总学时：60学分：大纲撰写人：陈国良、徐云、孙广中一、教学目标及要求本课程是为计算机科学与技术专业的高年级本科生开设的专业课，也可作为面向科学和工程计算的非计算机专业的高年级本科生和研究生的选修课程。

通过此课程的学习，可使学生了解和掌握计算机学科中以及大型科学与工程问题中的基本的并行与分布计算方法及其软硬基础。

二、教学重点和难点重点：并行计算机系统结构、模型、互连方式和性能评价，并行计算模型，并行算法设计策略、基本设计技术和PCAM设计方法学，典型的并行数值算法，并行程序设计等。

难点：并行结构模型和计算模型的理解，并行算法基本设计技术，并行数值算法等。

三、教材及主要参考书教材陈国良，《并行计算：结构，算法，编程》，北京：高教出版社，1999(初版)，2003(修订版)主要参考书：1.陈国良等，《并行计算机体系结构》，北京：高教出版社，20022.陈国良，《并行算法的设计与分析》，北京：高教出版社，2002 (修订版)3.陈国良等，《并行算法实践》，北京：高教出版社，20034.Barry Wilkinson等，陆鑫达等译，《并行程序设计》，北京：机械工业出版社，2001四、课程章节及学时分配第一部分并行计算硬件基础1.并行计算机系统结构和模型4课时(1)并行计算机系统结构(PVP、SMP、MPP、DSM、COW)。

(2)并行计算机存储器访问模型(UMA、NUMA、COMA、NORMA)。

2.并行计算机系统互连4课时(1)系统互连技术(节点内的互连：总线，开关，Buses，switches；节点间的互连：SAN；系统间的互连：LAN，MAN，WAN）。

(2)互连网络拓扑(静态互连网络：LA，RC，MC，TC，HC，CCC；动态互连网络：Buses，crossbar，MINI)。

标准网络（FDDI、ATM、SCI）。

3.并行系统性能评价4课时(1)加速比（Amdahl负载固定加速定律；Gustafson负载可扩放加速定律；Sun和Ni存储受限加速定律）。

063820并行计算32学时/2学分英文译名：Parallel Computing and Distributed Computing适用领域：计算机科学与技术，科学、工程计算开课单位：计算机科学与技术学院教学目的：当今，计算科学已成为与理论科学和实验科学并列的第三门科学，学生有必要了解、初步掌握高性能计算（并行与分布计算）的理论、技术及应用。

预备知识或先修课程要求：算法设计与分析，计算机系统结构，操作系统。

教学主要内容以及对学生的要求：并行计算系统结构介绍，并行计算性能评测，并行算法设计基础及一般设计方法。

分布式系统模型，通信、进程、命名和复制。

内容摘要：高性能计算的应用需求极为广泛，以美国等国家为代表已制订长远发展规划。

本课程将介绍并行计算机结构模型、系统互联技术，当代并行机系统：SMP、MPP和COW。

介绍并行计算性能评测方法与标准，并行算法的基础知识及模型。

并行算法的一般设计方法，包括串行算法的直接并行化，从问题描述开始设计并行算法，借用已有算法求解新问题。

并行算法的基本设计技术，并行算法的一般设计过程及PCAM设计方法学。

分布式系统的目标，分布式计算模型，远程过程调用，远程对象调用，消息通信，代码迁移，软件代理，移动实体的定位，时钟同步，分布式事务，以数据为中心的一致性模型，以客户为中心的一致性模型，分发协议，一致性协议。

基于协作的分布式系统：TIB/Rendezvoas，Jini，及二者的比较，协作模型。

协作系统中心通信、命名、同步、缓存和复制，容错性、安全性等。

考核方式：大作业；平时成绩(出勤情况+研讨情况)占20%。

课程主要教材：[1] 并行计算.陈国良.高等教育出版社，2011[2]分布式系统原理与范型（第2版）. Andrew S. Tanenbaum Maarten Van Steen著，辛春生，陈宗斌等译.清华大学出版社，2008主要参考书目：[1]网络并行计算与分布式编程环境，孙家祖等，科学出版社，1996。