并行计算总复习
第一章：
1并行计算与串行计算在算法和编程上有哪些显著差异？
答：·并行算法设计与并行计算机处理器的拓扑连接相关
·并行算法设计和采用的并行计算模型有关。
·并行计算有独自的通讯函数
·并行算法设计时，如何将问题分解成独立的子问题是科学研究问题，并非所有的问
题都可以进行分解。
2多核与多处理机的异同点？
多处理机：把多个处理器通过网络互连形成一个新机器。可以是专用，也可以是通用。拓扑连接是可以改变的。
多核：在过去单个处理器芯片上实现多个“执行核”。但这些执行核都有独立的执行命令集合和体系结构。这些独立的执行核+超线程SMT技术组成多核处理器
3对单处理器速度提高的主要限制是什么？
答：晶体管的集成密度，功耗和CPU表面温度等
第二章
1 SIMD 和MIMD 所代表的计算模型是什么？主要区别和各自的系统结构示意图。SPMD的含义是什么？
SIMD指单指令多数据流模型；MIMD指多指令多数据流模型；
SPMD指单程序多数据流模型，在SIMD中把指令改为程序表示每个处理器并行的执行程序。
SIMD MIMD
硬件较少处理器较多处理器
内存一个寻址系统，存储
量小多个寻址系统，存储量大
耗费较高，难开发易于开发（多个商业
组件可用）
加速高取决于应用
2 若按通讯方式对并行算法进行分类有几种分类方法，各自的特点是什么？
基于共享地址空间：并行平台支持一个公共的数据空间，所有处理器都可以访问这些空间。处理器通过修改存储在共享地址空间的数据来实现交互。
基于消息传递：消息传递平台有p个处理节点构成，每个节点有自己的独立地址空间。运行在不同节点上的进程之间的交互必须用消息来完成，称为消息传递。这种消息交换用来传递数据、操作以及使多个进程间的行为同步。
3 在理想并行计算模型中（并行随机访问计算机parallel random access machine(PRAM), EREW, ERCW CREW, 和CRCW表示的意思是什么？
EREW：互斥读互斥写，这一类的PRAM独占访问内存单元，不允许并发的读写操作。最弱的PRAM模型，对内存访问提供最小的并发性。
CREW：并发读互斥写。对内存单元允许多读，但对内存位置多写是串行的
ERCW：互斥读并发写。对内存单元允许多写，但多读是串行的。
CRCW：并发读并发写。对内存单元允许多读多写。最强大
4 能画出多处理机系统中处理单元的基本互连结构图，Mesh, hypercube, 网络，注意对顶点
编号的要求。
Mesh:
二维网格中每个维有sqrt（p）个节点，p为处理器的数目。
hypercube:p为处理器数目，超立方体结构有logP维，每维上有两个节点
一个前面加1实现，这样标号0110的节点和标号0101的节点相隔两个链路因为他们有两位
不同，性质以此类推。
网络：
设p个处理器processor（输入），p个存储区bank（输出）；该网络有sqrt（p）级
输入：i；输出：j
j=2i，0<=i<=p/2-1;
j=2i+1-p, p/2<=i<=p-1.
数据选路时，假设从s（二进制表示）传送到t，从最高位起开始比较，相同的位走直通，不同的位走交叉。
5 知道对静态网络的常用测度：直径，连通性，二分宽度(bisection width), cost.
直径：网络中两个处理节点之间的最长距离称为网络直径。（越小越好）
连通性：网络中任意两个节点间路径多重性的度量。连通性的一个度量是把一个网络分成两个不连通的网络需要删除的最少弧数目。（越大越好）
二分宽度：把网络分成两个相等网络时必须删去的最小通信链路数目。（越大越好）
cost：网络中所需的通信链路的数量或线路数量。
6 能说出一种解决多处理器系统中cache和内存数据一致性问题的方法。（侦听和基于目录）用无效协议维持一致性，并用基于目录的系统来实现一致性协议。
基于目录：
为全局内存增加一个目录，维护一个bitmap，表示已缓存的处理器及相应的数据项状态。三状态协议含有无效、脏以及共享三种状态。
工作原理：当一个处理器P1修改了共享数据，P1修改bitmap,state 为dirty,它自己可以继续修改。当另一处理器P2需要读该数据，目录告诉它p1目前拥有该数据，并通知p1更新状态，并把数据送给P2.
优点：减少数据无谓的移动和更新（把空间分的更细）
缺点：连接复杂性高O(mp)
7 能给出store-and-forward routing 和cut-through routing的思想。通讯费用是如何计算的？延迟时间，t s, t h, t w
store-and-forward routing ：在此过程中，消息穿过有多个链路的路径时，路径上的每个中间节点接受和存储完整的消息后，就把消息转发给下一个节点。
T = t s+（m t w+ t h ）l ，t h 为消息头导致的开销。l 为链路数。m 为消息字长。
cut-through routing ：在此过程中，消息被分成固定大小的单元，称为数据片。首先从源节点向目的节点发送跟踪程序以建立两点间的连接。连接完成后，数据片就一个接一个的发送。中间节点无需等待所有消息到达就可以发送数据片。当某一数据片被中间节点接收后，该数据片被传到下一节点。与store-and-forward routing 不同，每个中间节点无需用缓冲区空间存储完整的信息。因此，中间节点只需要使用更少的内存和带宽，速度也快得多。
T = t s + m t w + t h*l ，t h 为消息头导致的开销。l 为链路数。m 为消息字长。 Tcomm= ts+lth+mtw ；
1)startuptime (Ts): 在数据包上加上必要的头、尾信息，错误检测矫正信息、执行路由算法时间以及建立节点与路由器之间的接口。
2）per-hop time (Th): node latency from u to v;
3 )per-word-transfer time(Tw)(每个字的传输时间），如果通道带宽为r 个字符每秒，每个字符的传输时间为Tw=1/r
8 对Mesh 的X-Y_routing 和对Hypercube 的E-Cube routing 的路由规则。
Mesh 的X-Y_routing ：消息首先沿X 为出发，直到到达目标节点的列，再沿Y 维到达目的节点。其路径长度为L = |Sx-Dx|+|Sy-Dy|;Sx ，Sy 为源节点坐标；Dx ，Dy 为目标节点坐标。 Hypercube 的E-Cube routing ：考虑节点数为p 的d 维超立方体。令Ps 和Pd 分别为源节点和目标节点的编号。在E-Cube 算法中，节点Ps 计算Ps (+) Pd 的值并沿k 维发送消息，其中k 是Ps (+) Pd 中的最低非零有效位的位置。每个中间节点Ps 收到信息，计算出Ps (+) Pd ，再将消息沿着与最低非零有效位对应的维转发，直到消息到达目标节点。
9 如何把linear array, mesh 和hypercube 相互嵌入？G(i,d)函数的计算。 ·linear array 嵌入到hypercube ：
含2d 个节点的linear array 可以嵌入到d 维超立方体中，只需把linear array 中的节点i 映射到hypercube 的节点G （i,x ）上。函数G （i ，x ）定义如下： G （0，1）=0； G （1，1）=1；
G （i ，x+1）= G （i ，x ） i<2x G （i ，x+1）=2x +G(21+x -1-i,x) i ≥2x
（已知d 位葛莱码，对原项加前缀0，反映项加前缀1，可得到d+1位葛莱码）
·mesh 嵌入到hypercube ：
将s r 22?mesh 嵌入到到s r +2个节点的hypercube 中，只须将mesh 上的节点（i,j ）映射到hypercube 的节点G(i,r-1)||G(j,s-1)上，即node(i,j) —>G(i,r-1)||G(j,s-1)
·mesh 嵌入到linear array
10把复杂网络嵌入的简单网络，能说明些什么问题？其意义是什么？一般对简单网络的带宽是怎么要求的？
意义：高维上的网络一般布线复杂，有线的交叉和长短不一等问题。而加宽通讯带宽后的低维互连网络，可以取代高维复杂网络。如果带宽增加到可以抵消互连拥塞，就可按稠密网络一样运行。
第三章
11 dependency graph 的定义及画法。对同一问题dependency graph 的画法是否唯一？dependency graph表示任务间的依赖关系和任务的执行次序关系。是一种有向无环图，节点表示任务，边表示节点间的依赖性。边
13 并行算法的粒度定义是什么？粒度大小在理论上和在实际上对并行算法的影响。
分解问题得到的任务数量和大小决定了分解的粒度，将任务分解成大量的细小任务称为细粒度，而将任务分解成少量的大任务称为粗粒度。
14在进程调度中，把processes 影射到processors的基本原则是什么？减少通讯，…,
1）设法将相互独立的任务映射到不同的进程中以获得最大并发度；
2）确保关键路径上的任务一旦可执行就去执行它们，以使得总计算时间最短
3）映射相互交互的任务到同一进程以便最小化进程间的交互。
15在并行算法设计时，有几种把计算分解的技术？能给出名称并能举例说明。
·Recursive decomposition (递归分解）：可能产生太多任务使程序变慢
or 快速排序
·Data decomposition : based on the independency of data（基于数据独立性分解）：根据对输出数据的划分来划分任务。例如：矩阵相乘
·Exploration decomposition（探索分解）：对应于人工智能中基于解空间探索方法的问题求解，例如迷宫游戏
·Speculative decomposition （投机分解）：用于分支语句中，在未能决定分支转向时，并行的计算多个分支，当最终决定转向时，正确的分支对应的计算将被利用，其他的被丢弃。·混合分解，将前面的分解方法组合应用，在计算的不同阶段使用不同的分解方法。例如，快速排序，先数据分解然后再使用递归分解
16为了解决由于数据分布密度不均匀问题，能说出3种以上可以帮助使并行任务的负载接近平衡的方法或思路。
循环块分配、随机块分配、图划分
17 能说明data parallel model, task graph model 和work pool model 的含义。
·data parallel model（数据并行模型）：任务被静态或半静态的映射到进程，并且每个任务都对不同的数据进行相似的操作。这种并行性是把同样的操作并发的运用到不同的数据项上产生的结果，因此称为数据并行。
·task graph model（任务图模型）：使用任务之间的相互关系来提高本地性或减少交互开销。如果某一问题中，与任务对应的数据量远大于与任务相对应的计算，则通常用任务图模型来解决此类问题。
·work pool model（工作池模型）：动态映射任务到进程以保持负载平衡，在这种映射中，任何任务可能由任何进程执行。进程可以产生工作并把它添加到工作池中。
第四章
18 Basic communication operations
对偶的概念是什么？在对通讯原语研究中，为什么强调操作对之间的对偶性？能给出3个以上的对偶原语。
·通信操作的对偶是原始操作的逆操作，可以通过逆转原操作中的通信方向和消息序列来完成。
·强调对偶的意义在于，研究一个问题，其对偶问题的解可以类似解决。
·one-to-all broadcast / all-to-one reduction, all-to-all broadcast / all-to-all reduction, scatter / gather 19 能画出下列操作的示意图，并能解释通信原语所完成的任务是什么
one to all broadcast; all to one reduction
all to all broadcast; all to all reduction
scatter, gather, all reduce, prefix sum，
all to all personalized communication. Circular shift
·one to all broadcast; all to one reduction
一个进程发送相同的数据给其他所有的进程；
来自所有进程的数据通过一个相关的操作符组合起来，并被累加到一个目标进程的缓冲区中。
·all to all broadcast; all to all reduction
多对多广播是一对多广播的推广，其中所有p个节点同时发起一个广播；
多对多规约是多对多广播的对偶，p个多对一规约同时进行，每个操作都有不同的目标节点。
·scatter, gather,
散发：单个节点发送一个大小为m 的唯一消息给每一个其他节点，散发与广播的不同点是：广播，所有进程接收到相同的消息；而散发，不同的节点接收到不同的消息。
收集：一个节点从其他各个节点那里收集消息，与多对一规约不同，收集操作不涉及数据的
组合与规约。
·all reduce, prefix sum ，
全规约：等同于先进性一个多对一规约，再进行一个一对多广播。
前缀和：n0n1,…,np -1 —> S1,S2,…,Sp -1,其中
·all to all personalized communication ：
每个节点发送一个大小为m 的不同消息给其他每个节点，每个节点都发送不同的消息给不同的节点，而在多对多广播中，每个节点发送相同的消息给所有其他节点。
·Circular shift,
循环q 移位定义：在一个p 节点的总体中，节点i 发送一个数据包给节点（i+q ）mod p ，其中0 20能写出在hypercube 上的 · one to all broadcast/ ·all to one reduction P114P115 ∑==i j j i n S 0 ·all-to-all personal broadcast;P131 ·all-to-all broadcast; P118 算法以及时间复杂性的分析。能举出2种以上在并行编程中的应用例子。 第五章 21并行算法的分析测度 并行算法并行加速比S，效率E和费用cost的计算公式。说明在什么情况下可能出现超线性加速比？何谓费用最佳的并行算法cost-optimal？设计费用最佳的并行算法的思路是什么？·加速比S = Ts/Tp （Ts串行运行时间，Tp并行运行时间） 理论上，加速比不可能超过处理器数p，但是加速比大于p是可能的，当加速比大于p时，称为超线性加速比；使用高速缓存或基于探索策略的并行算法都可能出现超线性效果。 ·效率E= S/p= Ts/（Tp*p）（p：处理器的个数） ·Cost = Tp*p, E = Ts/cost. Cost-optimal if cost(n) = O(Ts)—>E = 1. cost-optimal:如果在并行计算机上，求解问题的成本作为属于数据大小的函数，与在单片机上的已知最快串行算法有着同样的渐进增长，那么称并行系统是成本最优的。 设计费用最优的并行算法思路： ①把数据划分为p个部分 ②用p个处理器分别来处理这p个部分 ③用并行算法将p个结果合并 ④根据费用最优得出p的值使p满足n = (plogp) 22 Amdahl定理的含义？如何证明？ Amdahl定理：一个规模为W的问题的串行部分为Ws，那么，不管用多少处理器，W/Ws都是其加速比的上界。 证明：因为W = Wp+Ws Ts = W Tp=Ws+Wp/p 又因为S= Ts/Tp 则S= W/(Ws+Wp/p)= (W/Ws)/(1+Wp/pWs) 因为p->无穷大, 则S-> W/Ws 第六章 23 MPI是什么的缩写，MPI是语言还是一个函数库？ MPI：the Message Passing Interface MPI is a function library，used with other programming languages 24 能说出三个MPI的基本函数,并作出解释。 ?MPI_Init 初始化MPI ?MPI_Finalize 终止MPI ?MPI_Comm_size 确定进程个数 ?MPI_Comm_rank 确定被叫进程的标号 ?MPI_send 发送 ?MPI_Recv 接收 25 MPI程序的基本结构是什么？一般的MPI程序都有MPI说明有哪些？ 异步模式，松散同步模式 ·启动和终止MPI MPI_Init(int *argc, char ***argv) MPI_Finalize() ·获取信息 MPI_Comm_size(MPI_Comm comm, int *size) MPI_Comm_rank(MPI_Comm comm, int *rank) ·发送和接收消息 MPI_Send() MPI_Recv() 26 MPI程序中容易出现什么形式的死锁？ 发送与接受顺序上的死锁 27 MPI是通过什么方法，实现在Mesh上的并行算法？能读懂MPI程序。 MPI_Cart_create(comm,2,10,1,1,&comm_2d) 从最初申请到的并发进程集合组成2维网格 int MPI_Comm_rank(MPI_comm_old, MPI_Comm_new) 把过去的id 变换成新的2维网格下的id 值 int MPI_Cart_rank(MPI_Comm comm_cart, int *coords, int *rank) 基于2维网格后的2维坐标，得到2维网格下的进程id） int MPI_Cart_coord(MPI_Comm comm_cart, int rank, int maxdims, int *coordinate) 根据在新的2维环境下进程的id，返回在2维网格下的坐标，coordinate是数组 第七章 28 Pthead的定义是什么？Pthread 程序一般要包含哪些语句？ IEEE指定的一个标准的线程API，POSIX API。POSIX也称为Pthread 线程的创建、终止pthread_create pthread_exit 等待所有线程运行完毕以便完成结果的合并pthread_join 29 在pthread中，thread之间的同步，对关键区域的共享使用时是如何实现的？ 使用mutex-lock(互斥锁) 使得各个线程互斥的访问关键区域。要访问关键区域，线程必须首先获得互斥锁并锁定pthread_mutex_lock()，离开关键区域后,要进行解锁pthread_mutex_unlock()，mutex-lock被一个线程锁定后，不允许其他的线程进入关键区域。 30 Mutex 的属性类型以及使用，条件变量和mutex_lock的一起使用。能用Pthread 语句写出简单的多线程之间对共享资源的共享的代码。 ·正常互斥锁：在任意时刻，只允许一个线程锁定互斥锁，已获得互斥锁的线程若试图再次锁定它，将导致死锁。 ·递归互斥锁：允许单一的线程多次锁定互斥锁，线程每锁定一个互斥锁时，锁计数器加1，每次解锁计数器减1，如果任何其他线程想成功锁定一个递归互斥锁，锁计数器必须为0. ·错误检查互斥锁：一个线程只能锁定一个互斥锁一次，当线程试图锁定一个已经锁定的互斥锁时，错误检查互斥锁将返回一个错误而不是死锁。 31 Open MP 是什么形式的API?如何实现并发程序设计的？ ·OpenMP 是一种可以用FORTRAN, C以及 C++在共享地址空间计算机上进行编程的指令性的API。OpenMP命令提供对并发，同步以及数据处理的支持，但不需要显式设置互斥锁、条件变量、数据范围以及初始化。 ·使用parallel命令来创建一组线程 #pragma omp parallel [clause list] { //parallel segment } 每个线程执行parallel segment中内容 Parallel和命令for、sections一起使用实现迭代和任务的并发。 ·for命令用来在多个线程间分割并行迭代空间，一般形式如下： #pragma omp for [clause list] /* for loop*/ ·sections命令用于对非循环的并行任务分配,形式如下： #pragma omp sections [clause list] { #pragma omp section { taskA(); } #pragma omp section { taskB(); } … } 每个段（即为相应的任务）分配给一个线程 32能用Open MP 写出矩阵与向量，矩阵之间和易于并行计算的程序代码。 矩阵乘 #pragma omp parallel default(private) shared (a, b, c, dim) num_threads(4) #pragma omp for schedule(static) for (i = 0; i < dim; i++) { for (j = 0; j < dim; j++) { c(i,j) = 0; for (k = 0; k < dim; k++) { c(i,j) += a(i, k) * b(k, j); } } } 第八章 并发实现矩阵与向量的乘法 能给出如何实现矩阵转置的算法。能写出Cannon，Fox和简单矩阵乘法算法。 33 并发实现矩阵与向量的乘法。A X ·带状划分的矩阵-向量乘法 ?划分(行带状划分): Pi存放xi和a（i,0）,a（i,1）,…,a（i,n-1）, 并输出yi ?算法: 对p=n情形 ①每个Pi向其他处理器播送xi(多到多播送)； ②每个Pi计算； ?注: 对p ·棋盘划分的矩阵-向量乘法 ?划分(块棋盘划分): Pi,j存放ai,j, xi置入Pi,i中 ?算法: 对p=n2情形 ①每个Pi,i向Pj,i播送xi(一到多播送)； ②按行方向进行乘-加与积累运算，最后一列Pi,n-1收集的结果为yi； p 的二维网孔， ?注: 对p< n2情形,p个处理器排成p 算法中Pi,i向Pj,i播送X中相应的p n/个分量 34 能给出如何实现矩阵转置的算法。 算法: ①按mesh 连接进行块转置(不同处理器间) ②进行块内转置(同一处理器内) 35能写出Cannon ， Fox 和简单矩阵乘法算法。 Cannon P255 ·初始时，把子矩阵Aij 和Bij 分配给处理器Pij ①矩阵A 的第i 行循环左移i 步，矩阵B 的第j 列循环上移j 步；t=p ； ②各处理器A 块与B 块进行乘-加运算；t--； ③if （t<>0）,A 矩阵每行循环左移1步，B 矩阵每列循环上移1步 上面算法中，每个进程Pij 中一共进行了p 次Aik 与Bkj （10-≤ ≤p k ）的相乘，从而完 成矩阵A 和B 的乘法运算 Fox 课件 ·初始时，把子矩阵Aij 和Bij 分配给进程Pij （同Cannon ） ①Ai,i 向所在行的其他处理器进行一到多播送； ②各处理器将收到的A 块与原有的B 块进行乘-加运算; ③B 块向上循环移动一步; ④如果Ai,j 是上次第i 行播送的块，本次选择 向所在行的其他处理器进行一到多播送; ⑤转②执行p -1次; 第九章 36奇、偶排序的并行算法， 能叙述双调（Bitonic ）排序的思路以及画法。知道该算法是如何在超立方体上实现的。 ·奇-偶排序的并行算法 考虑每个进程一个元素的情况。在奇数排序阶段，每个奇数下标的进程将其元素与其右边的相邻元素进行比较-交换；同样，在偶数排序阶段，每个偶数下标的进程将其元素与其右边的相邻元素进行比较-交换。 ·双调排序 s = ?a0,a1,…,an -1? 是一个双调序列并且 a0 ≤ a1 ≤ ··· ≤ an/2-1 and an/2 ≥ an/2+1 p j i A mod )1(,+ ≥···≥an-1 ；令子序列 s1 = ?min{a0,an/2},min{a1,an/2+1},…,min{an/2-1,an-1}? s2 = ?max{a0,an/2},max{a1,an/2+1},…,max{an/2-1,an-1}? 则s1与s2都是双调序列且s1中每个元素都小于s2中元素。这样原问题s排序就化简为两个较小的双调序列排序，并将结果连接起来。上述一个双调序列划分成两个较小双调序列的操作称作双调分裂。n个元素的序列进行logn次双调分裂即可完成排序。 将任意序列转化为双调序列并最终完成排序/ /label：进程标号d：超立方体维数 第十章 37 最小生成树和最短路径算法的并行实现；P319 P321 ·最小生成树Prim 算法： 设G （V ，E ）为加权无向连通图，A=（ai ，j ）为加权邻接矩阵。用Vt 来保存最小生成树构造过程中的顶点。维护一个数组d ，对于每个顶点)(T V V v -∈，d[v]中保存从Vt 中的任何顶点到顶点v 的边中最小的权值。 ① 任选一点r 加入Vt ，d[r]=0 ②对于所有)(T V V v -∈，若边（r ，v ）存在，则令d[v]=w(r,v)，否则令d[v]=∞ ③while Vt ≠V do 找到一个顶点u 满足d[u]=min{d[v]| )(T V V v -∈}; 将u 加入到集合Vt ； 对于所有)(T V V v -∈，更新d[v]的值； endwhile 并行形式： 令p 为进程数，将集合V 划分为p 个子集，每个子集分配给不同的进程。每个进程Pi 存储数组d 中与Vi 对应的部分。在while 循环的每次迭代中，每个进程Pi 计算d i [u]=min{d i [v]| )(T V V v -∈i V ?}，对所有的d i [u]进行多对一规约操作得到全局最小值，并存储在P0中。此时进程P0中保存新的顶点u ，它将被插入到Vt 中。进程P0使用一对多广播将u 广播给所有的进程。负责顶点u 的进程将u 标记为属于集合Vt ，最后每个进程对自己本地的顶点更新d[v]的值。 ·单源最短路径Dijkstra 算法 与最小生成树算法Prim 十分相似，不同点是Dijkstra 存储的数组l[u],它是从顶点s 经Vt 中的顶点到达点u 的最小成本，而Prim 存储d[u]，它是连接Vt 中的某个顶点与u 的最小成本。 并行形式也一样。 ·全源最短路径Floyd算法 使用递归公式 求解全部顶点对间的最短路径 并行形式： 用2维块映射划分矩阵D)(k，矩阵D)(k分为大小为) n (p p n 的p个块，每块分配给 / ( ) / 一个进程 38 图的连通分支的并发实现；P329 对图进行深度优先遍历可以找出连通分支 并行形式： 将图G的邻接矩阵划分为p个部分，每个部分分配给一个进程。第一步，每个进程Pi计算子图Gi的深度优先生成森林。第二步，生成森林按对合并，直到只剩下一个生成森林。 合并方法：假设将A合并到B，对A中的每条边（u，v），确定B中两个顶点是否处在同一棵树上，如果不是，则将两棵树合并。 39 寻找图的极大独立集算法的思想。P333 Luby算法：计算一个图的顶点V的最大独立集I： ①集合I初始设置为空，候选顶点集合C=V ②一个唯一的随机数分配给C中每一个顶点，如果某个顶点的随机数小于所有与它相邻顶 点的随机数，则将它加入到I中； 更新集合C，除去加入到I中的顶点以及与它们相邻的所有顶点 ③重复②至C为空 并行形式： 使用三个数组，一个存储进入最大独立集I中的节点，一个存储候选集C，一个存储随机数R。将候选集C在p个进程中划分。每个进程为从C中分配给它的顶点产生一个随机数。当所有顶点都产生随机数后，就可以来确定哪些顶点包含在I中。 第12章 40 Dynamic Programming的特点是什么？ 把问题划分为子问题，结合子问题的答案得到原问题的答案。 与分而治之方法的不同之处在于，动态规划当中的子问题相互依赖，不是独立的。 最优化：一个问题最优答案是由它的子问题的最优答案构造的 记忆性：避免重复计算，通常维护一个table来记录已经解决的子问题 41 如何利用存储空间换计算时间，能举例说明。 空间换时间的思路是保存计算结果，而不是重复计算。 当子问题有了计算结果后，结果会被保存在一个字典序列中， 当递归计算需要用到问题Q时，查字典确认问题Q是否已经被计算并保存：如果没有记录，执行递归调用 如果问题Q已经解决，则检索结果，不执行递归调用 返回计算结果之前，在字典中保存 42能说明如何去设计一个动态规划算法的基本步骤。 1找出最优解的性质，并刻画其结构特征 2 递归的定义最优解（写动态规划方程） 3 自下而上计算最优解的值 4 根据前面的计算信息构造最优解 43知道对矩阵乘法链和最长公共字串的计算算法。知道并行的动态规划算法的设计思路。·矩阵乘法链 · ·最长公共子串 用F[i,j]来表示包含串A前i个元素的子串与包含串B前j个元素的子串的最长公共子串。 长为m的串A与长为n的串B的最长公共子串长度即为F[i,j]的值。 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.机器规模的可扩放性 高性能计算（并行计算）复习提纲 第一章并行计算机系统及其结构模型 1．了解并行计算机系统互联网络及其分类 不同带宽与距离的互连技术: 总线、SAN、LAN、MAN、WAN 1，静态互联网络：是指处理单元之间有着固定连接的一类网络，在程序执行期间，这种点到点的连接不变。典型的静态网络有一维线性阵列、二维网孔、树连接、超立方网络、立方环、洗牌交换网、蝶形网络等。2，动态互联网络：是用开关单元构成的，可按应用程序的要求动态的改变连接组态。典型的动态网络包括总线、交叉开关和多级互连网络等,3，标准互联网络 2.并行计算机系统结构，参见图1.20（P23）五种结构，要求理解这几种结构的硬件组成及工作方式。 2，并行计算机系统结构： 行向量处理机pvp ：硬件：向量处理机vp、共享存储器SM。工作方式：高带宽的交叉开关网络将vp连向共享存储模块，存储器可以以兆字节每秒的速度想处理器提供数据。通常使用向量寄存器和指令缓冲器。 对称多处理机SMP：硬件：商品微处理器（具有片上或外设高速缓存）、共享存储器、 I/O设备。工作方式：微处理器由总线或交叉开关连向共享存储器。每个处理器可同等的访问共享存储器、I/O设备和操作系统 服务。 ＭPP一般是指超大型计算机系统，它具有如下特性：①处理节点采用商品微处理器；②系统中有物理上的分布式存储器；③采用高通信带宽和低延迟的互连网络；④能扩放至成百上千乃至上万个处理器；⑤它是一种异步的MIMD机器，程序系由多个进程组成，每个都有其私有地址空间，进程间采用传递消息相互作用DSM分布式共享存储多处理机 高速缓存目录DIR用以支持分布高速缓存的一致性。ＤＳＭ和ＳＭＰ的主要差别是，ＤＳＭ在物理上有分布在各节点中的局存从而形成了一个共享的存储器。对用户而言，系统硬件和软件提供了一个单地址的编程空间. COW工作站机群 机群往往是低成本的变形的MPP。COW的重要界线和特征是：①每个节点都是一个完整的工作站(不包括监视器、键盘、鼠标等），一个节点也可以是一台PC或SMP；②各节点通过一种低成本的商品（标准）网络互连（；③各节点内总是有本地磁盘④节点内的网络接口是松散耦合到I/O 总线上的，⑤一个完整的操作系统驻留在每个节点中，而MPP中通常只是个微核，COW 的操作系统是工作站ＵＮＩＸ，加上一个附加的软件层以支持单一系统映像、并行度、通信和负载平衡等。 3并行计算机的几种访问存储模型。 访问存储模型： 第一章：大数据与云计算 1.何为大数据？ 海量数据或巨量数据，其规模巨大到无法通过目前主流的计算机系统在合理时间内获取、存储、管理、处理并提炼以帮助使用者决策。 2.大数据具有4V+1C的特征 （1）数据量大：存储的数据量巨大，PB级是常态 （2）多样：数据的来源及格式多样 （3）快速：数据增长速度快 （4）价值密度低：需要对大量的数据进行处理，挖掘其潜在的价值。 （5）复杂度：对数据的处理和分析的难度大 3.什么是云计算？ 长定义：云计算是一种商业模型。它将计算任务分布在大量计算机构成的资源池上，使各种应用系统能根据需要获取计算力、存储空间和信息服务。 短定义：云计算是通过网络按需提供可动态伸缩的廉价计算服务。 4.云计算是并行计算、分布式计算和网络计算的发展。 5.云计算特点： （1）超大规模（2）虚拟化（3）高可靠性（4）通用性 （5）高可伸缩性（6）按需服务（7）极其廉价 6.云计算按照服务类型大致可分为三类 （1）将基础设施作为服务。（IaaS）（2）将平台作为服务。（PaaS）（3）将软件作为服务（SaaS） 7.云计算实现机制 云计算技术体系结构分为四层：物理资源层、资源池层、管理中间件层和SOA构建层 8.云计算优势 （1）更低的硬件和网络成本（2）更低的管理成本和电力成本（3）更高的资源利用率 第二章：Google云计算原理与应用 1.Google文件系统是一个大型的分布式文件系统。它为Google云计算提供海量存储，处于所有核心技术的底层。 2.GFS将整个系统的节点分为三类角色：客户端、主服务器、数据块服务器 3.GFS特点 （1）采用中心服务器模式（2）不缓存数据（3）在用户状态下实现（4）只提供专用接口4.在服务器失效经常发生的情况下,云计算数据存储技术需要采用容错机制和冗余机制来保证数据的可用性。 5.Master容错：Master上保存了GFS文件系统的三种元数据。 （1）命名空间，也就是整个文件系统的目录结构 （2）Chunk与文件名的映射表 （3）Chunk副本的位置信息，每一个Chunk默认有三个副本 6.Chunk Server容错：Chunk的默认大小是64MB。 7.系统管理技术 （1）大规模集群安装技术（2）故障检测技术（3）节点动态加入技术（4）节能技术 8. MapReduce：在编程时，开发者必须实现两个主要的函数Map和Reduce （1）一个Map函数就是对一部分原始数据进行指定的操作 （2）一个Reduce操作就是对每个Map所产生的中间结果进行合并操作 9.实现机制 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的架构。 答： 小学数学简便运算专项练习400题 第一部分(1-50题) 12.06＋5.07＋2.94 30.34＋9.76－10.34 83 ×3÷83 ×3 25 ×7×4 34÷4÷1.7 1.25÷32×0.8 102×7.3÷5.1 17 73+174-773 195－137－95 11 32+752+353 933-15.7-4.3 41.06 －19.72－20.28 752－383+83 8 74+295-95 700÷14÷5 18.6 ÷2.5÷0.4 1.96÷0.5÷4 1.06 ×2.5×4 13×1917÷1917 29÷2713×2713 19.68－（2.68＋2.97） 5.68＋（5.39＋4.32） 19.68－（2.97＋9.68） 7 172+(185-172) 576-(83-71 ) 0.74 ÷(71×10074) 1.25×（ 8 ÷0.5） 0.25 ×（ 4 × 1.2） 1.25×（ 213×0.8） 9.3 ÷(4÷93100) 24×(1211-83-61+31) (12+ 72) ×7 0.92×1.41＋0.92×8.59 516×137-53×137 1.3×11.6－1.6×1.3 59 ×11.6＋18.4×59 9999+999+99+9 4821-998 3.2×12.5×25 1.25×88 7.6÷0.25 3.5÷0.125 1.8×99＋1.8 3.8 ×9.9＋0.38 257×103-257×2-25 7 1.01×9.6 102×0.87 2.6 ×9.9 327 ×31+327 1712×32+32÷517 第二部分（51-100题） 3733 ×36 3733×38 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. 云计算按照服务类型大致可分为以下类（ A、B、C ） A.IaaS B. PaaS C. SaaS D.效用计算 10. 下列不属于Google云计算平台技术架构的是（ D ） A. 并行数据处理MapReduce B.分布式锁Chubby C. 结构化数据表BigTable D.弹性云计算EC2 11. 在目前GFS集群中，每个集群包含（ B ）个存储节点 A.几百个 B. 几千个 C.几十个 D.几十万个 12. 下列选项中，哪条不是GFS选择在用户态下实现的原因（ D ） A.调试简单 B.不影响数据块服务器的稳定性 C. 降低实现难度，提高通用性 D. 容易扩展 13. GFS中主服务器节点存储的元数据包含这些信息（ BCD ） A.文件副本的位置信息 B.命名空间 C. Chunk与文件名的映射 D. Chunk副本的位置信息 14. 单一主服务器（Master）解决性能瓶颈的方法是（ ABCD ） A.减少其在数据存储中的参与程度 B. 不适用Master读取数据 C.客户端缓存元数据 D. 采用大尺寸的数据块 15. （ B ）是Google提出的用于处理海量数据的并行编程模式和大规模数据集的并行运算的软件架构。 A. GFS B.MapReduce C.Chubby D.BitTable 16. Mapreduce适用于（ D ） A. 任意应用程序 B. 任意可在windows servet2008上运行的程序 C.可以串行处理的应用程序 D. 可以并行处理的应用程序 17. MapReduce通常把输入文件按照（ C ）MB来划分 A. 16 B32 C64 D128 18. 与传统的分布式程序设计相比，Mapreduce封装了（ ABCD ）等细节，还提供了一个简单而强大的接口。 A. 并行处理 B. 容错处理 C. 本地化计算 D. 负载均衡 19.（ D ）是Google的分布式数据存储于管理系统 A. GFS B. MapReduce C. Chubby D.Bigtable 20.在Bigtable中，（ A ）主要用来存储子表数据以及一些日志文件 A. GFS B. Chubby C.SSTable D.MapReduce 21. Google APP Engine使用的数据库是（ C ） A. 改进的SQLServer B. Orack C. Date store D. 亚马逊的SimpleDB 《并行算法设计与分析》考题与答案 一、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 运算定律练习题 （1）乘法交换律：a×b＝b×a 乘法结合律：（a×b）×c＝a×（b×c） 38×25×4 42×125×8 25×17×4 （25×125）×（8×4） 49×4×5 38×125×8×3 (125×25)×4 5 ×289×2 （125×12）×8 125×（12×4） (2) 乘法交换律和结合律的变化练习 125×64 125×88 44×25 125×24 25×28 （3）加法交换律：a＋b＝b＋a 加法结合律：（a＋b）＋c＝a＋（b＋c） 357＋288＋143 158＋395＋105 167＋289＋33 129＋235＋171＋165 378＋527＋73 169＋78＋22 58＋39＋42＋61 138＋293＋62＋107 （4）乘法分配律：（a＋b）×c＝a×c＋b×c 正用练习 （80＋4）×25 （20＋4）×25 （125＋17）×8 25×（40＋4）15×（20＋3） （5）乘法分配律正用的变化练习： 36×3 25×41 39×101 125×88 201×24 （6）乘法分配律反用的练习： 34×72＋34×28 35×37＋65×37 85×82＋85×18 25×97＋25×3 76×25＋25×24 （7）乘法分配律反用的变化练习： 38×29＋38 75×299＋75 64×199＋64 35×68＋68＋68×64 ☆思考题：（8）其他的一些简便运算。 800÷25 6000÷125 3600÷8÷5 58×101－58 74×99 【思路导航】在除法里，被除数和除数同时乘或除以一个相同的数，商不变。 325÷25 =（325×4）÷（25×4） =1300÷100 =13 【练一练1】（1）450÷25（2）525÷25 （3）3500÷125 《云平台与存储技术》2016-2017-2 复习题目 一选择题 1.云计算是对（）技术的发展与运用； A.并行计算B网格计算C分布式计算D三个选项都是； 答案：D 2.从研究现状上看，下面不属于云计算特点的是（）； A.超大规模 B.虚拟化 C.私有化 D.高可靠性； 答案：C 3. https://www.doczj.com/doc/3c858877.html,公司通过（）计算云，可以让客户通过WEB Service方式租用计算机来运行自己的应用程序。 A. S3 B. HDFS C. EC2 D. GFS 答案：C 5. IBM在2007年11月退出了“改进游戏规则”的（）计算平台，为客户带来即买即用的云计算平台。 A. 蓝云 B. 蓝天 C. ARUZE D. EC2 答案：A 6. 亚马逊AWS提供的云计算服务类型是（） A. IaaS B.PaaS C.SaaS D.三个选项都是 答案：D 7. 将平台作为服务的云计算服务类型是（） A. IaaS B.PaaS C.SaaS D.三个选项都不是 答案：B 8 将基础设施作为服务的云计算服务类型是IaaS，其中的基础设施包括 （） A.CPU资源 B.内存资源 C 应用程序 D.存储资源 E.网络资源 答案：C 9 关于虚拟化的描述，不正确的是（） A 虚拟化是指计算机元件在虚拟的基础上而不是真实的基础上运行。 B 虚拟化技术可以扩展硬件的容量，简化软件的重新配置过程。 C 虚拟化技术不能将多个物理服务器虚拟成一个服务器 D CPU的虚拟化技术可以单CPU模拟多CPU运行，允许一个平台同时运行多个操作系统。 10 windows azure 属于云服务的哪一类（） A SaaS B PaaS C IaaS D 以上三项都不是 答案：B 11云计算作为中国移动蓝海战略的一个重要部分，于2007年由移动研究院组织力量，联合中科院计算所，着手起步了一个叫做（）的项目。 A. “国家云” B. “大云” C. “蓝云” D. “蓝天” 答案：B 12 Google Docs 属于云服务的哪一类（） A SaaS B PaaS C IaaS D 以上三项都不是 答案：A 13 下列关于公有云和私有云描述不正确的是（） A 公有云是云服务提供商通过自己的基础设施直接向外部用户提供服务 B 公有云能够以低廉的价格，提供有吸引力的服务给最终用户，创造新的业务价值 C 私有云是为企业内部使用而构建的计算架构 D 构建私有云比使用公有云更便宜 答案：D 14 （多选）云计算的特性包括：（） A. 简便的访问 B. 高可信度 C. 经济型 D. 按需计算与服务 答案：A B C D 15 关于云管理平台描述正确的是（） A 云管理平台为业务系统提供灵活的部署、运行与管理环境 B 屏蔽底层硬件，操作系统的差异 C 为应用提供安全、高性能、可扩展、可管理、可靠和可伸缩的全面保障 D 云管理不涉及到虚拟资源的管理 Windows下MATLAB分布式并行计算服务器配置和使用方 法 1MATLAB分布式并行计算服务器介绍 MATLAB Distributed Computing Server可以使并行计算工具箱应用程序得到扩展，从而可以使用运行在任意数量计算机上的任意数量的worker。MATLAB Distributed Computing Server还支持交互式和批处理工作流。此外，使用Parallel Computing Toolbox 函数的MATLAB 应用程序还可利用MATLAB Compiler （MATLAB 编译器）编入独立的可执行程序和共享软件组件，以进行免费特许分发。这些可执行应用程序和共享库可以连接至MATLAB Distributed Computing Server的worker，并在计算机集群上执行MATLAB同时计算，加快大型作业执行速度，节省运行时间。 MATLAB Distributed Computing Server 支持多个调度程序：MathWorks 作业管理器（随产品提供）或任何其他第三方调度程序，例如Platform LSF、Microsoft Windows Compute Cluster Server（CCS）、Altair PBS Pro，以及TORQUE。 使用工具箱中的Configurations Manager（配置管理器），可以维护指定的设置，例如调度程序类型、路径设置，以及集群使用政策。通常，仅需更改配置名称即可在集群间或调度程序间切换。 MATLAB Distributed Computing Server 会在应用程序运行时在基于用户配置文件的集群上动态启用所需的许可证。这样，管理员便只需在集群上管理一个服务器许可证，而无需针对每位集群用户在集群上管理单独的工具箱和模块集许可证。 作业（Job）是在MATLAB中大量的操作运算。一个作业可以分解不同的部分称为任务（Task），客户可以决定如何更好的划分任务，各任务可以相同也可以不同。MALAB中定义并建立作业及其任务的会话（Session）被称为客户端会话，通常这是在你用来编写程序那台机器上进行的。客户端用并行计算工具箱来定义和建立作业及其任务，MDCE通过计算各个任务来执行作业并负责把结果返 云计算与虚拟化考试 一、单项选择题(每题2分,共45题) 1、云计算就是把计算资源都放到上（B ） A、对等网 B、因特网 C、广域网 D、无线网 2、我们常提到的"Window装个VMware装个Linux虚拟机"属于（C） A、存储虚拟化 B、内存虚拟化 C、系统虚拟化 D、网络虚拟化 3、简单的理解为云计算等于资源的闲置而产生的。（A） A、正确 B、错误 4、一个有10个硬盘组成的Raid5阵列最多可以允许（D）个硬盘出现故障不影响其数据的完整性。 A、1个 B、2个 C、4个 D、5个 5、相比各种网路存储的设置技术来讲，本地硬盘还是最快的（A ）。 A、正确 B、错误 6、SaaS是（A ）的简称。 A、软件即服务 B、平台即服务 C、基础设施即服务 D、硬件即服务 7、微软于2008年10月推出云计算操作系统是（C） A、GoogleAppEngine B、蓝云 C、Azure D、EC2 8、虚拟化资源指一些可以实现一定操作具有一定功能，但其本身是（A ）的资源，如计算池，存储池和网络池、数据库资源等，通过软件技术来实现相关的虚拟化功能包括虚拟环境、虚拟系统、虚拟平台。 A、虚拟 B、真实 C、物理 D、实体 9、云计算是对（D）技术的发展与运用 A、并行计算 B、网格计算 C、分布式计算 D、三个选项都是 10、虚拟交换机可以连多块物理网卡，所以同一块物理网卡可以连多个虚拟交换机。(B ) A、正确 B、错误 11、（D ）在许多情况下，能够达到99.999%的可用性。 A、虚拟化 B、分布式 C、并行计算 D、集群 12、下列哪个特性不是虚拟化的主要特征（D） A、高扩展性 B、高可用性 C、高安全性 D、实现技术简单 13、与开源云计算系统HadoopHDFS相对应的商用云计算软件系统是（A） A、GoogleGFS B、GoogleMapReduce C、GoogleBigtable D、GoogleChubby 14、IaaS是（C ）的简称。 A、软件即服务 B、平台即服务 C、基础设施即服务 D、硬件即服务 15、云计算可以把普通的服务器或者PC连接起来以获得超级计算机计算机的计算和存储等功能，但是成本更低。(A) A、正确 B、错误 16、Raid1是备份量极高的Raid策略，相应的他的保护能力也很强（B）。 A、正确 第二章习题（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计算机有多个处理单元，由单一的指令部件控制，按照同一指令流的要求为他们 万方数据 ２ＬＢＧＫＤ２Ｑ９模型的并行计算 ２．１数据分布 将流场划分成Ｎ。ｘＮ，的网格。设有Ｐ＝只×Ｐｖ个进程参与并行计算，进程号Ｐ。＝Ｈ以（０≤ｉ＜只，０≤Ｊ＜尸ｖ）。将数据按照重叠一条边的分块分布到各进程中。其中，进程Ｐ。存储并处理的数据网格点集，如图ｌ所示。 图１进程珊存储并处理的区域（斜线处为重叠部分） ２．２交替方向的Ｊａｃｏｂｉ迭代通信 Ｊａｃｏｂｉ迭代是一类典型的通信迭代操作。文献［４】主要讨论了一个方向的Ｊａｃｏｂｉ迭代。根据数据分布及计算要求，需要采用２个方向交替的Ｊａｃｏｂｉ迭代通信操作。本文认为，“即发即收”的通信策略能有效避免完全的“先发后收”可能造成的通信数据“堆积”过多，从而避免数据的丢失。进程Ｐｌｉ的通信操作如下（见图２）： （１）Ｉｆｉ≠只一１ｔｈｅｎ发送数据到进程Ｐ¨，； （２）Ｉｆｉ≠０ｔｈｅｎ从进程Ｐｆ＿Ｊ，接收数据； （３）Ｉｆ，≠只－１ｔｈｅｎ发送数据到进程Ｐｍｌ； （４）ＩｆＪ≠０ｔｈｅｎ从进程Ｐ—ｌ接收数据。 各进程并行执行上述操作。 图２交普方向的Ｊａｃｏｂｉ迭代 ２．３通信时间理论 由一般的通信模型可知，若发送、接收信息长度为ｎ字节的数据所需时间为：丁（ｎ）＝口＋ｎ∥，其中，常数口为通信启动时间；∥为常系数，则上述一次交替方向的Ｊａｃｏｂｉ迭代通信操作的时间约为 ２０ｅ＋２ｆｌ＇Ｎ、．Ｐ，＝１ Ｐ。＝１ 其他 其中，∥７＝∥ｓｉｚｅｏｆ（ｄｏｕｂｌｅ）。 一般情况下，当等３鲁，即等＝鲁时，通信的数据量（字节数）是最少的，为４口＋４∥，．／丝堡。可见，通信的信息 Ｖ只×０ 总量和通信时间随进程总数只×尸ｖ的增加而减少。 由于ｃ语言中数组是按“行”存放的（Ｆｏｒｔｒａｎ是按“列”存放的），当存放、发送列数据时，需要一定的辅助操作，这就增加了并行计算的计算时间，因此在只：Ｐｖ无法恰好等于Ｎｘ：Ｎ。时，需要综合考虑流场形状及大小、数据在内存中的按“行”（或按“列”）的存放方式，以确定数据的最佳分布方案。 ３数值实验 数值实验是在“自强３０００”计算机上进行的ｏｕ自强３０００”计算机拥有１７４个计算结点，每个计算结点上有２个３．０６ＣＰＵ，２ＧＢ内存。本文的实验使用了其中的３２个计算结点共６４个ＣＰＵ。程序采用ＭＰＩ及Ｃ语言编写，程序执行时，每个计算结点中启动２个进程。数值实验针对不同规模的网格划分、不同进程数以及不同的数据分布方案进行了大量实验，测得如下结果：不同的流场规模对应着各自的最佳网格划分方式；计算次数越多，加速比越大，越能体现并行计算的优越性。 由表１数据可以得知，对于规模为Ｎｘ×Ｎ、，＝４００ｘ４００，数据划分成６×６块时的加速比最高，而对于ＭＸＮｙ＝６００ｘ２００，数据划分为１２×３块则更具优越性。合适的划分方式可以使总体通信量减至最少，从而提高加速比和并行效率。另外，计算规模越大，加速比越大。 表１并行计算Ｄ２Ｑ９模型的加速比（进程数为３６） 在固定计算规模，增加处理器的情况下，并行系统的加速比会上升，并行效率会下降；在固定处理器数目，增加计算规模的情况下，并行系统的加速比和效率都会随之增加。 从表２可见，流场规模越大，并行计算的优越性越显著。因为此时计算规模（粒度）较大，相对于通信量占有一定的优势。由图３可见，加速比随进程数呈线性增长，这表明ＬＢＧＫＤ２Ｑ９模型的并行计算具有良好的可扩展性。 表２漉场规模固定时并行计算Ｄ２Ｑ９模型的加速比 ０８１６２４３２４０４８５６６４ ｎｕｍｏｆｐｒｏｃｅｓｓ 图３藐场规模固定时Ｄ２Ｑ９模型并行计算的加速比 ４结束语 本文讨论了ＬＢＧＫＤ２Ｑ９模型的分布式并行计算，通过大量的数值实验重点研究了数据分布方案如何与问题规模匹配，以获得更高的并行效率的问题。展示了ＬＢＧＫ模型方法良好的并行性和可扩展性。得到了二维ＬＢＧＫ模型并行计算数据分布的一般原则、交替方向Ｊａｃｏｂｉ迭代的通信策略。这些结论对进一步开展三维ＬＢＧＫ模型的并行计算及其他类似问题的并行计算有一定的指导意义。（下转第１０４页） 一１０１—万方数据 一、单选题 1、大数据的起源是（B）。 A：金融B：互联网C：电信D：公共管理 2、大数据的最明显特点是（B）。 A：数据类型多样 B：数据规模大C：数据价值密度高D：数据处理速度快 3、大数据时代，数据使用的最关键是（D）。 A：数据收集B：数据存储C：数据分析D：数据再利用 4、云计算分层架构不包括（D）。 A: Iaas B: Paas C: Saas D: Yaas 5、大数据技术是由（C）公司首先提出来的。 A：阿里巴巴B：百度C：谷歌D：微软 6、数据的精细化程度是指（C），越细化的数据，价值越高。 A：规模B：活性 C：颗粒度D：关联性 7、数据清洗的方法不包括（C） A：噪声数据清除B：一致性检查C：重复数据记录处理D：缺失值处理 智能手环的应用开发，体现了（C）的数据采集技术的应用。A：网络爬虫B：API接口C：传感器D：统计报表 9、下列关于数掲重组的说法中，错误的是（A）。 A：数据的重新生产和采集B：能使数据焕发新的光芒C：关键在于多源数据的融合和集成 D：有利于新的数据模式创新 10、美国海军军官莫里通过对前人航海日志的分析，绘制考了新的航海路线图，标明了大风与洋流可能发生的地点。这体现了大数据分析理念中的（B）。 A：在数据基础上倾向于全体数据而不是抽样数据 B：在分析方法上更注重相关分析而不是因果分析 C：在分析效果上更追究效率而不是绝对精确 D：在数据规模上强调相对数据而不是绝对数据 11、下列关于含思伯格对大数据特点的说法中，错误的是(D) A：数据规模大B：数据类型多 C：处理速度快D：价值密度高 12、当前社会中，最为突出的大数据环境是（A）A：互联网B：自然环境C：综合国力D：物联网 13、在数据生命周期管理实践中，（B）是执行方法。 A：数据存储和各份规范B：数据管理和维护C：数据价值发觉和利用D：数据应用开发和管理 14、下列关于网络用户行为的说法中，错误的是（C）。 A：网络公司能够捕捉到用户在其网站上的所有行为 B：用户离散的交互痕迹能够为企业提升服务质量提供参 C：数字轨迹用完即自动删除 D：用户的隐私安全很难得以规范保护 15、下列关于聚类挖报技术的说法中，错误的是（B）。 A：不预先设定数据归类类目，完全根据数据本身性质将数据聚合成不同类别 B：要求同类数据的内容相似度尽可能小 C：要求不同类数据的内容相仪度尽可能小 第三章互连网络 对于一颗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）通路中形成环，发生死锁 并行计算总复习 第一章： 1并行计算与串行计算在算法和编程上有哪些显著差异？ 答：·并行算法设计与并行计算机处理器的拓扑连接相关 ·并行算法设计和采用的并行计算模型有关。 ·并行计算有独自的通讯函数 ·并行算法设计时，如何将问题分解成独立的子问题是科学研究问题，并非所有的问 题都可以进行分解。 2多核与多处理机的异同点？ 多处理机：把多个处理器通过网络互连形成一个新机器。可以是专用，也可以是通用。拓扑连接是可以改变的。 多核：在过去单个处理器芯片上实现多个“执行核”。但这些执行核都有独立的执行命令集合和体系结构。这些独立的执行核+超线程SMT技术组成多核处理器 3对单处理器速度提高的主要限制是什么？ 答：晶体管的集成密度，功耗和CPU表面温度等 第二章 1 SIMD 和MIMD 所代表的计算模型是什么？主要区别和各自的系统结构示意图。SPMD的含义是什么？ SIMD指单指令多数据流模型；MIMD指多指令多数据流模型； SPMD指单程序多数据流模型，在SIMD中把指令改为程序表示每个处理器并行的执行程序。 SIMD MIMD 硬件较少处理器较多处理器 内存一个寻址系统，存储 量小多个寻址系统，存储量大 耗费较高，难开发易于开发（多个商业 组件可用） 加速高取决于应用 2 若按通讯方式对并行算法进行分类有几种分类方法，各自的特点是什么？ 基于共享地址空间：并行平台支持一个公共的数据空间，所有处理器都可以访问这些空间。处理器通过修改存储在共享地址空间的数据来实现交互。 基于消息传递：消息传递平台有p个处理节点构成，每个节点有自己的独立地址空间。运行在不同节点上的进程之间的交互必须用消息来完成，称为消息传递。这种消息交换用来传递数据、操作以及使多个进程间的行为同步。 3 在理想并行计算模型中（并行随机访问计算机parallel random access machine(PRAM), EREW, ERCW CREW, 和CRCW表示的意思是什么？ EREW：互斥读互斥写，这一类的PRAM独占访问内存单元，不允许并发的读写操作。最弱的PRAM模型，对内存访问提供最小的并发性。 CREW：并发读互斥写。对内存单元允许多读，但对内存位置多写是串行的 ERCW：互斥读并发写。对内存单元允许多写，但多读是串行的。 CRCW：并发读并发写。对内存单元允许多读多写。最强大 4 能画出多处理机系统中处理单元的基本互连结构图，Mesh, hypercube, 网络，注意对顶点 编号的要求。 第一章 1.硬件驱动力网络驱动力 2. 西摩·克雷( ) 3.约翰·麦卡锡 4.蒂姆·博纳斯·李 5.吉姆·格雷 6 7.基础设施即服务平台即服务软件即服务 8. (1) 超大规模 “云”具有相当的规模，云计算已经拥有100多万台服务器，、、微软、等的“云”均拥有几十万台服务器。企业私有云一般拥有数百上千台服务器。“云”能赋予用户前所未有的计算能力。 (2) 虚拟化 云计算支持用户在任意位置、使用各种终端获取应用服务。所请求的资源来自“云”，而不是固定的有形的实体。应用在“云”中某处运行，但实际上用户无需了解、也不用担心应用运行的具体位置。只需要一台笔记本或者一个手机，就可以通过网络服务来实现我们需要的一切，甚至包括超级计算这样的任务。 (3) 高可靠性 “云”使用了数据多副本容错、计算节点同构可互换等措施来保障服务的高可靠性，使用云计算比使用本地计算机可靠。 (4) 通用性 云计算不针对特定的应用，在“云”的支撑下可以构造出千变万化的应用，同一个“云”可以同时支撑不同的应用运行。 (5) 高可扩展性 “云”的规模可以动态伸缩，满足应用和用户规模增长的需要。 (6) 按需服务 “云”是一个庞大的资源池，你按需购买；云可以像自来水，电，煤气那样计费。 (7) 极其廉价 由于“云”的特殊容错措施可以采用极其廉价的节点来构成云，“云”的自动化集中式管理使大量企业无需负担日益高昂的数据中心管理成本，“云”的通用性使资源的利用率较之传统系统大幅提升，因此用户可以充分享受“云”的低成本优势，经常只要花费几百美元、几天时间就能完成以前需要数万美元、数月时间才能完成的任务。 云计算可以彻底改变人们未来的生活，但同时也要重视环境问题，这样才能真正为人类进步做贡献,而不是简单的技术提升。 (8) 潜在的危险性 云计算服务除了提供计算服务外，还必然提供了存储服务。但是云计算服务当前垄断在私人机构（企业）手中，而他们仅仅能够提供商业信用。对于政府机构、商业机构（特别像银行这样并行计算 - 练习题
高性能复习提纲答案
云计算复习资料
并行计算-期末考试模拟题原题
小学数学总复习简便运算400题(有答案)
云计算基础知识整理复习过程
并行算法设计与分析考题与答案
(完整版)简便运算的练习题和答案汇总
云计算期末习题含答案
MATLAB分布式并行计算服务器配置和使用方法Word版
云计算期末考试试卷及复习资料
计算机体系结构 习题与答案
LBGK模型的分布式并行计算
大数据复习题(答案)
并行计算(陈国良版)课后答案
并行计算总复习之秘笈
课后作业答案云计算与大数据
相关主题
文本预览