下载文档原格式
并行计算期末试题及答案1. 基础概念部分并行计算是一种计算模式，它使用多个处理单元同时执行计算操作，以加快计算速度。
在现代计算机系统中，我们常常使用多核处理器、图形处理器（GPU）或者分布式系统来实现并行计算。
1.1 并行计算的优势并行计算具有以下几个优势：加速计算速度：通过同时执行多个计算任务，可以极大地提高计算效率。
解决大规模问题：并行计算可以处理大规模和复杂的问题，提供更精确的结果。
降低能耗：通过合理利用处理器资源，可以降低计算任务的能耗。
应用广泛：并行计算可以应用于各个领域，如科学计算、大数据分析、机器学习等。
1.2 并行计算的分类并行计算按照任务之间的关系可以分为两类：数据并行：将数据划分为多个子集，同时在不同的处理器上进行计算，然后将计算结果汇总。
常见的应用包括矩阵运算、图像处理等。
任务并行：将任务划分为多个子任务，每个子任务由一个独立的处理器执行，最后将各个子任务的结果合并。
常见的应用包括并行搜索算法、并行排序等。
2. 并行计算的算法设计2.1 并行算法设计要点在设计并行算法时，需要考虑以下几个要点：任务划分：将计算任务划分为多个子任务，确保各个子任务之间的计算工作均衡，并保持任务之间的独立性。
任务调度：合理安排各个处理器上的任务执行顺序和时间，最大程度地减少通信开销和等待时间。
数据通信：处理器之间需要进行数据交换和通信，应选择合适的通信方式，并考虑通信延迟和带宽等因素。
数据同步：在多个处理器之间，可能需要进行数据同步操作，确保各个处理器之间的数据一致性。
2.2 并行算法实例：并行矩阵乘法并行矩阵乘法是一个常见的数据并行算法，可以有效地利用多核处理器加速大规模矩阵运算。
具体算法如下：步骤1：将输入矩阵划分为若干个小矩阵，每个小矩阵分配给一个处理器。
步骤2：每个处理器计算相应小矩阵的部分结果。
步骤3：将各个处理器计算得到的部分结果进行求和，得到最终的矩阵乘积结果。
3. 并行计算的应用举例3.1 科学计算在科学计算领域，有大量的计算任务需要处理大规模的数据和复杂的数学模型。
第十二章 并行程序设计基础习题例题：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]；试用①相并行；②分治并行；③流水线并行；④主-从行并行；⑤工作池并行等五种并行编程风范，写出如上计算内积的并行代码段。
南开大学“物联网工程”《并行程序设计》23秋期末试题库含答案第1卷一.综合考核(共20题)1.1) R=XR*1.3;G=XG*1.8;B=XB*1.1; 2) R=X[0]*1.3;G=X[1]*1.8;B=X[2]*1.1;这两个程序片段哪个进行向量化效率更高?A.1)B.2)C.不确定D.以上皆错2.SSE指令移动单精度浮点数，不能实现____。
A.将64位数据移动到SSE寄存器高位B.将64位数据移动到SSE寄存器低位C.将32位数据移动到SSE寄存器指定位置D.在两个SSE寄存器高/低64位间移动3.并行计算的新兴应用领域不包括_____。
A.制药B.数字媒体C.国防D.游戏4.如果运算对象是独立无关的变量，则在向量运算之前需_____。
A.将变量拷贝到连续区域B.将变量地址拷贝到连续区域C.将变量逐个传输到向量寄存器D.以上皆错5.CUDA线程层次中不包括()。
A.KernelB.GridC.BlockD.Thread6.7.8.MPI不包括的通信类别是____。
A.点对点通信B.数据传输组通信C.计算和数据传输组通信D.加锁解锁通信9.用pthread_barrier_init初始化障碍，应提供的参数不包括_____。
A.障碍对象B.障碍初值C.障碍属性D.参与的线程数10.多线程是()架构下的并行模式。
A.MIMDB.共享内存C.分布式内存D.分离式地址空间11.12.对于效率E，下面描述错误的是()。
A.理想并行E=1B.总是在0～1之间C.可能1D.可能随着处理器数量增大趋向于013.记并行时间为T，串行时间为T'，处理器数量为p，并行效率E的定义是____。
A.T'-TB.T'/TC.T'/pTD.pT-T'14.求解同一个问题的4个并行算法的等效率函数分析结果如下，其中()的可扩展性最优。
A.θ(plogp)B.θ(p^2)C.θ(p^2logp)D.θ(p^3)15.两个n*n的矩阵相乘，将所有n^2个乘法计算划分给不同进程，再将对应某行某列的n个乘法结果累加得到结果矩阵对应元素，这是一种划分____的数据并行。
例题习题讲解例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。
1、名词解释：（1）等分宽度：把网络划分为两个相等的部分（节点数之多差1），所需要去掉的网络边的条数。
（2）网络直径：网络中两个节点之间的最远的距离（3）并行运行时间：从第一台处理机开始执行任务开始，到最后一台处理机执行完任务所经历的时间。
（4）并行步：能够同时执行的操作数。
（5）加速比：同一任务在串行计算下的运行时间/并行计算下的运行时间。
2、介绍超立方体网络互连方式的性能指标解答：q维超立方体，等分宽度为2q-1，网络直径：q，网络接口数：q3、按照指令流和数据流，并行计算机可以分为哪些类型？各自适合什么样的并行计算？排名在前20的计算机都是什么类型的计算机？它们的区别是什么？解答：（1）SIMD：适合指令/操作级并行（2）MIMD：适合块、回路或子程序级的并行4、并行算法有哪些设计方法？（1）流水线技术（2）分而治之策略（3）平衡二叉树方法（4）倍增技术（5）加速级联策略5、举例说明平衡树方法的原理？参考：使用n/2台计算机，可以在⎡⎤nlog步完成运算。
26、Logp模型有哪些参数？BSP模型有哪些参数？这两个模型之间的关系是什么？（1） L ：源处理机与目标处理机之间进行消息通信所需要等待的延迟时间上限（2） o ：处理机用于发送或接收每个消息的时间开销（3） g ：连续发送/接收消息的时间间隙（4） P ：处理机个数BSP 模型：（1） P ：处理机数（2） g ：选路器吞吐率（3） L ：全局同步之间的时间间隔关系：（1） 本质上等效，可以相互模拟（2） 用BSP 模拟LOGP 所进行的计算时，通常会慢常数倍。
（3） 反之，慢对数倍7、 题目记不清了，只要知道两个公式就可以了，对于logp ：L+2o 对于logGp ：t α+t β8、 计算加速比和效率的题，具体记不清了，只要会使用公式就可以了。
9、 关于群集系统中QR 分解的题目。
将矩阵的行列都分成5等分，得到它的25个任务，按照贪婪算法的调度思想，画出子任务执行的并行步。
！第１题（1）什么是并行计算（2）它的优点有哪些（3）可以通过哪些结构完成并行计算1．并行计算就是在并行计算或分布式计算机等高性能计算系统上所做的超级计算。
（P3）2．计算极大地增强了人们从事科学研究的能力，大大地加速了把科技转化为生产力的过程，深刻地改变着人类认识世界和改造世界的方法和途径。
计算科学的理论和方法，作为新的研究手段和新的设计与创造技术的理论基础，正推动着当代科学与技术向纵深发展。
（P4）3．单指令多数据流SIMD、对称多处理机SMP、大规模并行处理机MPP、工作站机群COW、分布共享存储DSM多处理机。
（P22）第2题什么是网络计算它的特点它与分布式计算、集群计算的关系（P104）网络计算：在工作站机群COW环境下进行的计算称为网络计算。
特点：网络计算结合了客户机/服务器结构的健壮性、Internet面向全球的简易通用的数据访问方式和分布式对象的灵活性，提供了统一的跨平台开发环境，基于开放的和事实上的标准，把应用和数据的复杂性从桌面转移到智能化的网络和基于网络的服务器，给用户提供了对应用和信息的通用、快速的访问方式。
与分布式计算、集群计算的关系：，分布式计算是一门计算机科学，它研究如何把一个需要非常巨大的计算能力才能解决的问题分成许多小的部分，然后把这些部分分配给许多计算机进行处理，最后把这些计算结果综合起来得到最终的结果。
集群计算是使用多个计算机，如典型的个人计算机或UNIX工作站；多个存储设备；冗余互联，来组成一个对用户来说单一的高可用性的系统。
因此，网络计算与分布式计算和集群计算都是属于计算密集型，数据密集型和网络密集型应用。
第3题表征并行系统的性能指标有哪些并行系统的加速比如何定义它能否完全确定系统的性能为什么a.表征并行系统的性能指标主要有：CPU和存储器的基本性能指标，通信开销以及系统机器的成本、价格与性价比，还有系统加速比和系统可扩放性（p88页）；其中CPU和存储器的基本性能指标包括：工作负载，并行执行时间，存储器的层次结构和存储器的带宽。
计算机体系结构专升本试题存储系统与并行计算存储系统与并行计算的关系近年来受到了广泛的关注。
在计算机体系结构中，存储系统起着重要的作用，可以影响计算机的性能和效率。
并行计算则是一种利用多个处理器或计算机同时进行计算的方法，可以提高计算速度和处理能力。
本文将探讨存储系统与并行计算的关系，并分析它们在计算机体系结构中的重要性。
一、存储系统的概念与作用存储系统是计算机体系结构中的关键组成部分，负责存储和管理数据。
它可以分为主存储器和辅助存储器两部分。
主存储器是计算机的内存，用于存储正在执行的程序和数据。
辅助存储器则是计算机的硬盘或光盘等外部存储设备，用于长期存储和备份数据。
存储系统的主要作用有以下几个方面：1. 提供数据和指令的存储空间。
计算机需要存储程序和数据，存储系统提供了足够的存储空间，保证计算机能够正常运行。
2. 实现数据的读写操作。
存储系统可以通过读写指令来读取和写入数据，实现对数据的操作和处理。
3. 提供数据的高速访问。
存储系统具有较高的读写速度，能够快速响应计算机的读写请求，提高计算机的执行效率。
4. 实现数据的持久存储。
辅助存储器可以将数据永久保存在硬盘或光盘等介质中，保证数据的长期存储和备份。
综上所述，存储系统在计算机体系结构中发挥着至关重要的作用。
它不仅提供了计算机的存储空间，还可以对数据进行高效的读写操作，满足计算机的运行需求。
二、并行计算的概念与特点并行计算是一种利用多个处理器或计算机同时进行计算的方法。
与串行计算相比，它可以大幅度提高计算速度和处理能力，适用于复杂的计算任务和大规模的数据处理。
并行计算具有以下几个特点：1. 任务分解。
并行计算将复杂的计算任务分解为多个子任务，由不同的处理器或计算机同时执行，提高了计算效率。
2. 数据并行。
并行计算可以将输入数据分割成多个部分，由不同的处理器或计算机同时处理，减少了数据传输和通信的开销。
3. 结果合并。
并行计算将每个子任务的计算结果合并为最终的结果，提高了计算的准确性和可靠性。
以下是一些关于分布式并行计算的面试题目：
1. 请简要解释分布式并行计算的概念及其与并行计算的区别。
2. 请列举几种常见的分布式并行计算模型，并简要介绍它们的特点。
3. 在分布式并行计算中，如何解决数据依赖性问题？请举例说明。
4. 请解释如何在分布式并行计算中实现任务并行和数据并行。
5. 请简述分布式并行计算中可能遇到的问题及其解决方法。
6. 请介绍分布式并行计算中常用的通信机制，并说明它们的特点和适用场景。
7. 请解释分布式并行计算中的负载均衡策略，并介绍几种常见的负载均衡算法。
8. 请简述分布式并行计算中的容错机制，并说明如何确保计算结果的正确性。
9. 请介绍分布式并行计算在实际应用中的优势和挑战。
10. 请列举一些流行的分布式并行计算框架，并简要介绍它们的特点和应用场景。
在回答这些问题时，可以结合自己的经验和了解，举例说明相关概念和技术的应用。
并行计算面试题目并行计算是一种利用多个处理器同时进行计算的技术，以提高计算效率。
在进行并行计算时，通常会遇到一些相关的面试题目，这些题目旨在考察面试者对并行计算的理解和应用能力。
下面将介绍一些常见的并行计算面试题目，并对每个题目进行详细解答。
1. 什么是并行计算？请简要介绍并行计算的概念及其在计算领域的重要性。
并行计算是一种利用多个处理器同时进行计算的技术，以提高计算效率的方法。
在并行计算中，任务被分解成多个子任务，每个子任务由不同的处理器并行执行，最终将结果合并得到最终的计算结果。
并行计算在计算领域中具有重要意义，可以大大加快计算速度，提高计算效率，同时也可以处理大规模的计算任务，满足复杂计算需求。
2. 请介绍一下并行计算的分类及其特点。
并行计算可以分为两种基本类型：数据并行和任务并行。
数据并行是指将数据分解成多个部分，每个处理器处理不同的数据部分，最终将计算结果合并。
任务并行是指将计算任务分解成多个子任务，每个处理器并行执行不同的子任务，最终将结果合并。
数据并行适合处理大规模的数据集，任务并行适合处理复杂的计算任务。
3. 请解释一下并行计算中的并行度和并行效率，并说明它们的关系。
并行度是指在并行计算中同时执行的处理器的数量，是衡量并行计算规模的重要指标。
并行效率是指并行计算中实际获得的计算速度与理论计算速度之比，反映了并行计算的效率。
并行度越高，计算速度越快，但并行效率并不是线性增加，因为并行计算中存在通信和同步的开销，并行效率受到并行计算中的负载平衡和通信开销的影响。
4. 请说明并行计算中的并行算法有哪些，以及它们的应用领域和特点。
并行计算中常用的并行算法包括并行排序算法、并行搜索算法、并行矩阵计算算法等。
并行算法的应用领域包括计算机视觉、模式识别、机器学习等，具有并行计算速度快、处理能力强的特点。
并行算法的设计需要考虑并行计算的负载平衡、通信开销和算法并行度等因素，以提高并行算法的效率和性能。
计算机学院研究生《并行计算》课程考试试题（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%。
c ） 由于处理器增加时开销也会很大，在16个处理器上的加速比不会比8个处理器上的加速比高出40%。
给出分析过程和结论。
3. （10分）经测试发现，1）一个串行程序，94%的执行时间花费在一个可以并行化的函数中。
现使其并行化，问该并行程序在10个处理机上执行所能达到的加速比是多少？能达到的最大加速比是多少？2）一个并行程序，在单个处理机上执行，6%的时间花费在一个I/O 函数中，问要达到加速比10，至少需要多少个处理机？ 1）由Amdahl 定律知：加速比1(1)/Speedup f f p=+-依题意知：6%,10f p ==代入计算得：16.4994%6%10Speedup =≈+最大加速比为：111lim lim16.7(1)/6%p pSpeedupf f p f→∞→∞===≈+-2)由题意知：此时的串行时间比例为6%则：由式子111094%(1)/6%f f pp≤=+-+得：23.5p≥故至少需要24台处理机。
4．（12分）将一个由256个节点组成的环以dilation-1的方式嵌入到一个8维超立方体里，环中的节点编号为0~255，1）问环节点31，127，255分别映射到超立方体的哪个节点上？2）若超立方体中的结点10110011和进行通讯，如果按照环网拓扑结构，从出发，在超立方体中依次经过哪些节点才能把一条消息传递到？如果按照超立方体拓扑结构，又是如何实现从传递一条消息到的？5．（16分）已知12个具有单位执行时间的任务，任务图如下。
现在3个处理机上处理该任务集，请用Coffman-Graham算法求该任务集的调度优先表L，并用Graham表调度算法调度L，给出任务调度的Gantt图表示。
6．（10分）采用与前序遍历二元树的PRAM算法相同的数据结构，设计一个后序遍历二元树的PRAM算法。
7．（10分）下面是一个串行程序段，用OpenMP最大限度地开发其并行性。
这里假设a、b均为正实值数组，有合法的定义。
float rowterm[m]float colterm[q];int i, j;#pragma omp parallel {#pragma omp sections{#pragma omp parallel for private(j)for ( i=0; i<m; i++) {rowterm[i] = 0.0;#pragma omp parallel for reduction(+:rowterm[i])for (j=0; j<p; j++)rowterm[i] += a[i][2*j] * a[i][2*j+1];#pragma omp parallel forfor (j=0; j<p; j++) {a[i][2*j] /= rowterm[i];a[i][2*j+1] /= rowterm[i];}}}#pragma omp sections{#pragma omp parallel for private(j)for ( i=0; i<q; i++) {colterm[i] = 0.0;#pragma omp parallel for reduce(+:colterm [i])for ( j=0; j<p; j++)colterm[i] += b [2*j][i] * b [2*j+1] [i];#pragma omp parallel forfor ( j=0; j<p; j++) {b [2*j][i] /= colterm[i]; b [2*j+1] [i] /= colterm[i];}} } }8．（12分）查阅文献并结合自己的体会，列举1-2个你的研究领域里存在的典型并行计算应用，讨论一下它们适合的并行计算模式（不少于500字）。
答案1. 证明：（1）由超立方体的性质知： 一个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. 解： 由题可知计算规模是固定的，所以在并行环境下，根据Amdahl 定律可知： 加速比S=1/(1/p+f(1-1/p))，其中p 为处理器数，f 为串行分量的比例，则，f=(p/s-1)/(p-1)，同时对于固定规模的问题，并行系统所能达到的加速上限为1/f ，即受到串行分量的比例的限制。
在2个处理器的环境下，根据上图数据计算各并行程序的串行分量的比： 并行程序I ：f 1=0.20;并行程序II ：f 2=0.06; 并行程序III ：f 3=0.06; 并行程序IV ：f 4=0.02; 并行程序V ：f 5=0.15; 并行程序VI ：f 6=0.03;在16个处理器的环境下，根据上图数据计算各并行程序的加速比如下： 并行程序I ：S 1=4.00并行程序II ：S 2=5.72; 并行程序III ：S 3=8.41; 并行程序IV ：S 4=10.00; 并行程序V ：S 5=4.77; 并行程序VI ：S 6=10.67;则个并行程序在16个处理器的环境下与8个处理器的环境下的加速比提高了：并行程序I ：d 1=20%; 并行程序II ：d 2=31%; 并行程序III ：d 3=49%; 并行程序IV ：d 4=60%; 并行程序V ：d 5=25%; 并行程序VI ：d 6=64%;根据并行程序I 、V 的串行分量的比和16个处理器的环境下的加速比可知，对并行程序I 、V 在16个处理器上性能的陈述都选(b);根据并行程序II 和III 的串行分量的比和16个处理器的环境下的加速比可知，对并行程序II 在16个处理器上性能的陈述选(c);根据并行程序III 、IV 、VI 在16个处理器的环境下的加速比可知，对并行程序III 、IV 、VI 在16个处理器上性能的陈述都选(a);3. 1）由Amdahl 定律知：加速比1(1)/Speedup f f p=+-依题意知：6%,10f p ==代入计算得：16.4994%6%10 Speedup=≈+最大加速比为：111lim lim16.7(1)/6%p pSpeedupf f p f→∞→∞===≈+-2)由题意知：此时的串行时间比例为6%则：由式子111094%(1)/6%f f pp≤=+-+得：23.5p≥故至少需要24台处理机。
4．（12分）将一个由256个节点组成的环以dilation-1的方式嵌入到一个8维超立方体里，环中的节点编号为0~255，1）问环节点31，127，255分别映射到超立方体的哪个节点上？31:00010000;127:01000000;255:10000000若超立方体中的结点和进行通讯，如果按照环网拓扑结构，从出发，在超立方体中依次经过哪些节点才能把一条消息传递到？如果按照超立方体拓扑结构，又是如何实现从传递一条消息到0101 1001的？1011 0011: 2210101 1001：1101011 0011(221)->1011 0001(222)->1011 0000(223)->1001 0000(224)->1001 0001->……->1000 0000(255)->0000 0000(0)->0000 0001->…..->0101 1100（104）->0101 1101（105）->0101 1111（106）->0101 1110（107）->0101 1010（108）->0101 1011（109）->0101 1001（110）1011 0011->1011 0001->1011 1001->1001 1001->1101 1001->0101 1001(第一种方法)1011 0011->0011 0011->0111 0011->0101 0011->0101 1011->0101 1001(第二种方法)1101 0011->1001 0011->1101 0011->0101 0011->0101 0001->0101 1001(第三种方法)5.Step1：R=｛T11,T12｝是无直接后继的任务，任取，选T12,有a(T12)<-1；Step2：i从2到12循环，完成对a(Tj)(j=1,2…12)赋值i=2；R=｛T11，T10｝，N(T10)=｛1｝，N(T10)={0}，选T11，则a(T11)<-2；i=3; R=｛T9，T6，T10｝，N(T9)=2,N(T6)={2,1},N(T10)=1,选T10则a(T10)<-3;i=4;R={T9,T6,T7,T8},N(T9)=2,N(T6)={2,1},N(T7)=3,N(T8)=3,T9，T6任选，选T6，a(T6)<-4;i=5;R={T9,T7,T8},N(T9)=2,N(T7)=3,N(T8)=3,选T9，则a(T9)<-5;i=6;R={T4,T5,T7,T8},N(T4)=5,N(T5)=5,N(T7)=3,N(T8)=3,任选T7，T8，选T7，则a(T7)<-6;i=7;R={T4,T5,T8},N(T4)=5,N(T5)=5,N(T8)=3,选T8，则a(T8)<-7;i=8;R={T4,T5,T3},N(T4)=5,N(T5)=5,N(T3)={7,6}，T4，T5任选,选T4，则a(T4)<-8 i=9,R={T5,T3},N(T5)=5,N(T3)={7,6},选T5，则a(T5)<-9;i=10,R={T2,T3},N(T2)={9,8,4},N{T3}={7,6}，选T3，a(T3)<-10;i=11,R={T2},N(T2)={9,8,4}，选T2，a(T2)<-11;i=12,a(T1)<-12;Step3：构造L表：L=｛T1,T2,T3,T5,T4,T8,T7,T9,T6,T10,T11,T12｝；Step4:6. 策略如下：在执行后序遍历时，我们系统地访问树中所有的边，而且每条边要通过两次：一次从父节点到子节点，而另一次从子节点到父节点。
