为什么要并行计算
 
关于并行程序，首先思考它的目的，具体来说：
 
为什么我们要不断提高性能? 因为计算能力的提升是很多邻域能够进步的核心。
为什么我们要建立并行系统？ 因为对于单处理器而言，其性能的提升实际是提高了处理器上晶体管的密度，但受限于散热问题等，密度无法一直提升。如果考虑并行化，即生产多个相对简单的完整处理器放在一个芯片上，即多核处理器，就能解决密度问题。
为什么我们要写并行程序？ 编写并行程序是为了充分发挥多核处理器的优势，然而将串行程序改写成并行程序并不顺利。
 
关于并行程序和串行程序，举一个例子，假设要计算$n$个数的值，并求它们的和。对于这个问题，串行代码解法如下：
 
sum = 0;
for (i = 0; i < n; i++) {
    x = Compute_next_value(...); // 求得x的值
    sum += x;
}
 
现假设计算机有$p$个核，且$p<<n$，那么每个核只需处理约$\frac{n}{p}$个数的求值及加和，此时代码如下：
 
my_sum = 0;
my_first_i = ...;
my_last_i = ...;
for (my_i = my_first_i; my_i < my_last_i; my_i++) {
    my_x = Compute_next_value(...);
    my_sum += my_x;
}
 
上面代码中的my_开头的变量代表了每个核的私有变量。
 
当每个核计算得到自己的my_sum后，这些核把这个结果发送给核master，由master这个核来计算总和sum：
 
if (IsMasterCore) {
    sum  = my_x;
    for each core than myself {
        receive value from core;
        sum += value;
    }
} else {
    send my_x to the master;
}
 
当然，让master完成最终的求和并不是最优解，在核数足够多的情况下，可以采取如下策略：让0号核加上1号核的值，2号核加上3号核的值，以此类推，即偶数号核加上其后一号的核对应的值；然后让0号核加上2号核的值，4号核加上6号核的值……
 
虽然最优解听上去很完美，但是却难以作为一套方案通过编写并行程序来实现。因此才会有上面提到的，改写不顺利，但不能因为不顺利就浪费掉多处理器的能力。
 
如何编写并行程序
 
这个问题取决于如何在内核间划分工作的想法。主流的划分方法有：任务并行(task-parallelism) 和 数据并行(data-parallelism)。顾名思义：
 
任务并行：不同的核分配到的任务不同，每个核各司其职，最终完成整个任务。
数据并行：每个核处理的任务相似，但是处理的数据则不同。
 
在上面提到的求值并求和的例子中，master和其余核就是任务并行的一个实例，而除了master以外的这些核在做求值和加法运算的过程就是一个数据并行的实例。
 
编写并行程序过程中需要协调的问题：
 
