下载文档原格式
并行计算第七章并行算法常用设计技术在并行计算中，算法的设计是非常重要的，旨在提高计算速度和效率。
本章将介绍几种常用的并行算法设计技术，包括任务划分、任务调度和数据划分等。
这些技术可以帮助程序员实现高性能的并行计算。
一、任务划分任务划分是指将一个大型计算任务拆分成多个小任务，并分配给多个处理单元并行执行。
常见的任务划分策略有以下几种：1.分治法：将大问题划分成多个子问题，并分别解决。
该方法适用于问题可以被分解成一系列独立的子问题的情况。
例如，计算斐波那契数列可以使用分治法将其拆分成多个子问题，并分配给多个处理单元计算。
2.流水线：将一个长任务划分成多个子任务，并按照流水线的方式依次执行。
每个处理单元处理一个子任务，并将结果传递给下一个处理单元。
流水线技术适用于具有顺序执行步骤的应用，例如图像处理和视频编码。
3.数据并行：将输入数据划分成多个子数据集，并分配给多个处理单元并行处理。
每个处理单元只操作自己分配的子数据集，然后将结果合并。
数据并行可以提高计算速度和处理能力，适用于数据密集型应用，例如矩阵运算和图像处理。
二、任务调度任务调度是指为每个任务分配合适的处理单元，并按照一定的策略进行调度和管理。
常见的任务调度策略有以下几种：1.静态调度：在程序开始执行之前，根据预先设定的规则将任务分配给处理单元。
静态调度可以提高计算效率，但不适用于动态变化的任务。
2.动态调度：根据运行时的情况动态地调整任务的分配和调度。
动态调度可以根据负载情况来实时调整任务的分配，提高系统的整体性能。
3.动态负载平衡：将任务合理地分配给多个处理单元，使得每个处理单元的负载尽可能均衡。
动态负载平衡可以避免单个处理单元负载过重或过轻的情况，提高计算效率。
三、数据划分数据划分是指将输入数据划分成多个部分，并分配给多个处理单元。
常见的数据划分策略有以下几种：1.均匀划分：将输入数据均匀地划分成多个部分，并分配给多个处理单元。
均匀划分可以实现负载均衡，但可能导致通信开销增加。
并行算法设计一、引言并行算法是指在多核处理器或分布式系统上同时执行多个子任务，以提高计算效率和处理速度的一种计算模式。
随着计算机硬件技术的不断发展，越来越多的问题需要借助并行算法来解决。
本文将介绍并行算法的设计原则和常见的设计模式，以及在实际应用中的一些注意事项。
二、并行算法设计原则1. 任务划分原则：并行算法的基础是将原本串行执行的任务划分成多个独立的子任务，并通过适当的调度算法分配给不同的处理器进行并行执行。
任务划分应尽量保持任务的独立性，避免数据依赖关系过多，以提高并行度和性能。
2. 数据分布原则：在设计并行算法时，应根据不同任务的计算量和数据量合理规划数据分布方式。
对于计算密集型任务，可以将数据均匀划分给多个处理器；对于数据密集型任务，可以采用数据分布策略来平衡负载和减少数据通信的开销。
3. 通信和同步原则：并行算法中，处理器间的通信和同步操作是必不可少的。
在设计并行算法时，应考虑如何减少通信和同步的开销，以提高整体的算法性能。
可以通过减少数据传输量、合理设置同步点等方式来优化并行算法的通信和同步操作。
4. 任务调度原则：任务调度是指将多个子任务合理地分配给不同的处理器进行执行的过程。
合理的任务调度策略可以提高并行算法的负载均衡性和吞吐量，并减少处理器间的竞争情况。
在设计并行算法时，应考虑任务划分和任务调度的关系，选择合适的调度策略来优化算法性能。
三、并行算法设计模式1. 分治法：分治法是指将一个大问题分解成多个相互独立的小问题，并通过递归的方式将小问题的解合并成大问题的解。
在设计并行算法时，可以将原问题划分成多个子问题，分配给不同的处理器并行解决，最后将子问题的解合并得到最终结果。
2. 数据并行：数据并行是指将数据划分成多个子集，分配给不同的处理器并行处理。
对于同一类操作，各处理器可以独立计算自己所负责的数据子集，最后将各处理器计算得到的结果合并得到最终结果。
3. 流水线：流水线是指将一个任务划分成多个子任务，并通过不同的处理器按照一定的顺序依次执行。
计算机的并行计算技术有哪些详解并行计算的架构与应用在现代科技领域，计算机的并行计算技术被广泛应用于许多领域，提供了强大的计算能力和效率。
本文将详细解释并行计算的概念、架构和应用，以及介绍几种常见的并行计算技术。
一、并行计算的概念并行计算是指同时执行多个计算任务的过程，以提高计算机系统的速度和性能。
与传统的串行计算相比，通过并行计算，多个处理器可以同时处理不同的计算任务，从而大大缩短了计算时间。
二、并行计算的架构1. 对称多处理器（SMP）对称多处理器是一种常见的并行计算架构，它包含多个处理器核心（CPU），每个处理器核心都可以访问共享内存。
因此，每个处理器核心都具有相同的权限和能力，并且可以相互通信和协作。
2. 分布式内存计算机（DMC）分布式内存计算机是一种将多个计算机连接在一起，并通过网络进行通信的并行计算架构。
在分布式内存计算机中，每个计算机都有自己的本地内存，并且计算任务被划分为子任务，在多台计算机之间进行并行计算。
3. 向量处理器向量处理器是一种特殊的并行计算架构，其核心思想是通过同时执行多个数据元素来提高计算性能。
向量处理器具有广泛的数据并行能力，并且可以在单个指令中处理多个数据。
三、并行计算的应用1. 科学计算在科学研究领域，许多复杂的计算任务需要大量的计算资源和时间。
通过并行计算技术，科学家可以利用多个处理器来加速大规模的数值模拟、数据分析和计算实验，从而加快科学研究的进程。
2. 数据挖掘与机器学习数据挖掘和机器学习是分析和理解大规模数据集的重要领域。
并行计算技术可以加速数据挖掘算法和机器学习模型的训练和推断过程，减少模型训练时间，提高预测和分类准确性。
3. 图像和视频处理在图像和视频处理领域，许多算法需要处理大量的像素和帧。
通过并行计算技术，可以将图像和视频处理任务分成多个子任务，并在多个处理器上同时处理这些子任务，从而提高图像和视频处理的效率和实时性。
4. 数据库管理和并行查询在大规模数据库管理和查询中，通过并行计算技术可以将查询任务划分为多个子任务，并由多个处理器同时执行这些子任务。
并行计算的算法设计与优化在计算机科学领域，随着计算机性能的提升和大规模数据处理的需求增加，并行计算逐渐成为一种重要的解决方案。
并行计算旨在通过同时执行多个计算任务来提高计算效率和性能。
本文将探讨并行计算的算法设计与优化。
一、并行计算的基本概念并行计算指的是将计算任务分解为多个独立的子任务，并在多个处理单元上同时执行这些子任务的过程。
通过并行计算，可以显著缩短计算任务的执行时间，提高计算系统的吞吐量和响应速度。
二、并行计算的算法设计原则1. 任务划分：将计算任务分解为多个互相独立的子任务，确保每个子任务间的计算关系尽可能少。
2. 数据划分：将输入数据分割为多个适当大小的块，以便每个处理单元可以独立地操作这些数据块。
3. 通信与同步：处理单元之间需要进行通信和同步操作，以便完成数据交换和协调计算任务的进度。
4. 负载均衡：分配任务给每个处理单元时，需要确保每个处理单元的负载相对均衡，避免出现某个处理单元繁忙而其他处理单元空闲的情况。
5. 数据局部性：合理利用数据局部性原则，减少处理单元之间的数据传输，以提高整体计算效率。
三、并行计算的算法优化技术1. 并行算法设计：根据具体的计算问题，设计高效的并行算法，使得各个子任务能够充分利用处理单元的计算能力。
2. 并行性分析：对计算任务之间的依赖关系进行分析，确定哪些计算任务可以并行执行，以及在并行执行时能否通过调整计算顺序来减少通信开销。
3. 算法细节优化：在编写并行算法时，注意细节上的优化，如减少数据冲突、合并通信操作、使用局部缓存等。
4. 并行化策略选择：根据具体应用场景和硬件平台的特点，选择合适的并行化策略，如任务并行、数据并行、管道并行等。
四、并行计算的实际应用1. 大规模数据处理：并行计算在大数据处理、数据挖掘和机器学习等领域具有广泛的应用，可以加速数据处理和分析过程。
2. 科学计算：并行计算广泛应用于科学计算领域，如天气预测、流体力学模拟和量子化学计算等，可以加快计算过程，提高计算精度。
第篇第二篇并行算法的设计第五章并行算法与并行计算模型第六章并行算法基本设计策略第七章并行算法常用设计技术第八章并行算法一般设计过程并行算法般设计过程第七章并行算法常用设计技术7.1 划分设计技术7..均匀划分技术7.1.17.1.2 方根划分技术7.1.3 对数划分技术7137.1.4 功能划分技术7.2 分治设计技术727.3 平衡树设计技术7.4 倍增设计技术7.5 流水线设计技术75均匀划分技术均匀划分技术（1）▪划分方法[1]组每组[(1)/1/]1n 个元素A[1..n]分成p 组，每组A[(i A[(i--1)n/p+1..in/p]，i =1~p ▪示例：MIMDMIMD--SM 模型上的PSRS 排序b egin begin (1)均匀划分：将n 个元素A[1..n]均匀划分成p 段，每个p i 处理A[(i--1)n/p+1..in/p]A[(i 1)n/p 1..in/p](2)局部排序：p i 调用串行排序算法对A[(i A[(i--1)n/p+1..in/p]排序(3)选取样本：p i 从其有序子序列A[(i A[(i--1)n/p+1..in/p]中选取p 个样本元素(4)样本排序用台处理器对(4)样本排序：用一台处理器对p 2个样本元素进行串行排序(5)选择主元：用一台处理器从排好序的样本序列中选取p -1个主元，并播送给其他播给其他p i (6)主元划分：p i 按主元将有序段A[(i A[(i--1)n/p+1..in/p]划分成p 段(7)全局交换：各处理器将其有序段按段号交换到对应的处理器中归并排序各处理器对接收到的元素进行归并排序(8)归并排序：各处理器对接收到的元素进行归并排序end.均匀划分技术（2）71 PSRS N=27p=3例7.1 PSRS 排序过程。
N 27，p 3，PSRS 排序如下：(a)均匀划分(b)局部排序(c)正则采样6122033394069727233(d)采样排序：(e)选择主元：(f)主元划分(g)全局交换(h)归并排序第七章并行算法常用设计技术7.1 划分设计技术7..均匀划分技术7.1.17.1.2 方根划分技术7.1.3 对数划分技术7137.1.4 功能划分技术7.2 分治设计技术727.3 平衡树设计技术7.4 倍增设计技术7.5 流水线设计技术75方根划分技术（1）▪划分方法A[1n]1)n^(1/2)+1in^(1/2)]i=1~n^(1/2) n 个元素A[1..n]分成A[(i A[(i--1)n (1/2)+1..in (1/2)]，i=1~n (1/2)▪示例：SIMD SIMD--CREW 模型上的Valiant 归并(1975年发表)//有序组A[1p]B[1q] (假设p<=q) 处理器数⎣⎦pqk =//有序组A[1..p]、B[1..q], (假设p<=q),p<=q), 处理器数begin(1)方根划分: A,B 分别按；⎣⎦pq k =）、分成若干段（和i i ~1~1==(),按(2)段间比较: A 划分元与B 划分元比较(至多对)，确定A 划分元应插入B 中的区段；⎡⎤⎡⎤⎣⎦⎣⎦q j p q j p ⎣⎦⎣⎦q p ⋅(3)段内比较: A 划分元与B 相应段内元素进行比较，并插入适当的位置；(4)递归归并: B 按插入的A 划分元重新分段，与A 相应段(A 除去原划分元)构成了成对的段组对每对段组递归执行直至构成了成对的段组，对每对段组递归执行(1)~(3)，直至A 组为0时，递归结束; 各组仍按分配处理器；end.⎣⎦pq k =方根划分技术（2） 示例: A={1,3,8,9,11,13,15,16},p=8; B={2,4,5,6,7,10,12,14,17},q=9⎤⎦A: 1 3 8* 9 11 13* 15 16B: 2 4 5* 6 7 10* 12 14 17*⎡⎣)2,3,8===p p p （⎡⎤⎣⎦)3,3,9===q q q （{(1)(2)A: 138*91113*1516B: 2 4 5* 6 7 10* 12 14 17*{(3)13((2)A 1: 1 3 (p 12:911(p 2=2) A 2:1516B 1: 2 4 5 6 7 8(q 1=6) B 2: 10 12 13(q 2=3) B 3: 14 17A 1: 1 3*(p 1...... ......B11=6) ...... ......1*A 1111:...... ......B 11: 4 5 6 7 8 ...... ...... A:根划分技术（方根划分技术（3）算法分析 = (1)算法在并行递归过程中所需的处理器数≤⎣⎦pq k 段间比较:⎣⎦⎣⎦q p ⋅比较对数≤⎣⎦k pq ＝； ⎦⎦k ＝）－（≤⋅1 段内比较: ⎣⎣⎣⎦pq q p 递归调用: 设A,B 分成若干子段对为(p 1,q 1), (p 2,q 2),…… 则∑p i ≤p, ∑q i ≤q, 由Cauchy 不等式＝>⎣⎦⎣⎦⎣⎦⎣⎦k pq q p q p q p ii i i i i =≤≤≤∑∑∑∑ k = 综上，整个过程可用处理器数⎣⎦pq 完成。
第7章并行算法简介计算机发展的趋势是越来越先进，从数据和信息处理到知识处理，最终到智能处理，每前进一步，均要求增强计算机的处理能力。
计算机发展的历史表明，为了达到高性能，除了必须提高元器件的速度外，系统结构（体系结构）也必须不断改进，特别是当元器件的速度达到极限时，后者将变成问题的焦点。
1 并行计算简介计算机系统结构的改进主要围绕着增加同一时间间隔内的操作数量，即所谓并行处理技术；而为并行处理所设计的计算机统称之为并行计算机，在并行计算机上求解问题的过程称之为并行计算；凡适合于在各种并行计算机上求解问题和处理数据的算法就称之为并行算法。
并行计算是一比较年轻的领域：因为著名的I11iac IV(阵列处理机也叫阵列处理器)1975年才开始运行，第一台Cray-1(流水线向量处理机)1976年才交付使用；低成本的多处理机(也称多处理器)1984年以后也才开始流行．并行计算机的发展主要是某些大型应用领域的要求；1)例如气象预报2)空气动力学3)人工智能4)卫星图象处理5)核反应模拟以及军事应用等为了达到上述高性能的要求，除了提高速度外，主要是改进计算机的系统结构，例如：1)引入I／O通道：将费时的I／O操作交给I／O处理器(即通道)去作，从而解脱了CPU的负担；2)交叉存贮：将存贮体分成多个模块，以达到并行存取和减少冲突之目的。
3)高速缓存：减少处理机和主存中的数据交换时间，平滑其间的数据流动速率；4)指令先行：一次取出好几条下一次待执行的指令，致使取指令可以和指令译码同样快；5)多功能单元：在中央处理器中设置多个功能单元(加法、乘法器等)可以提高单一程序的吞吐量，缩短周转时间；6)指令重叠和流水线技术：在同一时间允许多条指令在不同的阶段按流水线方式执行不同的操作；7)向量处理技术：一条向量指令可同时处理向量的n个分量，它们可以同时在各个处理器中进行运算，也可以连续地送入流水线中进行重叠处理；8)多道程序设计：同时把若干个作业放在内存中，允许在同一时间有多道程序处于运行状态；9)数据驱动：与常规的冯·诺依曼计算机不同，它不是采用指令驱动操作，而是采用操作数(据)驱动操作，这样如果有多个操作数准备就绪时，就可以彼此并行地执行而不受指令顺序执行的限制，从而有可能充分开拓并行度。
并行计算：使用并行计算提高计算效率的技巧和方法并行计算是一种通过同时处理多个任务或部分任务来提高计算效率的方法。
在计算机科学领域中，随着数据量不断增大和计算需求不断增加，传统的串行计算方式已经无法满足要求。
因此，并行计算技术成为了一种重要的解决方案。
并行计算的主要优点包括：提高计算效率、减少计算时间、增加计算容量、降低成本等。
利用多核处理器、集群、云计算等技术，可以实现并行计算。
以下是一些提高并行计算效率的技巧和方法：1.任务分解：将大任务分解成多个子任务，然后同时执行这些子任务，提高整体计算效率。
在任务分解过程中，要考虑到任务之间的依赖关系和数据之间的传输延迟，避免出现资源竞争和数据不一致的情况。
2.负载均衡：合理分配任务给不同的处理单元，避免出现某一处理单元负载过重而导致整体性能下降的情况。
负载均衡可以通过动态调整任务分配策略来实现，根据任务的执行情况进行监控和调整。
3.数据传输优化：在并行计算过程中，数据传输往往是影响计算效率的关键因素之一。
通过减少数据传输量、优化数据传输路径、减少数据传输延迟等方法，可以提高计算效率。
4.并行编程模型：选择合适的并行编程模型对于提高计算效率至关重要。
常见的并行编程模型包括MPI、OpenMP、CUDA等，根据具体的应用场景和硬件平台选择合适的并行编程模型可以提高计算效率。
5.并行算法设计：设计并行算法时，需要考虑到并行计算的特点，合理利用并行计算资源，减少通信开销和数据冗余，提高算法并行度和并行效率。
6.硬件优化：在进行并行计算时，选择合适的硬件设备也非常重要。
优化硬件配置、选择性能强劲的处理器和内存、使用高速网络连接等方法可以提高并行计算效率。
7.并行计算框架：利用现有的并行计算框架如Hadoop、Spark等，可以简化并行计算的开发流程，提高开发效率，同时也能够提高计算效率。
8.任务调度策略：合理的任务调度策略能够有效地利用计算资源，避免资源浪费和资源竞争，提高整体计算效率。
并行计算Parallel Computing主讲人徐云Spring, 2014第二篇并行算法的设计第五章并行算法与并行计算模型第六章并行算法基本设计策略第七章并行算法常用设计技术第八章并行算法一般设计过程第七章并行算法常用设计技术7.1 划分设计技术7.1.1 均匀划分技术7.1.2 方根划分技术7.1.3 对数划分技术7.1.4 功能划分技术7.2 分治设计技术7.3 平衡树设计技术7.4 倍增设计技术7.5 流水线设计技术均匀划分技术（1）划分方法n个元素A[1..n]分成p组，每组A[(i-1)n/p+1..in/p]，i=1~p示例：MIMD-SM模型上的PSRS排序begin(1)均匀划分：将n个元素A[1..n]均匀划分成p段，每个p i处理A[(i-1)n/p+1..in/p](2)局部排序：p i调用串行排序算法对A[(i-1)n/p+1..in/p]排序(3)选取样本：p i从其有序子序列A[(i-1)n/p+1..in/p]中选取p个样本元素(4)样本排序：用一台处理器对p2个样本元素进行串行排序(5)选择主元：用一台处理器从排好序的样本序列中选取p-1个主元，并播送给其他p i(6)主元划分：p i按主元将有序段A[(i-1)n/p+1..in/p]划分成p段(7)全局交换：各处理器将其有序段按段号交换到对应的处理器中(8)归并排序：各处理器对接收到的元素进行归并排序end.均匀划分技术（2）例7.1 PSRS 排序过程。
N=27，p=3，PSRS 排序如下：154648933967291143669408961971221545397845832273372206141539464872919312213640546169899720273233535872849763972124069203372612203339406972723369614153946487291931221364054616989972027323353587284976141561415394648729193122136405461698997202732335358728497394648729193122136405461698997202732335358728497(a)均匀划分：(b)局部排序：(c)正则采样：(d)采样排序：(e)选择主元：(f)主元划分：(h)归并排序：(g)全局交换：第七章并行算法常用设计技术7.1 划分设计技术7.1.1 均匀划分技术7.1.2 方根划分技术7.1.3 对数划分技术7.1.4 功能划分技术7.2 分治设计技术7.3 平衡树设计技术7.4 倍增设计技术7.5 流水线设计技术方根划分技术（1）划分方法n 个元素A[1..n]分成A[(i -1)n^(1/2)+1..in^(1/2)]，i=1~n^(1/2) 示例：SIMD -CREW 模型上的Valiant 归并(1975年发表)//有序组A[1..p]、B[1..q], (假设p<=q), 处理器数begin(1)方根划分: A,B 分别按；(2)段间比较: A 划分元与B 划分元比较(至多对)，确定A 划分元应插入B 中的区段；(3)段内比较: A 划分元与B 相应段内元素进行比较，并插入适当的位置；(4)递归归并: B 按插入的A 划分元重新分段，与A 相应段(A 除去原划分元)构成了成对的段组，对每对段组递归执行(1)~(3)，直至A 组为0时，递归结束; 各组仍按分配处理器；end.⎣⎦pq k =⎣⎦pq k =⎡⎤⎡⎤⎣⎦⎣⎦）、分成若干段（和q j p i q j p i ~1~1==⎣⎦⎣⎦q p ⋅⎣⎦pq k =方根划分技术（2） 示例: A={1,3,8,9,11,13,15,16},p=8; B={2,4,5,6,7,10,12,14,17},q=9A: 1 3 8* 9 11 13* 15 16B: 2 4 5* 6 7 10* 12 14 17*⎡⎤⎣⎦)2,3,8===p p p （⎡⎤⎣⎦)3,3,9===q q q （{(1)(2)A: 1 3 8* 9 11 13* 15 16B: 2 4 5* 6 7 10* 12 14 17*{ (3)A 1: 1 3 (p 1=2) A 2: 9 11 (p 2=2) A 2: 15 16B 1: 2 4 5 6 7 8(q 1=6) B 2: 10 12 13(q 2=3) B 3: 14 17A 1: 1 3* (p 1=2) ...... ......B 1: 2 4 5* 6 7 8*(q 1=6) ...... ......A 11: 1* A 11: ...... ......B 11: 2 3* B 12: 4 5 6 7 8 ...... ......A:B: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17方根划分技术（3）算法分析 (1)算法在并行递归过程中所需的处理器数≤⎣⎦pq k = 段间比较:⎣⎦⎣⎦q p ⋅比较对数≤⎣⎦k pq ＝； 段内比较: ⎣⎦⎣⎦⎣⎦k pq q p ＝）－（≤⋅1 递归调用: 设A,B 分成若干子段对为(p 1,q 1), (p 2,q 2),…… 则∑p i ≤p, ∑q i ≤q, 由Cauchy 不等式＝>⎣⎦⎣⎦⎣⎦⎣⎦k pq q p q p q p ii i i i i =≤≤≤∑∑∑∑综上，整个过程可用处理器数⎣⎦pq k =完成。
(2)时间分析记λi 是第i 次递归后的A 组最大长度，＝>p =0λ, ⎣⎦⎣⎦i p i i −≤≤≤−21"λλ 算法在C i 常数=λ时终止递归，即12+≤≤−C p C i 常数常数＝> 1log log C p i 常数+≤ 由(1)知算法中其他各步的时间为O(1), 所以Valiant 归并算法时间q p p O q p t k ≤=)log (log ),(第七章并行算法常用设计技术7.1 划分设计技术7.1.1 均匀划分技术7.1.2 方根划分技术7.1.3 对数划分技术7.1.4 功能划分技术7.2 分治设计技术7.3 平衡树设计技术7.4 倍增设计技术7.5 流水线设计技术对数划分技术划分方法n个元素A[1..n]分成A[(i-1)logn+1..ilogn]，i=1~n/logn示例：PRAM-CREW上的对数划分并行归并排序(1)归并过程: 设有序组A[1..n]和B[1..m]j[i]=rank(b ilogm:A)为b ilogm在A中的位序，即A中小于等于b ilogm的元素个数(2)例：A=(4,6,7,10,12,15,18,20), B=(3,9,16,21) n=8, m=4=>logm=log4=2=> j[1]=rank(b logm:A)=rank(b2:A)=rank(9:A)=3, j[2]=…=8B0: 3, 9 B1: 16, 21A0: 4, 6, 7 A1: 10, 12, 15, 18, 20A和B归并化为(A0, B0)和(A1, B1)的归并第七章并行算法常用设计技术7.1 划分设计技术7.1.1 均匀划分技术7.1.2 方根划分技术7.1.3 对数划分技术7.1.4 功能划分技术7.2 分治设计技术7.3 平衡树设计技术7.4 倍增设计技术7.5 流水线设计技术功能划分技术（1）划分方法n个元素A[1..n]分成等长的p组，每组满足某种特性。
示例：(m, n)选择问题(求出n个元素中前m个最小者) 功能划分：要求每组元素个数必须大于m；算法：p194算法7.4输入：A=(a1,…,a n); 输出：前m个最小者；Begin(1) 功能划分：将A划分成g=n/m组，每组含m个元素；(2) 局部排序：使用Batcher排序网络将各组并行进行排序；(3) 两两比较：将所排序的各组两两进行比较，从而形成MIN序列；(4) 排序-比较：对各个MIN序列，重复执行第(2)和第(3)步，直至选出m个最小者。
End功能划分技术（2）第七章并行算法常用设计技术7.1 划分设计技术7.2 分治设计技术7.2.1 并行分治设计步骤7.2.2 双调归并网络7.3 平衡树设计技术7.4 倍增设计技术7.5 流水线设计技术并行分治设计步骤将输入划分成若干个规模相等的子问题；同时(并行地)递归求解这些子问题； 并行地归并子问题的解，直至得到原问题的解。
第七章并行算法常用设计技术7.1 划分设计技术7.2 分治设计技术7.2.1 并行分治设计步骤7.2.2 双调归并网络7.3 平衡树设计技术7.4 倍增设计技术7.5 流水线设计技术双调归并网络（1） 双调序列(p195定义7.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 定理给定双调序列(x 0,x 1,…,x n -1), 对于s i =min{x i ,x i+n/2}和l i =max{x i ,x i+n/2}，则小序列(s 0,s 1,…,s n -1)和大序列(l 0,l 1,…,l n -1)仍是双调序列。
双调归并网络（2） (4,4)双调归并网络双调归并网络（3） Batcher双调归并算法输入：双调序列X=(x0,x1,…,x n-1)输出：非降有序序列Y=(y0,y1,…,y n-1)Procedure BITONIC_MERG(x)Begin(1)for i=0 to n/2-1 par-do(1.1) s i=min{x i,x i+n/2}(1.2) l i=max{x i,x i+n/2}end for(2)Recursive Call:(2.1)BITONIC_MERG(MIN=(s0,…,s n/2-1))(2.2)BITONIC_MERG(MIN=(l0,…, l n/2-1))(3)output sequence MIN followed by sequence MAX End第七章并行算法常用设计技术7.1 划分设计技术7.2 分治设计技术7.3 平衡树设计技术7.3.1 设计思想7.3.2 求最大值7.3.3 计算前缀和7.4 倍增设计技术7.5 流水线设计技术平衡树设计技术设计思想以树的叶结点为输入，中间结点为处理结点，由叶向根或由根向叶逐层进行并行处理。
示例求最大值计算前缀和第七章并行算法常用设计技术7.1 划分设计技术7.2 分治设计技术7.3 平衡树设计技术7.3.1 设计思想7.3.2 求最大值7.3.3 计算前缀和7.4 倍增设计技术7.5 流水线设计技术求最大值（1）算法7.8: SIMD-TC(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/2A1An/4An/2-1An/2An/2+1An-2An-1AnAn+1An+2An+3A2n-4A2n-3A2n-2A2n-1K=m-1K=m-2K=0P1P1P2Pn/2-1Pn/2P1Pn/2-1求最大值（2）SIMD-CRCW上常数时间求最大值算法算法SIMD-CRCW上枚举算法//输入A[1..p]，p个不同元素//B[1..p][1..p],M[1..p]为中间处理用的布尔数组, 如果M[i]＝1, 则A[i]为最大值begin(1)for 1≤i, j≤p par-do //工作量O(p2); 时间O(1),因为允许同时读if A[i]≥A[j] then B[i, j]=1 else B[i, j]=0end ifend for(2)for 1≤i≤p par-do //工作量O(p2); 时间O(1),因为允许同时写M[i]=B[i,1]∧B[i,2]∧…∧B[i,p]end for end T(n)=O(1)W(n)=O(p2)可以用p2个处理器实现速度虽快，但不是WT最优第七章并行算法常用设计技术7.1 划分设计技术7.2 分治设计技术7.3 平衡树设计技术7.3.1 设计思想7.3.2 求最大值7.3.3 计算前缀和7.4 倍增设计技术7.5 流水线设计技术计算前缀和（1）问题定义n个元素{x1,x2,…,x n}，前缀和是n个部分和：S i=x1*x2*…*x i, 1≤i≤n 这里*可以是＋或×串行算法：S i=S i－1*x i计算时间为O(n)并行算法：p199算法7.9 SIMD-TC上非递归算法令A[i]=x i, i=1~n,B[h,j]和C[h,j]为辅助数组(h=0~logn, j=1~n/2h)数组B记录由叶到根正向遍历树中各结点的信息(求和)数组C记录由根到叶反向遍历树中各结点的信息(播送前缀和)计算前缀和（2） 例：n=8, p=8, C01~C08为前缀和计算前缀和（3）SIMD -SM 上非递归算法begin(1)for j=1 to n par -do //初始化B[0,j]=A[j ]end if(2)for h=1 to logn do //正向遍历for j=1 to n/2h par -doB[h,j ]=B[h -1,2j -1]*B[h -1,2j]end for end for时间分析:(1) O(1) (2) O(logn) (3) O(logn)==>t(n)=O(logn) , p(n)=n , c(n)=O(nlogn)(3)for h=logn to 0 do //反向遍历for j=1 to n/2h par-do (i) if j=even then //该结点为其父结点的右儿子C[h,j]=C[h+1,j/2]end if (ii) if j=1 then //该结点为最左结点C[h,1]=B[h,1]end if(iii) if j=odd>1 then //该结点为其父结点的左儿子C[h,j]=C[h+1,(j-1)/2]*B[h,j]end ifend forend for end第七章并行算法常用设计技术7.1 划分设计技术7.2 分治设计技术7.3 平衡树设计技术7.4 倍增设计技术7.4.1 设计思想7.4.2 表序问题7.4.3 求森林的根7.5 流水线设计技术倍增设计技术设计思想又称指针跳跃(pointer jumping)技术，特别适合于处理链表或有向树之类的数据结构；当递归调用时，所要处理数据之间的距离逐步加倍，经过k步后即可完成距离为2k的所有数据的计算。
