并行考试复习知识点

考试题型：名词解释〔5~6个〕，简答〔4~5〕，画图〔17分〕，并行算法〔40分〕第一章绪论1.什么是并行计算？并行计算〔parallelcomputing〕是指，在并行机上，将一个应用分解成多个子任务，分配给不同的处理器，各个处理器之间相互协同，并行地执行子任务，从而到达加速求解速度，或者求解应用问题。大任务大任务分解多个子任务不同处理单元分给快速求解协同合作根本条件：硬件〔并行机〕、并行算法设计、并行编程环境主要目标：提高求解速度，扩大问题规模并行计算的三个根本条件：(1)并行机。并行机至少包含两台或两台以上处理机，这些处理机通过互连网络相互连接，相互通信。(2)应用问题必须具有并行度。也就是说，应用可以分解为多个子任务，这些子任务可以并行地执行。将一个应用分解为多个子任务的过程，称为并行算法的设计。(3)并行编程。在并行机提供的并行编程环境上，具体实现并行算法、编制并行程序，并运行该程序，到达并行求解应用问题的目的。并行计算的主要研究内容：(1)并行机的高性能特征抽取。(2)并行算法设计与分析。(3)并行实现技术，主要包含并行程序设计和并行性能优化。基于并行机提供的并行编程环境，例如消息传递平台MPI或者共享存储平台OpenMP，具体实现并行算法，研制求解应用问题的并行程序。(4)并行应用。2.并行计算和分布式计算的区别，不同：并行计算不同于分布式计算〔distributedcomputing〕分布式计算主要是指，通过网络相互连接的两个以上的处理机相互协调，各自执行相互依赖的不同应用，从而到达协调资源访问，提高资源使用效率的目的。但是，它无法到达并行计算所倡导的提高求解同一个应用的速度，或者提高求解同一个应用的问题规模的目的。对于一些复杂应用系统，分布式计算和并行计算通常相互配合，既要通过分布式计算协调不同应用之间的关系，又要通过并行计算提高求解单个应用的能力。3.各种结构画图，概念，特点，以及两两之间的差异：大型并行计算机〔scalable-parallelComputer〕可分为:单指令多数据流机SIMD并行向量处理机PVP对称多处理机SMP大规模并行处理机MPP分布式共享存储DSM多处理机工作站机群COW〔1〕DSM〔DistributedSharedMemory〕分布式共享存储〔2〕MPP〔MassivelyParallelProcessing〕大规模并行处理结构每个结点相对独立，有一个或多个微处理器每个结点均有自己的操作系统各个结点自己独立的内存，防止内存访问瓶颈各个结点只能访问自己的内存模块扩展性较好〔3〕对称多处理机SMP:采用商用微处理器，通常有片上和片外Cache，基于总线连接，集中式共享存储，UMA结构。优点：对称性单地址空间，易编程性，动态负载平衡，无需显示数据分配高速缓存及其一致性，数据局部性，硬件维持一致性低通信延迟，Load/Store完成问题：欠可靠，BUS,OS,SM通信延迟〔相对于CPU〕，竞争加剧慢速增加的带宽〔MBdouble/3年,IOB更慢〕不可扩放性---〉CC-NUMASMP〔4〕NOW〔NetworkofWorkstations〕工作站机群也称为COW〔ClusterofWorkstations〕，与MPP之间的界限越来越模糊。每个结点都是一个完整的工作站，有独立的硬盘与UNIX系统结点间通过低本钱的网络〔如千兆以太网〕连接每个结点安装消息传递并行程序设计软件，实现通信、负载平衡等投资风险小、结构灵活、可扩展性强、通用性好、异构能力强，被大量中小型计算用户和科研院校所采用存在的问题：通信性能，并行编程环境。工作站集群COW结构图，如下：NOW的典型代表：Beowulfcluster微机机群，如下列图：〔5〕Cluster机群每个结点含多个商用处理器，结点内部共享存储采用商用机群交换机通过前端总线连接结点，结点分布存储各个结点采用Linux操作系统、GNU编译系统和作业管理系统属性PVPSMPMPPDSMCOW结构类型MIMDMIMDMIMDMIMDMIMD互联网络交叉开关交叉开关，总线定制网络定制网络商业化网络通信机制共享变量共享变量消息传递共享变量消息传递地址空间单地址空间单地址空间多地址空间单地址空间多地址空间系统存储器集中共享集中共享分布非共享分布共享分布非共享访存模型UMAUMANORMANUMANORMA可扩展并行计算机开展正趋于三种系统结构：无共享体系结构共享磁盘体系结构共享存储器体系结构4.微机处理器的多级存储结构,cache〔应该没有〕微处理器主频越来越高，内存容量越来越大，但内存访问速度的增长较慢缓解内存墙性能瓶颈：Cache高速缓存第二章流水线处理机和向量处理机5.流水线的原理5条指令顺序执行20Δt;现8ΔT即可完成,如完成一条指令的时间为T,把一条指令解释分解成时间相等的M个子过程,那么每隔Δt=T/m就可以处理一条指令，最大吞吐率提高。6.流水线的各种分类方法以及分类。按流水处理的级别分类按流水线完成功能的多少分类按流水不同功能的联接切换方式分类按处理的数据类型分类按流水线的结构分类其它类型1〕按流水处理的级别分类部件级流水:指构成部件内的各个子部件之间的流水处理机级流水:指构成处理机的各个部件之间的流水系统级流水:指构成计算机系统的多个处理机之间的流水2〕按流水线完成功能的多少分类单功能流水线----只能实现一种功能的流水处理。多功能流水线指----同一流水线的各个段之间可以有多种不同的联接方式以实现多种不同的运算或功能。3〕按流水不同功能的联接切换方式分类静态流水线----在某一时间里各段只能按一种功能联接流水，只有等流水线全部流空后才能切换成按另一种功能来联接流水。动态流水线----各功能段在同一时间内可按不同运算或功能联接目前，高性能流水处理机大多都采用多功能静态流水静态多功能流水线时空图4〕按处理的数据类型分类标量流水处理机：没有向量数据表示，只能对标量进行处理.向量流水处理机：机器具有向量数据表示，设置有向量指令和向量运算硬件，能对向量的各个元素流水地处理。5〕按流水线的结构分类线性流水----各段串行联接，没有反应回路，各段只经过一次。非线性流水----流水线中除有串行联接的通路外.还有某种反应回路，使一个任务流经流水线时，需要屡次经过某个段或跳过某些段，称非线性流水。图为：非线性流水线6〕其它类型可大量采用，用硬件来实现复杂的多维流水线，同时设多个方向脉动地向前推进，以进一步提高流水的并行处理能力。第三章阵列处理机7.什么是阵列处理机，及其特殊应用。阵列处理机属于SIMD并行机，多台处理机〔既处理单元PE〕排成阵列，利用资源重复的方法开拓并行性。单一的指令运行在大型的数据结构〔如数组和矩阵等〕上，所以也叫做数据并行结构〔DataParallelArchitecture〕。阵列机的根本结构：〔控制单元，管理单元〕阵列处理机通常由一个控制单元CU〔ControlUnit〕，n个处理单元PE〔ProcessingElement〕,m个存储模块M和一个互连网络IN(InterconnectionNetwork)所组成。SC是管理处理机。CU将单一指令流播送至各个PE，而所有活动的PE将从相应的M中取出各自所需的数据元素〔多数据流〕，以同步的方式执行该条指令。阵列机中，IN也常叫做对准(Alignment)或置换(Permutation)网络，它用来提供各PE之间或PE与M之间的通信连接。按以存储模块的分布方式不同，阵列机可分为两种根本组态：分布存储的阵列机：处理器----处理器组态〔也称为闺房式〕共享存储的阵列机：处理器----存储器组态〔也称为舞厅式〕阵列机的主要特点：使用资源重复的方法来开拓计算问题的空间上的并行性；所有PE必须同时进行相同的操作，计算是同步的，也叫同步计算；该类结构是以某一类算法为背景开展起来的计算机，使用简单、规整的互连网络来实现PE间的通信，限定了所适用的求解问题的算法的类型，所以阵列机的研究必须与并行算法密切结合。阵列机是一种专用的计算机，尤其适合求解有限差分、矩阵运算、信号处理、图像处理，线性规划等一类计算问题。阵列机的特殊应用：〔？？？〕阵列处理机是一个异构型多处理机系统：1.专门对付数组运算的处理单元阵列组成的处理机；2.专门从事处理单元阵列的控制及标量处理的处理机；3.专门从事系统输入输出及操作系统的处理机。8.网络拓扑的一些概念：网络直径—(diameter)D；网络中任意两个结点间最短路径的最大值。路径长度用遍历的链路数来度量。结点度—(nodedegree)d；与结点相连接的链路〔边〕数。反映了结点所需的I/O端口数，也反映了结点的价格。等分宽度—当某一网络被切成相等的两半时，沿切口的最小边数(通道)称通道等分宽度。对称网络—从任何结点看拓扑结构都是一样。数据寻径功能—数据寻径网络用来进行PE间数据交换。〔静、动〕第四章多处理机9.多处理机的概念MIMD并行计算机结构模型：对称多处理机SMP的特点：〔1〕对称性。系统中任何处理器都可以访问共享存储器的任何存储单元和I/O设备，且具有相同的访存时间。因此，SMP结构也称为均匀存储访问〔UMA〕结构。〔2〕单一物理地址空间。共享存储器的所有存储单元都按单一地址空间编址。〔3〕高速缓存一致性。多级高速缓存支持数据局部性，而且用硬件自动实现高速缓存一致性。〔4〕低通信延迟。处理器之间的通信采取对共享存储单元使用简单的读/写指令来完成，因此，通信的时间延迟很低。〔详见第四章课件〕多处理机：具有两个以上的处理机，在操作系统控制下，通过共享的主存或输入/输出子系统或高速通讯网络进行通讯。10.多处理机与阵列机的区别：多处理机属于多指令流多数据流系统，与单指令流多数据流系统的阵列处理机相比：在结构上:它的多个处理机要用多个指令部件分别控制，通过机间互连网络实现通讯；在算法上:不限于向量数组处理，还要挖掘和实现更多通用算法中隐含的并行性；在系统管理上:要更多地依靠软件手段有效地解决资源分配和管理，特别是任务分配、处理机调度、进程的同步和通讯等问题。从以下几个方面，主要说明其差异：结构灵活性阵列处理机的结构主要是针对向量、数组处理设计的，有专用性。处理单元数虽然已达6384以上，却只需要设置有限、固定的机间互连通路就可满足一批并行度很高的算法的需要。多处理机是实现作业、任务、程序段的并行，为适应多样的算法，结构应更灵活多变，以实现复杂的机间互连，防止争用共享的硬件资源。这是多处理机机数少的原因之一。程序并行性阵列处理机实现操作级并行，一条指令即可对整个数组同时处理，并行性存在于指令内部，识别比拟容易，可以从指令类型和硬件结构上提供支持，由程序员编程时加以利用，或由向量化编译程序来协助。多处理机中，并行性还存在于指令外部，处理多个任务间的并行，加上系统要求通用，使程序并行性的识别较难，必须利用算法、程序语言、编译、操作系统以及指令、硬件等多种途径，挖掘各种潜在的并行性，而不是主要依靠程序员在编程时解决。并行任务派生阵列处理机是通过指令来反映数据间是否并行计算，并由指令直接启动多个处理单元并行工作。多处理机是指令流，需要有专门的指令或语句指明程序中各程序段的并发关系，并控制它们并发执行，使一个任务执行时可以派生出与它并行执行的另一些任务。派生出的并行任务数目随程序和程序流程的不同而动态变化，并不要求多处理机像阵列处理机那样用固定的处理器加屏蔽的方法来满足其执行的需要。如果派生出的并行任务数多于处理机数，就让那些暂分配不到空闲处理机的任务排队，等待即将释放的处理机。反之，那么可以让多余的空闲处理机去执行其它的作业。因此多处理机较阵列处理机运行的效率要高些。进程同步阵列处理机实现的是指令内部对数据操作的并行，所有活泼的处理单元在同一个控制器控制下，同时执行同一条指令，工作自然是同步的。多处理机实现的是指令、任务、作业级的并行，同一时刻，不同处理机执行不同指令，工作进度不会也不必保持一致。但如果并发程序之间有数据相关或控制依赖，就要采取特殊的措施同步，使并发进程能按所需的顺序执行。资源分配和任务调度阵列处理机主要执行向量数组运算，处理单元数目是固定的。程序员编写程序时，利用屏蔽手段设置处理单元的活泼状态，就可改变实际参加并行执行的处理单元数目。多处理机执行并发任务，需要处理机的数目没有固定的要求，各个处理机进入或退出任务以及所需资源的变化情况要复杂得多。这就需要解决好资源分配和任务调度，让处理机的负荷均衡，尽可以提高系统硬件资源的利用率，管理和保护好各处理机、进程共享的公用单元，防止系统死锁。这些问题解决的好坏将会直接影响系统的效率。第五章机群的分类，体系结构11.机群的概念一组独立的计算机〔节点〕的集合体，节点间通过高性能的互连网络连接；各节点除了可以作为一个单一的计算资源供交互式用户使用外，还可以协同工作，并表现为一个单一的、集中的计算资源，并行计算任务使用。机群的重要特征：机群的各节点都是一个完整的系统，节点可以是工作站，也可以是PC机或SIMD机；互连网络通常使用商品化网络，如以太网、FDDI、ATM、光纤通信等，局部商业机群也采用专业网络互连；网络接口与节点的I／O总线松耦合相连；各节点有一个本地磁盘；各节点有自己的完整的操作系统。12.机群的分类根据不同的标准，机群可有多种分类方式。根据应用目标：高性能机群〔HPCluster〕和高可用性机群〔HACluster〕根据节点的拥有情况：专用机群〔Dedicatescluster〕和非专用机群〔Nondedicatedcluster〕根据节点的硬件构成：PC机群COPC〔ClusterofPCs〕，工作站机群COW，对称多处理机SMP机群Clumps〔ClusterofSMPs〕.根据节点的操作系统：Linux机群〔如Beowulf〕，Solaris机群〔如BerkeleyNow〕，NT机群〔如HPVM〕，AIX机群〔如IBMSP2〕根据节点的配置：同构机群—各节点有相似的体系，并使用相同的操作系统。异构机群—节点可以有不同的体系，运行的操作系统也可不同。从综合比拟角度机群分为两类：专用形—紧耦合、同构、通过一个前端系统进行集中式管理，常用来替代传统的大型超级计算机系统。企业型—松耦合、由异构节点构成，节点可以有多个属主，机群管理者对节点有有限的管理权。13.机群的体系结构1〕机群节点连接方式：机群节点有三种连接方式，如图5.1所示。最常见的是无共享机群，节点间通过I/O总线连接；共享磁盘〔SharedDisk)的体系常用于注重可用性的商用小规模机器上，在节点失效时能由其他节点承当失效节点的工作；共享存储器的机群节点通过存储总线连接，由于比前两种机群难于实现，还没有得到广泛的应用。2)机群的理想体系结构①多个高性能节点：如PC、工作站、SMP等；②目前最新的〔State-of-the-art〕操作系统：如基于层次结构或基于微内核的操作系统；③高性能互连网络：如千兆位的以太网或Myrinet；④快速通信协议和效劳：如主动消息AM或快速消息FM；⑤机群中间层：包括单一系统映像和系统可用性低层结构；⑥并行编程环境和工具：如编译器、MPI、PVM等；⑦应用：包括串行应用和并行应用。并行计算第三章1.网络性能指标〔不确定考〕节点度〔NodeDegree〕：射入或射出一个节点的边数。在单向网络中，入射和出射边之和称为节点度。网络直径〔NetworkDiameter〕：网络中任何两个节点之间的最长距离，即最大路径数。对剖宽度〔BisectionWidth〕：对分网络各半所必须移去的最少边数对剖带宽〔BisectionBandwidth〕:每秒钟内，在最小的对剖平面上通过所有连线的最大信息位〔或字节〕数如果从任一节点观看网络都一样，那么称网络为对称的〔Symmetry〕2.膨胀系数将网络中的各节点映射到另一个网络中去。用膨胀〔Dilation〕系数来描述嵌入的质量，它是指被嵌入网络中的一条链路在所要嵌入的网络中对应所需的最大链路数。如果该系数为1，那么称为完美嵌入。3.加速度比性能三定律〔不确定考〕详见课件Amdahl定律Gustafson定律SunNi定律可扩放性评测标准等效率度量标准等速度度量标准平均延迟度量标准第四章并行算法设计4.什么是并行算法，及其分类。并行算法：一些可同时执行的进程的集合，这些进程互相作用和协调动作从而到达给定问题的求解。并行算法的分类：数值计算和非数值计算同步算法和异步算法分布算法确定算法和随机算法5.并行算法的同步〔应该不考〕同步概念：同步是在时间上强使各执行进程在某一点必须互相等待；可用软件、硬件和固件的方法来实现。同步语句例如：算法4.1共享存储多处理器上求和算法输入：A=(a0,…,an-1),处理器数p输出：S=ΣaiBegin(1)S=0(2.3)lock(S)(2)forallPiwhere0≤i≤p-1doS=S+L(2.1)L=0(2.4)unlock(S)(2.2)forj=itonsteppdoendforL=L+ajEndendforendfor6.并行算法的通讯通讯：共享存储多处理器使用：globalread(X,Y)和globalwrite(X,Y)分布存储多计算机使用：send(X,i)和receive(Y,j)通讯语句例如：算法4.2分布存储多计算机上矩阵向量乘算法输入：处理器数p,A划分为B=A[1..n,(i-1)r+1..ir],x划分为w=w[(i-1)r+1;ir]输出：P1保存乘积AXBegin(1)Computez=Bw(2)ifi=1thenyi=0elsereceive(y,left)endif(3)y=y+z(4)send(y,right)(5)ifi=1thenreceive(y,left)End7.并行计算的模型概念，定义1〕PRAM模型根本概念：由Fortune和Wyllie1978年提出，又称SIMD-SM模型。有一个集中的共享存储器和一个指令控制器，通过SM的R/W交换数据，隐式同步计算。结构图：PRAM-CRCW分类PRAM-CRCW并发读并发写CPRAM-CRCW(CommonPRAM-CRCW)：仅允许写入相同数据PPRAM-CRCW(PriorityPRAM-CRCW)：仅允许优先级最高的处理器写入APRAM-CRCW(ArbitraryPRAM-CRCW)：允许任意处理器自由写入PRAM-CREW并发读互斥写PRAM-EREW互斥读互斥写优点：适合并行算法表示和复杂性分析，易于使用，隐藏了并行机的通讯、同步等细节。缺点：不适合MIMD并行机，忽略了SM的竞争、通讯延迟等因素2〕异步APRAM模型根本概念：又称分相〔Phase〕PRAM或MIMD-SM。每个处理器有其局部存储器、局部时钟、局部程序；无全局时钟，各处理器异步执行；处理器通过SM进行通讯；处理器间依赖关系，需在并行程序中显式地参加同步路障。指令类型：(1)全局读(2)全局写(3)局部操作(4)同步计算过程：由同步障分开的全局相组成优缺点：易编程和分析算法的复杂度，但与现实相差较远，其上并行算法非常有限，也不适合MIMD-DM模型。3〕BSP模型根本概念：由Valiant(1990)提出的，“块〞同步模型，是一种异步MIMD-DM模型，支持消息传递系统，块内异步并行，块间显式同步。模型参数：p：处理器数(带有存储器)l：同步障时间(Barriersynchronizationtime)g：带宽因子(timesteps/packet)=1/bandwidth计算过程：由假设干超级步组成，每个超级步计算模式为下列图：优缺点：强调了计算和通讯的别离，提供了一个编程环境，易于程序复杂性分析。但需要显式同步机制，限制至多h条消息的传递等。4〕logP模型根本概念：由Culler(1993)年提出的，是一种分布存储的、点到点通讯的多处理机模型，其中通讯由一组参数描述，实行隐式同步。模型参数：L：networklatencyo：communicationoverheadg：gap=1/bandwidthP：#processors注：L和g反映了通讯网络的容量优缺点：捕捉了MPC的通讯瓶颈，隐藏了并行机的网络拓扑、路由、协议，可以应用到共享存储、消息传递、数据并行的编程模型中；但难以进行算法描述、设计和分析。第五章并行算法的一般设计方法8.快排算法的并行化算法5.2PRAM-CRCW上的快排序二叉树构造算法输入：序列(A1,…,An)和n个处理器输出：供排序用的一棵二叉排序树Begin(1)foreachprocessorido(2)repeatforeachprocessori<>rootdo(1.1)root=iif(Ai<Afi)∨(Ai=Afi∧i<fi)then(1.2)fi=root(2.1)LCfi=i(1.3)LCi=RCi=n+1(2.2)ifi=LCfithenexitelsefi=LCfiendifendforelse(2.3)RCfi=i(2.4)ifi=RCfithenexitelsefi=RCfiendifendifendrepeatEnd9.SIMD-CC上的并行算法第六章并行算法的根本设计技术10.划分技术〔了解，详见课件〕均匀划分技术方根划分技术对数划分技术功能划分技术11.双调归并网络及双调归并算法〔可能K〕双调序列(p149定义6.2)：(1,3,5,7,8,6,4,2,0)(8,7,6,4,2,0,1,3,5)(1,2,3,4,5,6,7,8)以上都是双调序列Batcher定理：给定双调序列(x0,x1,…,xn-1),对于si=min{xi,xi+n/2}和li=max{xi,xi+n/2}，那么小序列(s0,s1,…,sn-1)和大序列(l0,l1,…,ln-1)仍是双调序列。双调归并网络：Batcher双调归并算法：输入：双调序列X=(x0,x1,…,xn-1)输出：非降有序序列Y=(y0,y1,…,yn-1)ProcedureBITONIC_MERG(x)Begin(1)fori=0ton/2-1par-do(1.1)si=min{xi,xi+n/2}(1.2)li=max{xi,xi+n/2}endfor(2)RecursiveCall:(2.1)BITONIC_MERG(MIN=(s0,…,sn/2-1))(2.2)BITONIC_MERG(MIN=(l0,…,ln/2-1))(3)outputsequenceMINfollowedbysequenceMAXEnd12.平衡树1〕设计思想：以树的叶结点为输入，中间结点为处理结点，由叶向根或由根向叶逐层进行并行处理。2〕求最大值：算法6.8:SIMD-TC(SM)上求最大值算法Beginfork=m-1to0doforj=2kto2k+1-1par-doA[j]=max{A[2j],A[2j+1]}endforendforend图示：时间分析t(n)=m×O(1)=O(logn)p(n)=n/23〕计算前缀和：问题定义：n个元素{x1,x2,…,xn}，前缀和是n个局部和：Si=x1*x2*…*xi,1≤i≤n这里*可以是＋或×串行算法：Si=Si－1*xi计算时间为O(n)并行算法：p154算法6.9SIMD-TC上非递归算法令A[i]=xi,i=1~n,B[h,j]和C[h,j]为辅助数组(h=0~logn,j=1~n/2h)数组B记录由叶到根正向遍历树中各结点的信息(求和)数组C记录由根到叶反向遍历树中各结点的信息(播送前缀和)例如：n=8,p=8,C01~C08为前缀和13.倍增设计技术1〕设计思想：又称指针跳跃(pointerjumping)技术，特别适合于处理链表或有向树之类的数据结构；当递归调用时，所要处理数据之间的距离逐步加倍，经过k步后即可完成距离为2k的所有数据的计算。2〕例如：a〕表序问题问题描述n个元素的列表L，求出每个元素在L中的次第号(秩或位序或rank(k))，rank(k)可视为元素k至表尾的距离；例如：n=7(1)p[a]=b,p[b]=c,p[c]=d,p[d]=e,p[e]=f,p[f]=g,p[g]=gr[a]=r[b]=r[c]=r[d]=r[e]=r[f]=1,r[g]=0(2)p[a]=c,p[b]=d,p[c]=e,p[d]=f,p[e]=p[f]=p[g]=gr[a]=r[b]=r[c]=r[d]=r[e]=2,r[f]=1,r[g]=0(3)p[a]=e,p[b]=f,p[c]=p[d]=p[e]=p[f]=p[g]=gr[a]=4,r[b]=4,r[c]=4,r[d]=3,r[e]=2,r[f]=1,r[g]=0(4)p[a]=p[b]=p[c]=p[d]=p[e]=p[f]=p[g]=gr[a]=6,r[b]=5,r[c]=4,r[d]=3,r[e]=2,r[f]=1,r[g]=0算法：P155算法6.10(1)并行做：初始化p[k]和distance[k]//O(1)(2)执行次//O(logn)(2.1)对k并行地做//O(1)如果k的后继不等于k的后继之后继，那么(i)distance[k]=distance[k]+distance[p[k]](ii)p[k]=p[p[k]](2.2)对k并行地做rank[k]=distance[k]//O(1)运行时间：t(n)=O(logn)p(n)=nb〕求森林的根问题描述：一组有向树F中,如果<i,j>是F中的一条弧，那么p[i]=j(即j是i的双亲)；假设i为根，那么p[i]=i。求每个结点j(j=1~n)的树根s[j].例如：初始时P[1]=p[2]=5p[3]=p[4]=p[5]=6P[6]=p[7]=8p[8]=8P[9]=10p[10]=11p[11]=12p[12]=13p[13]=13s[i]=p[i]算法：P157算法6.11运行时间：t(n)=O(logn)W(n)=O(nlogn)第七章并行算法的一般设计过程14.PCAM设计方法学〔简答〕设计并行算法的四个阶段:划分(Partitioning):分解成小的任务，开拓并发性；通讯(Communication):确定诸任务间的数据交换，监测划分的合理性；组合(Agglomeration):依据任务的局部性，组合成更大的任务；映射(Mapping):将每个任务分配到处理器上，提高算法的性能。〔一〕划分：先进行数据分解(称域分解)，再进行计算功能的分解(称功能分解)；使数据集和计算集互不相交；划分阶段忽略处理器数目和目标机器的体系结构；能分为两类划分：域分解(domaindecomposition)和功能分解(functionaldecomposition)〔i〕域分解：划分的对象是数据，可以是算法的输入数据、中间处理数据和输出数据；将数据分解成大致相等的小数据片；划分时考虑数据上的相应操作；如果一个任务需要别的任务中的数据，那么会产生任务间的通讯；〔ii〕功能分解：划分的对象是计算，将计算划分为不同的任务，其出发点不同于域分解；划分后，研究不同任务所需的数据。如果这些数据不相交的，那么划分是成功的；如果数据有相当的重叠，意味着要重新进行域分解和功能分解；功能分解是一种更深层次的分解。〔二〕通讯通讯是PCAM设计过程的重要阶段；划分产生的诸任务，一般不能完全独立执行，需要在任务间进行数据交流；从而产生了通讯；功能分解确定了诸任务之间的数据流；诸任务是并发执行的，通讯那么限制了这种并发性；四种通讯模式：局部/全局通讯结构化/非结构化通讯静态/动态通讯同步/异步通讯〔三〕组合组合是由抽象到具体的过程，是将组合的任务能在一类并行机上有效的执行；合并小尺寸任务，减少任务数。如果任务数恰好等于处理器数，那么也完成了映射过程；通过增加任务的粒度和重复计算，可以减少通讯本钱；保持映射和扩展的灵活性，降低软件工程本钱；〔四〕映射，方法描述每个任务要映射到具体的处理器，定位到运行机器上；任务数大于处理器数时，存在负载平衡和任务调度问题；映射的目标：减少算法的执行时间并发的任务>不同的处理器任务之间存在高通讯的>同一处理器映射实际是一种权衡，属于NP完全问题；小结：划分：域分解和功能分解通讯：任务间的数据交换组合：任务的合并使得算法更有效映射：将任务分配到处理器，并保