通信(communication）
负载均衡(load balancing)
同步(synchronization)
 
编写显式并行（explicit parallel）程序
 
这里学习三种不同的C扩展：
 
Message-Passing Interface (MPI)
POSIX threads (Pthreads)
OpenMP
 
在学习的过程中，将重点关注两种主要类型的并行系统：共享内存系统 (shared-memory system)和分布式内存系统 (distributed-memory system)。
 
在共享内存系统中，核心可以共享对计算机内存的访问；原则上，每个核都可以读写每个内存位置。（Pthreads, OpenMP）
 
在分布式内存系统中，每个核都有自己的私有内存，核必须通过通过网络发送消息之类的方式显式通信。（MPI）
 
 
上图中，图(a)是共享内存系统，图(b)是分布式内存系统。
 
并发、并行和分布式
 
 
 
在并发计算中，一个程序是指在任何时刻都可以同时进行多个任务的程序。
 
 
在并行计算中，一个程序是指多个任务紧密合作来解决一个问题的程序。
 
 
在分布式计算中，一个程序可能需要与其他程序合作来解决一个问题。
 
 
// 以上内容整理自《Introduction to Parallel Programming》一书

why ?
 
为什么要编写并行程序与构建并行系统
 The answer：单处理器的性能具有瓶颈，内部原因是因为晶体管的密度不可能无限制的增大，外部原因是因为密度增大，处理器的散热就是一个很大的问题，过于高的温度会影响性能。
 
how ?
 
Two methods：任务并行与数据并行
 在这里，用一个简单的例子来说明任务并行与数据并行之间的区别：现在有一个教授P，然后他的手下有4个助教（A,B,C,D），期末考试参加的学生有100个，然后改卷子，卷子一共有5道题目。
 首先，我们可以将教授以及他手下的主教5人看作是5个核，然后，如果每一个核负责改卷子上的某一道题目，那么这样就属于任务并行（总共有5个任务，一个核一个）。另外一个想法就是一个核负责20个学生的卷子，则这就是数据并行（总共100个数据，每一个核20个）。
 并行程序的设计过程中，要注意的问题：核之间的通信，负载平衡，同步。
 功能最强大的并行程序就是通过显式的并行结构来编写，即用扩展C和扩展C++编写。
 
what should we do ?
 
三种并行编程的方法：
 One : 消息传递接口（Message-Passing Interface MPI）
 Two : POSIX线程(POSIX threads Pthreads)
 Three : OpenMP
 为什么会有三种并行编程的实现方法：因为总的而言，并行系统可以分为2类：其中一类是共享内存系统，另外一种是分布式内存系统。Pthreads以及OpenMP是为了共享内存系统的编程而设计的，而MPI是为了分布式内存系统而设计的。
 关于共享内存系统中两种方法的主要区别是：Pthreads是比较底层的然而OpenMP是对C语言相对更高层次的扩展。

**计算机体系结构由程序设计者看到的计算机系统的属性，抽象的概念性的结构和功能属性。 
 计算机组成:是计算机体系结构的逻辑实现。 
 计算机实现:是计算机组成的物理实现。 
 重点内容 
 计算机系统的层次结构 现代并行计算机的组成 
 ü硬件核心:处理机、存储器和外围设备组成了计算机系统。 
 ü互连:外围设备可以直接或通过局域网和广域网与主机相连。 
 ü映射是一种算法结构与硬件结构相匹配的双向过程。包括处理机调度、存储器映象、处理器间的通信等..存在的问题：不能以通用和可移植方式进行并行程序设计。将着眼点放在语言执行的效率、对不同机器的可移植性、与现有的顺序语言的兼容性、并行性的表达和编程的简便性 
 改进编译器：预处理程序、预编译器、并行化编译器 
 ü预处理程序：采用顺序编译器和目标计算机的低层程序库实现高级并行结构。 
 ü预编译器：需要程序流分析、相关性检查和有限的优化来检测并行性。 
 ü联接过程的效果取决于预处理程序、预编译器、并行化编译器、加载程序 
 和操作系统支持的功效。由于程序行为的不可预测，现有的编译器在检测 
 所有类型的并行性时都不是完全自动或完全智能进行的。有效的办法：p将编译器命令插入源代码，帮助编译器做出较好的结果。这样，用户可与编译器进行交互重构，这已被证明对提高并行计算机性能是十分有用的。 
 物理结构 
 üMISD(多指令流单数据流)机在执行不同的指令流时，同一数据流通过处理机线性阵列就是所谓 流水线执行特定算法的脉动阵列(Systolic arrays)。 
 并行计算机有两大类：共享存储型多处理机、消息传递型多计算机 
 早期的超级计算机可分为： 
 流水线向量机：用带有少量带有向量硬件，但性能很高的处理机来装备. 
 SIMD计算机：强调开发大规模数据并行性 
 pSIMD计算机开发的是PE之间的空间并行性;p存储器分布的SIMD计算机由同一阵列控制部件控制的PE阵列组成;p程序和数据通过主机装入控制存储器; 
 p指令是送到控制部件进行译码;ü标量操作或控制操作，则将直接由与控制部件相连的标量处理机执行;ü向量操作，则将它广播到所有PE并行地执行;p划分后的数据集合通过向量数据总线广播到所有PE的本地存储器;pPE通过数据寻径网络互连。数据寻径网络执行PE间的通信，如移数、置换和其它寻径操作。控制部件通过执行程序来控制数据寻径网络。PE的同步由控制部件的硬件实现;p所有PE在同一个周期执行同一条指令;p可以用屏蔽逻辑来决定任何一个PE在给定的指令周期执行或不执行指令 
 共享存储器模型:是一种PE使用共享存储器的SIMD计算机。PE和存储器之间的通信网络是一个对准网络，它也受控制部件控制。 
 抽象机模型的概念与意义 
 ü并行计算机的理论模型是从物理模型抽象的； 
 ü为开发并行算法提供了一种方便的框架； 
 ü用这些模型可求得并行计算机的理论性能界限； 
 ü可在芯片制作前估算芯片区的VLSI复杂性和执行时间。 
 计算机求解一个规模为s的问题的算法复杂性取决于:Ø执行时间Ø存储空间 
 一个抽象机模型用语义属性和性能属性进行描述 
 语义属性:同构性、同步性、交互机制、地址空间、存储器模型、原子操作（不可分，有限） 
 性能属性：包括机器规模、时钟频率、工作负载、执行时间（顺序/并行）、速度、加速比、效率以及利用率等 
 语义属性具有较长的延续性，并行计算机换代时仍保持不变。 
 性能属性高度依赖系统结构平台，随着计算机换代而改变。 
 并行程序的操作类型：计算操作、并行性操作、交互操作 
 并行程序的开销源：并行性开销、通信开销、同步开销、不平衡开销 
 并行随机存取机模型 PRAM：用途:可用来开发并行算法和分析可扩展性及复杂性。MIMD、细粒度、严格同步、零开销、共享变量。特点：在PRAM上的一个并行程序由n个进程组成，其中第i个进程留驻在第i个处理器上，且由一串指令所组成。在每个基本时间步(称为周期)，每个处理器执行一条指令。指令包括数据传送、算/逻、控制流以及I/O指令，在典型的顺序计算机中均有这些指令。①规模为1的PRAM退化为传统的RAM机。这种机器为SISD机。②当处理器多于1个时，一个PRAM将访问多个数据流，且通常可执行多个指令流。因此PRAM是一个MIMD机。 MIMD的特例: 
 如果在每一周期，所有处理器必须执行相同指令，即只有一个指令流时，则PRAM就成为单指令流、多数据流(SIMD)机器。 
 SPMD计算：单程序、多数据，所有进程执行同一程序，而由进程指标加以参数化。 
 SIMD和SPMD间的差别是，在SPMD计算中，同一周期可以执行不同指令。 
 ①进程同步是严格的，任何处理器的存储器写操作或转移操作之前，必须完成其他处理器的存储器读操作。②PRAM是在指令级同步的。③实际的MIMD并行机是异步的。每个进程有自己的速率，与其他处理器进程速率无关。 在PRAM模型中，进程间通过共享变量(或共享存储器)进行交互，进程间通过共享变量进行交互的异步MIMD机，常称为多处理机。 
 进程间通过消息传递进行交互的异步MIMD机，常称为多计算机 
 ①理论PRAM模型中，所有进程对所有存储单元均有相等的访问时间。这种机器为均匀存储器访问(UMA)。②若采用非均匀存储器访问(NUMA)，将演变为异步PRAM模型（APRAM）。③ PRAM模型不合适多计算机。 
 多计算机中，每个处理机有它自己的分离地址空间。这些机器被称为具有多地址空间。正是由于此原因，多计算机的处理机间通信不是通过共享变量，而是借助消息传递。 
 存储器模型：主要目的是协调写冲突问题，有四种PRAM模型方案。 ①EREW-PRAM模型——互斥读、互斥写。禁止一台以上处理机同时读、写同一存储单元。 这是限制最大的PRAM模型。②CREW-PRAM模型——并发读、互斥写。用互斥使写冲突避免。可以并行读同一存储单元。③ERCW-PRAM模型——互斥读、并发写。允许互斥读或并行写同一存储单元。④CRCW-PRAM模型——并发读、并发写，允许在同一时刻并行读或者并行写。PRAM模型常用EREW和CRCW规则优点：PRAM模型略去很多细节，形式简单，便于开发并行程序，在此模型基础上开发的并行算法易于改进成实用的并行算法。缺点：与物理模型存在差异，实际上，这种并行计算机是不存在的。原因在于零通信开销和指令级同步的不现实假设。共享存储器的SIMD机是与PRAM模型最接近的结构 
 块同步并行模型 BSP特点：（1）一个BSP程序有n个进程，每个驻留在一个结点上。基本时间单位是周期(或时间步)。（2）程序按严格的超步序列执行。（3）同步路障迫使进程等待。（4）BSP计算机是MIMD系统。（5）BSP模型是超步级的松同步。（6）在一个超步中，不同进程以不同速率异步执行。（7）BSP模型交互机制是共享变量或是消息传递。 
 h关系的定义：（1）一个h关系是任何通信操作的抽象，在其中，每个结点最多发出h个字到各结点，并且每个结点最多接收h个字。（2）在一个BSP计算机中，实现任何h关系的时间不会超过gh个周期，g是由机器平台决定的一个常数。一个超步执行时间的确定计算时间w：处理器中完成计算操作所需的最大周期数；路障同步开销为L；通信开销为gh周期，g是实现h关系的比例系数，常数；执行一个超步的时间为:w+gh+L 
 优点：与PRAM模型相比，BSP模型更为实际，更接近物理模型，BSP模型除了用于进程管理的并行性开销外，它考虑了所有其他开销 
 阶段并行模型基本描述：一个并行程序以一系列阶段加以执行，当前阶段的所有操作未完成之前，不能开始下一阶段操作 
 三类阶段的定义：并行化阶段主要涉及进程管理的开销阶段；计算阶段一个或多个处理器执行若干局部计算操作；交互阶段完成交互操作所执行的任务。。特点：不同的计算阶段可以不同的工作速度执行不同的工作负载；不同的交互操作可取不同的时间 
 可扩展性范围包括资源可扩展性是指通过增加处理器数、更多的存储部件(高速缓存，主存，磁盘)以及增加软件等方法，使系统具有更高性能或功能。涉及三方面：Ø规模可伸缩性、Ø资源扩展、Ø软件可扩展性。 
 ü当前的并行计算机规模的扩展：Ø加入更多处理器、Ø增加互连网络、接口以及通信软件在内的子系统、有效地利用更大并行性，即如何为扩大的系统进行编程 
 ü计算机系统中发展最快的部件是处理器进展最慢的部分是程序设计语言 
 SMP和MMP只具有有限的空间可扩展性；ü因特网则具有最好的空间可扩展性 
 可扩展设计原理：ü独立原理ü平衡设计原理ü可扩展性设计原理、时延隐藏原理 
 独立原理：应努力使系统中的各个组成部分（硬、软件）相互独立如果无法达到完全独立，则应尽力使相关程度减至最小并使相关性尽量清晰。优点：ü使独立扩展成为可能，ü使异构可扩展性成为可能、要求部件不受制于一个特别的体系结构或系统 
 ü消息传递接口(MPl)是使用少量独立(正交)语言特征的成功范例。üMPI基于4个相互正交的主要概念：数据类型、通信操作、通信子集、虚拟拓扑 
 实现独立原理的两种通用技术：ü将体系结构和实现分开、ü使用标准组件 
 平衡设计原理：ü应努力最小化任何性能瓶颈ü应避免不平衡系统的设计ü应避免单点失效，即一个部件失效将使整个系统崩溃 
 Amdahl法则：处理速度应与存储器容量和I／O速度相平衡 实现：ü粗略地估计每秒一百万指令(MIPS)的计算速度，应与1MB存储器容量和1Mb/s的I/O速率相平衡 
 并行系统50％法则ü并行程序性能取决于：Ø负载不平衡;Ø并行化开销;Ø通信启动开销(t0);Ø以及每字节通信开销（tc）；ü50％法则：4个开销因素的每一个使性能衰减都不大于50％，那么就认为此并行系统是平衡的 
 单结点速度P1”表示的是“计算速度”；“渐进带宽r∞=1/tc”表示的是“通信速度”。 
 设计“平衡的”由两个慢速部件（处理器速度、网络速度）构成的系统。优于设计“不平衡的‘一个快速（处理器速度）一个慢速（网络速度）构成的系统。平衡设计可以改善系统的性能 
 ü计算机系统设计理念：Ø在设计一个可扩展的系统时，应该从一开始就将可扩展性作为主要目标，而不是设计完成后再来考虑这一问题。Ø为系统将来可能扩展以提供更高性能或缩小以使价格降低或是有更大的成本有效性作好准备。 
 可扩展性设计的两种流行方法：过度设计、向后兼容性 
 过度设计：是指系统在设计时不单纯地只是为了满足目前系统的最低需要，设计必须包括一些附加特性，以期在未来的扩展系统中性能得到改进 
 ü地址空间大小：即处理器能直接访问的字节单元数。 
 向后兼容性：在设计硬件或软件部分时，必须兼顾缩减系统的需求。向后兼容性并不表示一个旧系统的所有特性都应保留。应该剔除陈旧的特性，在应用过度设计技术时，应考虑成本问题且不应对未来期待过多，虽然有时过度设计确实能减少总的开发和生产成本。 
 缺少合适的并行软件是阻碍主流用户接纳并行计算的主要原因。并行系统软件和应用软件不仅数量很少,而且功能性也相当原始。困难：p并行编程中有许多不同的模型是一个更复杂的智力活动。并行程序的环境要比串行程序落后得多 
 编程模型（虚）即是程序员在开发一个并行程序时所见到和使用的模型。自然模型（实）是由一个特定并行计算机平台所提供的、用户可见的最低层的编程模型，其他的编程模型可在此自然模型上加以实现 
 环境工具是指任何硬件和软件的实用程序，以帮助用户程序的开发和执行，ü是那些通常与操作系统或程序设计语言无关的工具集 
 ü大多数程序基于命令式机器模型，中心概念是状态更新ü一个命令式程序可看成是一个状态机(或一个自动机) 
 程序变量集：数据变量、控制变量 
 ü开始时，进程为不存在状态。当它的创建者，父进程执行进程创建操作后，它才出现。一个新创建的子进程准备执行，但仅在被调度后，它方可开始运行(执行其代码)。 
 ü重量级的并行进程不适用于可扩展并行计算机，除非并行进程具有粗计算粒度。要开发较细粒度并行性，必须使用轻量级进程 
 OS进程和线程间的主要差别：在重量级的OS进程中，多个线程能共存于进程(包括进程描述符)的同一地址空间，并且共享；当创建一个(重量级)进程时，通常它有一个单线程，称为基本线程；通过执行一个线程创建操作，任何进程能创建另外的线程 
 颗粒度是指在两次并行性操作之间所执行的计算负载。 
 单线程：从程序员的观点，一个数据并行程序中由一个进程执行，具有单一控制线；使得一个数据并行程序就像一个顺序程序。并行操作子聚合数据结构上：数据并行程序的一个单步(语句)，可指定同时作用在不同数据组元素或其他聚合数据结构上的多个操作；松散同步(LooselySynchronous)：在数据并行程序的每条语句之后，均有一个隐含的同步，这种语句级的同步是松散的(相对于SIMD机器每条指令之后的紧同步而言)；全局命名空间：数据并行程序中的所有变量均驻留在单一地址空间内，所有语句可访问任何变量，只要满足通常的变量作用域规则；隐式相互作用：因为数据并行程序的每条语句之末存在着一个隐含的路障，所以不需要一个显式同步；通信可由变量指派而隐含地完成。隐式数据分配：程序员不必要明确地指定如何分配数据，可将改进数据局部性和减少通信的数据分配方法揭示给编译器 
 分别对应数据并行模型 消息传递模型 共享变量模型 
 并行程序的并行度(degree of parallelismDOP)通常定义为可同时执行的分进程数。 
 颗粒度;指在两次并行性操作或交互操作之间所执行的计算负载 
 通信操作类型：数据交换、同步操作、聚集操作 
 宏基准程序 
 NPB基准程序组由5个核心(EP、MG、CG、FT和IS)和3个模拟应用(LU、SP和BT)程序组成。 
 核心程序：EP 基准程序、MG基准程序、CG基准程序、FT基准程序、IS基准程序。模拟应用程序：BT、LU、SP 
 PARKBENCH基准程序组：低层基准程序、核心基准程序、压缩应用基准程序、HPF编译器基准程序 
 并行STAP程序组：APT、HO-PD、BM、EL等4个基准程序的结构 
 用户经常提到6种性能：执行时间；速度;吞吐率；利用率;成本有效性;性能／成本比 
 工作负载（W）：是程序中的计算操作数 Ppeak：是处理器的峰值速度 
 处理速度;是指单位时间的工作负载（W)的处理,W 表示“工作负载”，其单位是“Mflop(兆 
 浮点运算)”,处理速度：Pn=W/Tn,其单位是Mflop／s 
 提高系统吞吐率的两个方法:流水化、无相关的分配 
 利用率 Un=Pn/(nPpeak)指一个给定计算机实际可达到速度与峰值速度之比 
 成本有效性：单位成本实现的工作负载。衡量单位： Gflop／$ 
 3个指标来测量程序C的计算工作负载：执行时间；执行的指令数；执行的浮点操作数； 
 存储器层次结构的主要指标：存储器容量、存储器时延、存储器带宽 
 并行性开销的来源：进程管理、分组操作、进程查询操作。交互开销的来源：同步、聚集、通信
 
