1.并行算法设计主要有哪些方法，各种方法的特点是什么？
①串行程序的直接并行化：检查和开拓现有串行算法中固有的并行性，直接
将其并行化。一个显著优点是：算法的稳定性，收敛性等问题在串行算法中已有结论
②从问题描述开始设计并行算法：从问题本身的描述出发，从头设计一个全新的并
行算法
③借用已有的算法求解新问题：借助已有的并行算法求解新问题，方法描述：找出求解问题和某个已解决问题之间的联系；改造或利用已知算法应用到求解问题上。
2.并行算法的设计过程主要分为哪几个阶段，各阶段主要完成什么工作，各阶段
之间的有什么关系？
设计过程分为四步：任务划分(Partitioning 划分) 、通信分析(Communication 通信) 、任务组合(Agglomeration 组合) 、处理器映射(Mapping 映射)。
各阶段的任务：
划分：将计算任务分解成小任务，以尽量开拓并行执行的可能性；
通信：确定小任务需要进行的通信，为组合做准备；
组合：将一些小任务组合成大任务以减少通信开销；
映射：将组合后的任务分配到处理器上，其目标是使总执行时间和通信开销尽量小，使处理器的利用率尽量高
3.并行算法设计技术要有哪些？并说明各种技术主要的设计思想
划分设计技术、分治设计技术、平衡树设计技术、倍增设计技术、流水线设计技术、破对称技术
划分设计技术：划分技术的基本出发点是有效利用空闲处理器、大问题求解需要提高求解速度。具体划分方法包括均匀划分、平方根划分、对数划分、功能划分等。
分治技术：分治技术是一种问题求解的方法学，其思想是将原来的大问题分解成若干个特性相同的子问题分而治之。
流水线技术：设计思想是将算法流程划分成p个前后衔接的任务片断，每个任务片断的输出作为下一个任务片断的输人;所有任务片断按同样的速率产生出结果。
倍增技术：又称指针跳跃技术，适用于处理以链表或树之类表示的数据结构。每当递归调用时，要处理的数据之间的距离将逐步加倍，经过k步后就可完成距离为2*的所有数据的计算。
破对称技术：破对称就是要打破某些问题的对称性，常用于图论和随机算法问题。
平衡树技术：以树的叶结点为输人，中间结点为处理结点，由叶向根或由根向叶逐层进行并行处理。
2014年《并行计算系统》复习题 1.（15分）给出五种并行计算机体系结构的名称，并分别画出其典型结构。 ①并行向量处理机（PVP） ②对称多机系统（SMP） ③大规模并行处理机（MPP） ④分布式共享存储器多机系统（DSM）
⑤工作站机群（COW） 2.（10分）给出五种典型的访存模型，并分别简要描述其特点。 ①均匀访存模型（UMA）： 物理存储器被所有处理机均匀共享 所有处理机访存时间相同 适于通用的或分时的应用程序类型 ②非均匀访存模型（NUMA）： 是所有处理机的本地存储器的集合 访问本地LM的访存时间较短
访问远程LM的访存时间较长 ③Cache一致性非均匀访存模型（CC-NUMA）： DSM结构 ④全局Cache访存模型（COMA）： 是NUMA的一种特例，是采用各处理机的Cache组成的全局地址空间 远程Cache的访问是由Cache目录支持的 ⑤非远程访存模型（NORMA）： 在分布式存储器多机系统中，如果所有存储器都是专用的，而且只能被本地存储机访问，则这种访问模型称为NORAM 绝大多数的NUMA支持NORAM 在DSM中，NORAM的特性被隐匿的 3. （15分）对于如下的静态互连网络，给出其网络直径、节点的度数、对剖宽度，说明该网络是否是一个对称网络。 网络直径：8 节点的度数：2
对剖宽度：2 该网络是一个对称网络 4. （15分）设一个计算任务，在一个处理机上执行需10个小时完成，其中可并行化的部分为9个小时，不可并行化的部分为1个小时。问： （1）该程序的串行比例因子是多少，并行比例因子是多少？ 串行比例因子：1/10 并行比例因子:9/10 （2）如果有10个处理机并行执行该程序，可达到的加速比是多少？10/(9/10 + 1) = 5.263 （3）如果有20个处理机并行执行该程序，可达到的加速比是多少？10/(9/20 + 1)= 6.897 5.（15分）什么是并行计算系统的可扩放性？可放性包括哪些方面？可扩放性研究的目的是什么？ 一个计算机系统（硬件、软件、算法、程序等）被称为可扩放的，是指其性能随处理机数目的增加而按比例提高。例如，工作负载能力和加速比都可随处理机的数目的增加而增加。 可扩放性包括: 1.机器规模的可扩放性
Reviews on parallel programming并行计算英文班复习考试范围及题型：（1—10章） 1 基本概念解释；Translation (Chinese) 2 问答题。Questions and answer 3 算法的画图描述。Graphical description on algorithms 4 编程。Algorithms Reviews on parallel programming并行计算 1 基本概念解释；Translation (Chinese) SMP MPP Cluster of Workstation Parallelism, pipelining, Network topology, diameter of a network, Bisection width, data decomposition, task dependency graphs granularity concurrency process processor, linear array, mesh, hypercube, reduction,
prefix-sum, gather, scatter, thread s, mutual exclusion shared address space, synchronization, the degree of concurrency, Dual of a communication operation, 2 问答题。Questions and answer Chapter 1 第1章 1) Why we need parallel computing? 1）为什么我们需要并行计算？ 答： 2) Please explain what are the main difference between parallel computing and sequential computing 2）解释并行计算与串行计算在算法设计中的主要不同点在那里？ 答： Chapter 2 第2章 1) What are SIMD, SPMD and MIMD denote? 1）解释SIMD, SPMD 和 MIMD是什么含义。 答： 2) Please draw a typical architecture of SIMD and a typical architecture of MIMD to explan. 2）请绘制一个典型的SIMD的体系结构和MIMD的架构。 答：
《并行算法设计与分析》考题与答案 一、1.3，处理器PI的编号是： 解：对于n ×n 网孔结构,令位于第j行，第k 列（0≤j，k≤n-1）的处理器为P i（0≤i≤n2-1）。以16处理器网孔为例,n=4（假设j、k由0开始）： 由p0=p(j,k)=p(0,0) P8=p(j,k)=p(2,0) P1=p(j,k)=p(0,1) P9=p(j,k)=p(2,1) P2=p(j,k)=p(0,2) P10=p(j,k)=p(2,2) P3=p(j,k)=p(0,3) P11=p(j,k)=p(2,3) P4=p(j,k)=p(1,0) P12=p(j,k)=p(3,0) P5=p(j,k)=p(1,1) P13=p(j,k)=p(3,1) P6=p(j,k)=p(1,2) P14=p(j,k)=p(3,2) P7=p(j,k)=p(1,3) P15=p(j,k)=p(3,3) 同时观察i和j、k之间的关系，可以得出i的表达式为：i= j * n+k
一、1.6矩阵相乘（心动算法） a)相乘过程 设 A 矩阵= 121221122121 4321 B 矩阵=1 23443212121121 2 【注】矩阵元素中A(i,l)表示自左向右移动的矩阵，B(l,j)表示自上向下移动的矩阵，黑色倾斜加粗标记表示已经计算出的矩阵元素,如12, C(i,j)= C(i,j)+ A(i,l)* B(l,j) 1 2、
4、
6、
8、
10 计算完毕 b)可以在10步后完成，移动矩阵长L=7，4*4矩阵N=4,所以需要L+N-1=10
第二章习题（P69-70） 一、复习题 1．简述冯?诺依曼原理，冯?诺依曼结构计算机包含哪几部分部件，其结构以何部件为中心？ 答：冯?诺依曼理论的要点包括：指令像数据那样存放在存储器中，并可以像数据那样进行处理；指令格式使用二进制机器码表示；用程序存储控制方式工作。这3条合称冯?诺依曼原理 冯?诺依曼计算机由五大部分组成：运算器、控制器、存储器、输入设备、输出设备，整个结构一般以运算器为中心，也可以以控制器为中心。 (P51-P54) 2．简述计算机体系结构与组成、实现之间的关系。 答：计算机体系结构通常是指程序设计人员所见到的计算机系统的属性，是硬件子系统的结构概念及其功能特性。计算机组成（computer organization）是依据计算机体系结构确定并且分配了硬件系统的概念结构和功能特性的基础上，设计计算机各部件的具体组成，它们之间的连接关系，实现机器指令级的各种功能和特性。同时，为实现指令的控制功能，还需要设计相应的软件系统来构成一个完整的运算系统。计算机实现，是计算机组成的物理实现, 就是把完成逻辑设计的计算机组成方案转换为真实的计算机。计算机体系结构、计算机组成和计算机实现是三个不同的概念，各自有不同的含义，但是又有着密切的联系，而且随着时间和技术的进步，这些含意也会有所改变。在某些情况下，有时也无须特意地去区分计算机体系结构和计算机组成的不同含义。 (P47-P48) 3．根据指令系统结构划分，现代计算机包含哪两种主要的体系结构？ 答：根据指令系统结构划分，现代计算机主要包含：CISC和RISC两种结构。 (P55) 4．简述RISC技术的特点？ 答：从指令系统结构上看，RISC 体系结构一般具有如下特点： (1) 精简指令系统。可以通过对过去大量的机器语言程序进行指令使用频度的统计，来选取其中常用的基本指令，并根据对操作系统、高级语言和应用环境等的支持增设一些最常用的指令; (2) 减少指令系统可采用的寻址方式种类，一般限制在2或3种; (3) 在指令的功能、格式和编码设计上尽可能地简化和规整，让所有指令尽可能等长; (4) 单机器周期指令，即大多数的指令都可以在一个机器周期内完成，并且允许处理器在同一时间内执行一系列的指令。 (P57-58) 5．有人认为，RISC技术将全面替代CISC，这种观点是否正确，说明理由？ 答：不正确。与CISC 架构相比较，RISC计算机具备结构简单、易于设计和程序执行效率高的特点，但并不能认为RISC 架构就可以取代CISC 架构。事实上，RISC 和CISC 各有优势，CISC计算机功能丰富，指令执行更加灵活，这些时RISC计算机无法比拟的，当今时代，两者正在逐步融合，成为CPU设计的新趋势。 (P55-59) 6．什么是流水线技术？ 答：流水线技术，指的是允许一个机器周期内的计算机各处理步骤重叠进行。特别是，当执行一条指令时，可以读取下一条指令，也就意味着，在任何一个时刻可以有不止一条指令在“流水线”上，每条指令处在不同的执行阶段。这样，即便读取和执行每条指令的时间保持不变，而计算机的总的吞吐量提高了。 (P60-62) 7．多处理器结构包含哪几种主要的体系结构，分别有什么特点？ 答：多处理器系统：主要通过资源共享，让共享输入/输出子系统、数据库资源及共享或不共享存储的一组处理机在统一的操作系统全盘控制下，实现软件和硬件各级上相互作用，达到时间和空间上的异步并行。 SIMD计算机有多个处理单元，由单一的指令部件控制，按照同一指令流的要求为他们
第三章互连网络 对于一颗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); 二元胖树如图所示，此时所有非根节点均有2个父节点。如果将图中的每个椭圆均视为单个节点，并且成对节点间的多条边视为一条边，则他实际上就是一个二叉树。试问：如果不管椭圆，只把小方块视为节点，则他从叶到根形成什么样的多级互联网络 答：8输入的完全混洗三级互联网络。 四元胖树如图所示，试问：每个内节点有几个子节点和几个父节点你知道那个机器使用了此种形式的胖树 答：每个内节点有4个子节点，2个父节点。CM-5使用了此类胖树结构。 试构造一个N=64的立方环网络，并将其直径和节点度与N=64的超立方比较之，你的结论是什么 答：A N=64的立方环网络,为4立方环（将4维超立方每个顶点以4面体替代得到），直径d=9，节点度n=4 B N=64的超立方网络，为六维超立方（将一个立方体分为8个小立方，以每个小立方作为简单立方体的节点，互联成6维超立方），直径d=6，节点度n=6 一个N=2^k个节点的 de Bruijin 。 。。。试问：该网络的直径和对剖宽度是多少 答：N=2^k个节点的 de Bruijin网络直径d=k 对剖宽带w=2^(k-1)
一个N=2^n个节点的洗牌交换网络如图所示。试问：此网络节点度==网络直径==网络对剖宽度== 答：N=2^n个节点的洗牌交换网络，网络节点度为=2 ，网络直径=n-1 ，网络对剖宽度=4 一个N=（k+1）2^k个节点的蝶形网络如图所示。试问：此网络节点度=网络直径=网络对剖宽度= 答：N=（k+1）2^k个节点的蝶形网络，网络节点度=4 ，网络直径=2*k ，网络对剖宽度=2^k 对于如下列举的网络技术，用体系结构描述，速率范围，电缆长度等填充下表中的各项。（提示：根据讨论的时间年限，每项可能是一个范围） 答： 如图所示，信包的片0，1，2，3要分别去向目的地A，B，C，D。此时片0占据信道CB，片1占据信道DC，片2占据信道AD，片3占据信道BA。试问： 1）这将会发生什么现象 2）如果采用X-Y选路策略，可避免上述现象吗为什么 答： 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)有i d C 个节点与s 的距离为i 。 证明：由超立方体的性质知： 一个d 维的超立方体的每个节点都可由d 位二进制来表示，则与某个节 点的距离为i 的节点必定在这d 位二进制中有i 位与之不同，那么随机从d 位中选择i 位就有i d C 种选择方式，即与s 的距离为i 得节点就有i d 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 d D 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个处理器上执行了测试。下表表示了各程序达到的加速比。
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); 2.4 试构造一个N=64的立方环网络，并将其直径和节点度与N=64的超立方比较之，你的结论是什么？ 答： N=64的立方环网络,为4立方环（将4维超立方每个顶点以4面体替代得到），直径 d=9，节点度n=4 4.11 一个在p 个处理器上运行的并行程序加速比是p-1，根据Amdahl 定律，串行分量为多少? 答： p/(1+f(p-1))=p-1, f=1/(p-1)2 5.5假定开始时P i (1《i 《n)存有数据 d i ，所谓累加求和是指用 ∑=i j i d 1，来代替中的原始值d i ，算法5.3给出了在PRAM 模型上累加求和算法。 Input: di are kept in Pi, where Output: replaces di in processor Pi Begin for j=0 to logn-1 do for i=2j +1 to n par-do (i) di= d i + d i-2j (ii) Pi=di end for end for End (1）试用n=8为例子，按照上述算法逐步计算出累加和。 (2）分析算法的时间复杂度。
6.3 7.2（1） 例:A={1,3,6,8,11,13} p=6;B={2,4,5,7,10,12,14} ,q=7 p =3, q =3 A={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 * } 33 54 21 13 33 82 40 72
第十二章 并行程序设计基础 习题例题： 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 section lock(S)； critical section unlock(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]； 试用①相并行；②分治并行；③流水线并行；④主-从行并行；⑤工作池并行等五种并行编程风范，写出如上计算内积的并行代码段。 5、图12.15示出了点到点和各种集合通信操作。试根据该图解式点倒点、播送、散步、收集、全交换、移位、归约与前缀和等通信操作的含义。 图12.15点到点和集合通信操作
1在并行机系统中，主流操作系统有UNIX/Linux，AIX(IBM)，HPUX(HP)，Solaris(SUN)，IRIX(SGI)等。 2 常用的并行算法设计的基本技术有划分，分治，倍增，流水域，破对称，平衡 树等设计技术。 3 Matlab并行程序编写过程分为创建对象，创建工作，指定工作任务，提交工作，等待和返回计算任务结果六步。 1. 云计算是对（ D ）技术的发展与运用 A. 并行计算 B网格计算 C分布式计算 D三个选项都是 2. IBM在2007年11月退出了“改进游戏规则”的（ A ）计算平台，为客户带来即买即用的云计算平台。 A. 蓝云 B. 蓝天 C. ARUZE D. EC2 3. 微软于2008年10月推出云计算操作系统是（ C ） A. Google App Engine B. 蓝云 C. Azure D. EC2 4. 2008年，（ A ）先后在无锡和北京建立了两个云计算中心 A. IBM B. Google C. Amazon D. 微软 5. 将平台作为服务的云计算服务类型是（ B ） A. IaaS B.PaaS C.SaaS D.三个选项都不是 6. 将基础设施作为服务的云计算服务类型是（ A ） A. IaaS B.PaaS C.SaaS D.三个选项都不是 7. IaaS计算实现机制中，系统管理模块的核心功能是（ A ） A. 负载均衡 B 监视节点的运行状态 C应用API D. 节点环境配置 8. 云计算体系结构的（ C ）负责资源管理、任务管理用户管理和安全管理等工作 A.物理资源层 B. 资源池层 C. 管理中间件层 D. SOA构建层 9. 下列不属于Google云计算平台技术架构的是（ D ） A. 并行数据处理MapReduce B.分布式锁Chubby C. 结构化数据表BigTable D.弹性云计算EC2 10. 在目前GFS集群中，每个集群包含（ B ）个存储节点 A.几百个 B. 几千个 C.几十个 D.几十万个 11. 下列选项中，哪条不是GFS选择在用户态下实现的原因（ D ） A.调试简单 B.不影响数据块服务器的稳定性 C. 降低实现难度，提高通用性 D. 容易扩展 12. GFS中主服务器节点存储的元数据包含这些信息（ BCD ） A.文件副本的位置信息 B.命名空间 C. Chunk与文件名的映射 D. Chunk副本的位置信息 13. 单一主服务器（Master）解决性能瓶颈的方法是（ ABCD ） A.减少其在数据存储中的参与程度 B. 不适用Master读取数据 C.客户端缓存元数据 D. 采用大尺寸的数据块 14. （ B ）是Google提出的用于处理海量数据的并行编程模式和大规模数据集的并行运算的软件 架构。 A. GFS B.MapReduce C.Chubby D.BitTable 15. Mapreduce适用于（ D ） A. 任意应用程序 B. 任意可在windows servet2008上运行的程序 C.可以串行处理的应用程序 D. 可以并行处理的应用程序
第三章互连网络 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=4 B N=64的超立方网络，为六维超立方（将一个立方体分为8个小立方，以每个小立方作为简单立方体的节点，互联成6维超立方），直径d=6，节点度n=6 3.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 ，网络对剖宽度=4 3.7 一个N=（k+1）2^k个节点的蝶形网络如图3.50所示。试问：此网络节点度=？网络直径=？网络对剖宽度=？ 答：N=（k+1）2^k个节点的蝶形网络，网络节点度=4 ，网络直径=2*k ，网络对剖宽度=2^k 3.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共享或独有.其部件的完整性和单核处理器内核相比完全一?致。片上多核处理器(CMP)是将多个计算内核集成在一个片处埋器芯片中.从而提高计算能力。每个微处理器核心实质上都是?个相对简单的单?线程微处理誥或者比较简单的冬线程微处理器. 这样多个效处理器核心就可以并行地执行程序代码.因而具有了较高的线程级并行性。由于CMP采川了相对简单的微处理蛊作为处理器核心?使得CMP具有高主煉设计和验证周期短.控制逻辑简单、扩展性好.易于实现.功耗低.通信延迟低等优点。此外.CHP还能充分利用不同应用的指令级并行和线程级并行，具有校高线程级并行性的应用町以很好地利用这种结构來提高性能。按照内核的对等与否，CMP 可分为同构多核和异构多核。计算内核相同，地位对等的称为''同构参核役同构CHP人务数山通用的处理器组成.零个处理器执行和同或者类似的任务。计算内核不同，地位不对等的称为“异构多核”，异构多核多采用“主处理核+协处理核”的设计。 C5IP处理器山多个CPU核心组成.每个核心执行％自的程序代码.但是CMP处理器的冬CPU核心执行的程序之间耍进行数据共享和同步.所以硬件结构必须支持核间通信。高效的通信机制是CHP处理器高性能的敢要保障?比较主流的片上高效通信机制有两种，一种是基于总线共享的cache结构，一种是基于片上的互连结构。总线共cache结构是扌旨每个CPU内核拥有共享的二级或三级cache,用于保存比较常用的数据.并通过连接核心的总线进行通信。这种系统的优点是结构简单，通信速度I淙缺点是基于总线的结构可扩展性较差。基于片上互连的结构是指每个CPU核心具有独立的处理单元和cache,各个CPU核心通过交叉开关或片上网络等方式连接在-?起。各个CPU 核心间通过消息通信。这种结构的优点是可扩展性好,数据带宽有保证，缺点是硕件结构复杂?且软件改动较大。 性能计算方法 以下6种性能爲求是用户经常提到的：执行时间.运行速隊吞吐率.利用率.成本有效性以及性能/成本比。 1) 运行?：运行速度是衡虽计算机性能的-项币雯指标。通常所说的计算机运算速度(平均运算速度).是指毎秒钟所能执行的描令条数.-般用 “百万条指令/秒"(mips, Million Instruction Per Second)来描述。同一台计算机.执行不同的运算所需时间可能不同?【大M对运算速度的描述常采用不同的方法。常用的有CPU时钟频率(丄频入每秒T?均执行折令数(ips)等。 2) 执行时间：等于从并行程序开始执行到所有进程执行完毕，瞄上时钟走过的时间，也称为谱上时间((wall clock time wall clock time).对客个 进程，增上时间可进??步分解为计算进涉分解为计算CPU时间.通偃CPU.同步开销时间.同步解的进程空闲时间。 3) 吞吐率：吞吐率定义为在单位时间内所处理的作业数。如果每次只执行一个作业，那么吞吐率就是执行时何的(御数。当有多个作业彼同 时执行时.常使用吞吐率来农示系统的性能。 4) 利川率：可茨示为计算机可达到速度与峰值速度之比。 5) 成本有效性:农示成本有效性的合适指标是利用率因子(或简称利川率),其可用利用率农达式,即农示为一个给定计算机可达到速度与峰值 速度之比。 6) 性能/成木比：所获得的性能与所消耗费用之比。性能可以川所获得的计并机达到放大速度表示。 第二章分布式系统中的通信机制 1?如果一个客户/服务器系统的通信原语是非阻塞的，在消息实际彼发送之前发送.对send的调川已完成。为了减少开销? 一些系统不拷贝数据到内核，而是直接从川户空间发送。对于这样的系统，诸设计两种方案.发送者能知道传输己经完成?可以遥新使用缓冲区。 第-?种方法是内核将消息拷贝到内部缓冲区，其后允许进程继续执行。第二种方法是当消息被发送后?中断发送者并通知它缓冲区可用.这里不需耍备分，节省了时间。 2?在许多通信系统中，调用send 个计数器，以保证当服务器削溃时客户机不会永久彼挂起。假设一容错系统，所有的客八机和 服务器都用多处理机方式实现.那么客户机或服务器谢溃的概率儿乎等于寥。你认为在这样的系统中能安全地避免超时吗？ 不安全。因为在客户机和眼务器的通信过程中,并不仅仅由于客户机或服务器崩溃,从而引起信息的丢失，系统的瘫痪。在信息传输网络中也可能引起信息的丢失。而超时机制能够無决这个问题。 3. 解释RPC的工作原理和参数传递方法。僻释何为异步RPC。 客户机器上的进程调用远程过程时，通过客户存根将参数传递到服务器，然后阻塞"C直到收到响应。服务器上的服务器存根使用这些参数调用本地的过程，得出结果后再传递冋客户机器客户存根捉取结果后以通常的方式返冋。从客户的角度看,该过程和木地调用具有相同的形式，是透明的。 参数传递方法有传递值参数和传递引川参数。 在异步RPC中，服务器接收到客户发送的RPC请求后立即向客户送回应冷Z后再调川客户请求的过程.客户收到确认消息麻继续向下执行,只是在服务器将结果传递回来时发生一个中断。
并行计算期末试题 适用专业：理工类 考试说明： 1、将试卷答案以学号命名为word文件，如115042101.doc，上传到 ftp://172.17.124.203/upload。 2、第一、二大题，直接将答案写在题后；第三、四题要求将程序补充、编写完 整并将运行结果截图插在题目后面。 一、简述题（每小题4分，共20分）。 1、简述openmp编译制导指令master,single,critical,atomic的功能。 1.master制导语句指定代码段只能被主线程执行 2.single编译制导语句指定内部代码只能由线程组中的一个线程执行。线程组中没有执行single语句的线程会一直等待代码块的结束，使用nowait子句除外。 3.critical制导语句表明域中的代码一次只能由一个线程执行，其他线程被阻塞在临界区 4.atomic制导语句指定特定的存储单元将被原子更新 2、简述openmp编译制导子句shared,private的功能？简述openmp编译制导指令threadprivate的功能。 1.private子句表示它列出的变量对于每个线程是局部的。 2.shared子句表示它所列出的变量被线程组中所有的线程共享，所有线程都能对它进行读写访问。 3.threadprivate语句使一个全局文件作用域的变量在并行域内变成每个线程私有，每个线程对该变量复制一份私有拷贝并在多个并行域中保持。 3、简述openmp函数omp_set_num_threads，omp_get_num_threads， omp_get_thread_num的功能；环境变量OMP_NUM_THREADS的功能。 omp_set_num_threads
上机地点：电三楼519机房 上机时间分为两组：周六上午9:00~11:30，PB12011班级同学 周六晚上6:30~9:00，其他同学 【注意事项】 1.本次作业分为简单题和中等题，简单题每题3分，共6分,中等题 4分。 2.实验请用基于C/C++的OpenMP编程模型最大效度的实现并行。 3.在完成实验后，提交实验报告时请务必给出不同线程数的加速比 图或加速比表格，并需要给出你算法的核心思想。代码请附在实验报告最后的附件中，最后只需要交实验报告即可。 4.请在一周之内提交你的实验报告，命名按照“1_学号_姓名”的格 式，如“1_SA13011075_张三”，并发送至pc_2015spring@https://www.doczj.com/doc/a913541567.html, 5.实验报告模板和本文档可以到此处下载： https://www.doczj.com/doc/a913541567.html,/~xiangbin/pc2015/ 6.测试时间函数参考。 double time_used; struct timeval tv_start, tv_end; gettimeofday(&tv_start, NULL); function(); gettimeofday(&tv_end, NULL); time_used=(tv_https://www.doczj.com/doc/a913541567.html,_sec-tv_https://www.doczj.com/doc/a913541567.html,_sec)*1000000+(tv_https://www.doczj.com/doc/a913541567.html,_usec-tv_https://www.doczj.com/doc/a913541567.html,_ usec); printf("time_used = %lf s\n", time_used/1000000); 一．简单题 1.针对教材中求PI的实例程序，请给出至少两种不同并行方式的OpenMP 实现。（划分数>= 1, 000, 000） 2. 使用OPENMP编写矩阵乘法程序。
一、名词术语翻译 1）SIMD ：Single Instruction Multiple Data, 单指令多数据流。 2）MIMD ：Multiple Instruction Multiple Data, 多指令多数据流。 3）SIMT ：Single Instruction Multiple Threads, 单指令多线程。 4）SPMD ：Single Program Multiple Data, 单程序多数据流。 5）MPMD ：Multiple Program Multiple Data, 多程序多数据流。 6）PVP ：Parallel Vector Processor, 并行向量处理机。 7）SMP ：Symmetric Multiprocessor, 对称多处理机。 8）MPP ：Massively Parallel Processor, 大规模并行处理机。 9）DSM ：Distributed Shared Memory, 分布式共享存储。 10）COW ：Cluster of Workstation, 工作站机群。 11）UMA ：Uniform Memory Access, 均匀存储访问模型。 12）NUMA ：Nonuniform Memory Access, 非均匀存储访问模型。 13）COMA ：Cache-Only Memory Access, 全高速缓存访问模型。 14）NORMA ：No-Remote Memory Access, 非远程存储访问模型。 15）CC-NUMA ：Coherent-Cache Nonuniform Memory Access, 高速缓存一致性非均匀存储访问模型。 16）CUDA ：Compute Unified Device Architecture, 统一计算架构。 17）GPU ：Graphics Process Unit, 图形处理器。 18）GPGPU ：General-Purpose Computing on GPU, 通用计算的图形处理器。 19）HPC ：High Performance Computing, 高性能计算。 二、简答题 1、常用的MPI群集通信函数有哪些？简述其功能。（4.5 P194）【群集通信是一个进程组中的所有进程都参加的全局通信操作。 群集通信一般实现三个功能：通信、聚集和同步。 通信功能主要完成组内数据的传输； 聚集功能在通信的基础上对给定的数据完成一定的操作； 同步功能实现组内所有进程在执行进度上取得一致。】
我们的大数据时代 （一） 单选题（每题2分） 1. 下列关于舍恩伯格对大数据特点的说法中，错误的是（D） A. 数据规模大 B. 数据类型多样 C. 数据处理速度快 D. 数据价值密度高 2. 下列关于大数据的分析理念的说法中，错误的是（D） A. 在数据基础上倾向于全体数据而不是抽样数据 B. 在分析方法上更注重相关分析我不是因果分析 C. 在分析效果上更追究效率而不是绝对精确 D. 在数据规模上强调相对数据而不是绝对数据 3. 万维网之父是（C） A. 彼得·德鲁克 B. 舍恩伯格 C. 蒂姆·伯纳斯— D. 斯科特·布朗 4. 下列关于普查的缺点的说法中，正确的是（A）。 A. 工作量较大，容易导致调查容有限、产生重复和遗漏现象 B. 误差不易被控制 C. 对样本的依赖性比较强 D. 评测结果不够稳定
5.下列关于聚类挖掘技术的说法中，错误的是（B）。 A. 不预先设定数据归类类目，完全根据数据本身性质将数据聚合成不同类别 B. 要求同类数据的容相似度尽可能小 C. 要求不同类数据的容相似度尽可能小 D. 与分类挖掘技术相似的是，都是要对数据进行分类处理 6. 智慧城市的构建，不包含（C）。 A. 数字城市 B. 物联网 C. 联网监控 D. 云计算 7.大数据的起源是（C）。 A. 金融 B. 电信 C. 互联网 D. 公共管理 8. 智慧城市的智慧之源是（C）。 A. 数字城市 B. 物联网 C. 大数据 D. 云计算 9. 假设一种基因同时导致两件事情，一是使人喜欢抽烟，二是使这个人和肺癌就是（A）关系，而吸烟和肺癌则是（A）关系。 A. 因果；相关
（1）比较PVP, SMP, MPP, DSM, Cluster, Constellation https://www.doczj.com/doc/a913541567.html,/cnlht/article/details/6237955 PVP:并行向量处理机 系统中包含了少量的高性能专门设计定制的向量处理器VP（Vector Processor），每个至少具有1Gflops的处理能力。 系统中使用了专门设计的高带宽的交叉开关网络向VP连向共享存储模块，存储器可以M/s字节的速度向处理器提供数据。 这样的机器通常不使用高速缓存，而是使用大量的向量寄存器和指令缓冲器。 SMP:对称多处理机 SMP系统使用商品微处理器（具有片上或外置高速缓存），他们经由高速总线（或交叉开关）连向共享存储器。这种机器主要应用于商务，例如数据库、在线事务处理系统和数据仓库等。重要的是系统是对称的，每个处理器可等同地方问共享存储，限制系统中的处理器不能太多（一般小于64个），同时总线和交叉开关互连一旦做成也难于扩展。
MPP：大规模并行处理机 MMP一般是指超大型（Very Large-Scale）计算机系统，他具有如下特征： ①处理结点采用商用微处理器； ②系统中有物理上的分布式存储器； ③采用高通信带宽和低延迟的互联网络（专门设计和定制的）； ④能扩放至成百上千乃至上万个处理器； ⑤它是一种异步的MIMD机器，程序系由多个进程组成，每个都有其私有地址空间，进程间采用传递消息相互作用。 MMP的主要应用是科学计算、工程模拟和信号处理等以计算为主的领域。
DSM：分布式共享存储 高速缓存目录DIR用以支持分布高速缓存的一致性。DSM和SMP的主要差别是，DSM在物理上有分布在各个节点中的局存，从而形成了一个共享的存储器。对用户而言，系统硬件和软件提供了一个单地址的编程空间。DSM相对于MPP的优越性是编程较容易。 Cluster/Cow：工作站机群 COW的重要界限和特征是： ①COW的每一个节点都是一个完整的工作站（不包括监视器、键盘、鼠标等），这样的节点有时叫做“无头工作站”，一个节点也可以是一台PC或SMP； ②各节点通过一种低成本的商品（标准）网络（如以太网、FDDI和ATM开关等）互连（有的商用机群也使用定做的网络）； ③各节点内总是有本地磁盘，而MPP节点内却没有；
2014年《并行计算系统》复习题 （15分）给出五种并行计算机体系结构的名称，并分别画出其典型结构。 ①并行向量处理机（PVP） ②对称多机系统（SMP） ③大规模并行处理机（MPP） ④分布式共享存储器多机系统（DSM） ⑤工作站机群（COW） （10分）给出五种典型的访存模型，并分别简要描述其特点。 ①均匀访存模型（UMA）： 物理存储器被所有处理机均匀共享 所有处理机访存时间相同 适于通用的或分时的应用程序类型 ②非均匀访存模型（NUMA）： 是所有处理机的本地存储器的集合 访问本地LM的访存时间较短 访问远程LM的访存时间较长 ③Cache一致性非均匀访存模型（CC-NUMA）： DSM结构 ④全局Cache访存模型（COMA）： 是NUMA的一种特例，是采用各处理机的Cache组成的全局地址空间 远程Cache的访问是由Cache目录支持的 ⑤非远程访存模型（NORMA）： 在分布式存储器多机系统中，如果所有存储器都是专用的，而且只能被本地存储机访问，则这种访问模型称为NORAM 绝大多数的NUMA支持NORAM 在DSM中，NORAM的特性被隐匿的 3. （15分）对于如下的静态互连网络，给出其网络直径、节点的度数、对剖宽度，说明该网络是否是一个对称网络。 网络直径：8 节点的度数：2 对剖宽度：2 该网络是一个对称网络 4. （15分）设一个计算任务，在一个处理机上执行需10个小时完成，其中可并行化的部分为9个小时，不可并行化的部分为1个小时。问： （1）该程序的串行比例因子是多少，并行比例因子是多少？ 串行比例因子：1/10
并行比例因子:9/10 如果有10个处理机并行执行该程序，可达到的加速比是多少？ 10/(9/10 + 1) = 5.263 （3）如果有20个处理机并行执行该程序，可达到的加速比是多少？ 10/(9/20 + 1)= 6.897 （15分）什么是并行计算系统的可扩放性？可放性包括哪些方面？可扩放性研究的目的是什么？ 一个计算机系统（硬件、软件、算法、程序等）被称为可扩放的，是指其性能随处理机数目的增加而按比例提高。例如，工作负载能力和加速比都可随处理机的数目的增加而增加。可扩放性包括: 1.机器规模的可扩放性 系统性能是如何随着处理机数目的增加而改善的 2.问题规模的可扩放性 系统的性能是如何随着数据规模和负载规模的增加而改善 3.技术的可扩放性 系统的性能上如何随着技术的改变而改善 可扩放性研究的目的: 确定解决某类问题时何种并行算法与何种并行体系结构的组合，可以有效的利用大量的处理器； 对于运用于某种并行机上的某种算法，根据在小规模处理机的运行性能预测移植到大规模处理机上的运行性能; 对固定问题规模，确定最优处理机数和可获得的最大的加速比 （15分）给出五个基本的并行计算模型，并说明其各自的优缺点。 ①PRAM：SIMD-SM 优点： 适于表示和分析并行计算的复杂性； 隐匿了并行计算机的大部底层细节（如通信、同步），从而易于使用。 缺点： 不适于MIMD计算机，存在存储器竞争和通信延迟问题。 ②APRAM:MIMD-SM 优点： 保存了PRAM的简单性； 可编程性和可调试性（correctness）好； 易于进行程序复杂性分析。 缺点： 不适于具有分布式存储器的MIMD计算机。 ③BSP：MIMD-DM 优点: 把计算和通信分割开来； 使用hashing自动进行存储器和通信管理； 提供了一个编程环境。 缺点： 显式的同步机制限制并行计算机数据的增加； 在一个Superstep中最多只能传递h各报文。