并行程序中的开销可分为3类：负载不平衡开销、并行性开销、交互开销。执行一个并行程序所需的时间为： T= Tcomp+Tpar+Tinteract 
 并行性开销的来源：进程管理、分组操作、进程查询操作 
 交互开销来源：同步、聚集、通信 
 数据并行：在理想环境下于每个时钟内可并发地执行500到3500个算术操作。 
 指令级并行：并行度较低。指令级并行性的极限约在5左右，很少超过7。一个合理设计的超标量处理器上，可期待每周期并发执行2.0到5.8条指令。 
 加速比分析： 
 n是并行系统中处理器数。W是问题规模（给定问题的总计算量)Ws=W1为顺序工作负载，Wp为并行工作负载 。为顺序分量比例，=Ws/W；1-为并行分量比例Ts=T1为顺序执行时间，Tp为并行执行时间。S为加速比；E为效率。 
 考虑开销的加速比说明： 
 并行加速比不仅受限于程序的顺序分量，而且也受并行程序运行时的平均开销影响。 
 Amdahl定律结论：固定负载加速比随顺序瓶颈α和平均开销的增加而急剧下降。顺序瓶颈问题不能用单纯增加机器规模（处理器数目）的办法来解决。 
 存储受限的加速定律：基本思想：只要存储空间许可，应尽量增大问题规模，以产生更好和更精确的解(此时可能使执行时间略有增加) 
 受限存储器加速比定义：此时工作负载仍然表示为W=αW+(1-α)W。Ø令因子G(n)反应存储容量增加到P倍时工作负载的增加量，扩大后的工作负载为:W’=αW+(1-α)G(n)W**

一、选择题（每小题2分，共20分）
 1、按照结点间连接的性质，互联网络的拓扑结构可以分为___________三类。
 ①静态拓扑结构 ②动态拓扑结构 ③混合拓扑结构 ④宽带互联网络
 A.①②③ B.①②④ C.②③④ D.①③④
 2、并行算法按照进程间程序的执行顺序关系可以分为同步算法、异步算法和___________。
 A.独立并行算法 B.混合算法 C.加速算法 D.级联算法
 3、常用的三个加速比性能模型包括___________。
 ①固定负载加速比性能模型 ②固定时间加速比性能模型
 ③存储受限加速比性能模型 ④固定速度加速比性能模型
 A.①②④ B.①③④ C.②③④ D.①②③
 4、研究并行算法的可扩展性的目的是___________
 ①确定某类问题的何种并行算法与何种并行系统的组合，可有效的利用系统大量处理机
 ②有算法在小规模并行机上的运行性能来预测起移植到大规模并行机上后的运行性能
 ③对一固定规模的问题，能确定起运行在某类并行系统上时，所需的最有处理机台数和获得的最大加速比
 ④指导并行算法和并行机体系结构的改进
 A.①②③ B.②③④ C.①②③④ D.①③④
 5、LogP模型是异步的，假设所有消息都很短，LogP模型中参数g表示__________。
 A.源处理机与目标处理机之间进行消息通信所需等待的延迟时间的上限
 B.一台处理机连续进行消息发送或接收时的最小时间间隔
 C.处理机用于发送或者接受每个消息的时间开销
 D. 处理机或处理模块的数量
 6、BSP模型是以三个参数描述____________的多计算模型，在BSP模型中，计算由一系列用全局同步器分开的周期为L的超级步组成。
 A.快速存储 B.同步存储 C.共享存储 D.分布式存储
 7、MPI中收集操作将消息从多个进程收集到一个进程上，该函数为_________。
 A.MPI_BARRIER B.MPI_GATHER C.MPI_SCATTER D.MPI_REDUCE
 8、Matlab提供的实现并行循环计算功能的内部函数为___________。
 A.pmode B.for-drange C.parfor D.spmd
 9、在Matlab环境下___________负责管理客户端提交的job，为job的各个task分配工作单元，向客户端返回执行结果。
 A.scheduler B.worker C.client D.lab
 10、在Matlab环境下，关于临时变量描述错误的是_________。
 A.在每个worker每次执行循环之前都对临时变量重新赋值
 B.如果变量在parfor循环体内被赋值且变量的索引与循环变量无关，此类变量称为临时变量
 C.临时变量必须在循环体内赋值
 D.临时变量对parfor循环体外的同名变量产生影响
 二、判断题（正确写对，错误写错，每小题2分，共10分）
 11、Flynn(1966年)分类法是根据系统的指令流和数据流对计算机系统进行分类的一种方法，将并行计算机分为SISD、SIMD、MISD和MIMD系统。并行计算机系统除少量专用的SIMD系统外，绝大部分为MIMD系统。_________
 12、可以将问题规模大致分为输入输出规模、计算规模、内存需求规模和通信（同步）规模。_________
 13、并行算法设计中的平衡树方法适合处理链表、无向图等数据结构，经常应用于通信系统中。_________
 14、MPI是一个库，因此其使用可以和特定的语言结合也可以独立使用。_________
 15、在Matlab环境下，pmode与spmd并行结构的主要区别在于pmode只能执行并行程序，而spmd并行结构可混合串行和并行程序。_________
 
三、填空题（每小题2分，共10分）
 16、科学与工程计算对并行计算的需求是十分广泛的，但所有的应用问题都可以概括为计算密集型问题、_________ 问题和网络密集型问题。
 17、人们对计算机系统结构进行改进，主要围绕增加同一时间间隔的 ，即并行处理技术。
 18、分治策略是将原问题分成若干个特征相同的子问题分别处理。常见的分治策略有任务分割和___。
 19、利用MPI_Send可以发送数据，其函数为MPI_Send(buf,count, _________, dest,
 tag,comm)。
 20、在SPMD并行结构中，用户可以由____________获得每个worker的编号。
 
四、简答题（每小题5分，共10分）
 21、简要叙述并行计算的研究目标和研究内容。
 22、简要叙述并行计算模型的作用。
 五.程序填充题（每小题10分，共10分）
 23、Arnoldi算法是一种求解线性代数方程组的常用迭代算法，结合算法的具体步骤，将如下程序补充完整。Arnoldi算法描述时可能用到公式：①
 ,②
 ,③
 ,④
 。
 function xx=arnoldi(aa,bb)
 [m,n]=size(aa);
 v0=ones(m,1);
 v(:,1)= v0/ ; % 向量单位化
 m0=3;
 h=zeros(m0,m0);
 for j=1:m0
 for i=________________
 h(i,j)=sum(aav(:,j). _________;
 end
 w(:,j)=aa*v(:,j)-hv(j,h(1:j,j),v(:,1:j)); %函数hv已经给出
 h(j+1,j)= _________;
 if h(j+1,j)==0
 break
 end
 v(:,j+1)= _________;
 end
 六、综合题（每小题10分，共40分）
 24、Cannon算法由于具有很好的负载平衡，是计算矩阵乘法
 的一种常用并行算法，给出该方法每一轮次数据的存储位置和所进行的具体运算（处理器台数，和是12维方阵）。其中矩阵，矩阵B 、矩阵C采用类似划分块。
 25、稀疏矩阵可以采用CSR格式进行压缩存储，给出下面稀疏矩阵的行压缩存储表示(即给出)。
 
 
26、FOM算法是一种求解线性代数方程组的常用并行迭代算法，结合如下公式给出该算法的具体步骤。可能用到公式①，②，③。
 27、线性代数方程组求解是科学与工程计算中经常遇到的一类问题，考虑对下三角方程组的并行求解，其中，。如果利用卷帘存储方式，采用分布式系统进行计算，给出以处理器台数为，时各处理器执行的运算和相应的操作。