并行算法的设计与分析(4)
- 格式：ppt
- 大小：543.00 KB
- 文档页数：21
下载文档原格式
合集下载
并行算法设计
并行算法设计一、引言并行算法是指在多核处理器或分布式系统上同时执行多个子任务，以提高计算效率和处理速度的一种计算模式。
随着计算机硬件技术的不断发展，越来越多的问题需要借助并行算法来解决。
本文将介绍并行算法的设计原则和常见的设计模式，以及在实际应用中的一些注意事项。
二、并行算法设计原则1. 任务划分原则：并行算法的基础是将原本串行执行的任务划分成多个独立的子任务，并通过适当的调度算法分配给不同的处理器进行并行执行。
任务划分应尽量保持任务的独立性，避免数据依赖关系过多，以提高并行度和性能。
2. 数据分布原则：在设计并行算法时，应根据不同任务的计算量和数据量合理规划数据分布方式。
对于计算密集型任务，可以将数据均匀划分给多个处理器；对于数据密集型任务，可以采用数据分布策略来平衡负载和减少数据通信的开销。
3. 通信和同步原则：并行算法中，处理器间的通信和同步操作是必不可少的。
在设计并行算法时，应考虑如何减少通信和同步的开销，以提高整体的算法性能。
可以通过减少数据传输量、合理设置同步点等方式来优化并行算法的通信和同步操作。
4. 任务调度原则：任务调度是指将多个子任务合理地分配给不同的处理器进行执行的过程。
合理的任务调度策略可以提高并行算法的负载均衡性和吞吐量，并减少处理器间的竞争情况。
在设计并行算法时，应考虑任务划分和任务调度的关系，选择合适的调度策略来优化算法性能。
三、并行算法设计模式1. 分治法：分治法是指将一个大问题分解成多个相互独立的小问题，并通过递归的方式将小问题的解合并成大问题的解。
在设计并行算法时，可以将原问题划分成多个子问题，分配给不同的处理器并行解决，最后将子问题的解合并得到最终结果。
2. 数据并行：数据并行是指将数据划分成多个子集，分配给不同的处理器并行处理。
对于同一类操作，各处理器可以独立计算自己所负责的数据子集，最后将各处理器计算得到的结果合并得到最终结果。
3. 流水线：流水线是指将一个任务划分成多个子任务，并通过不同的处理器按照一定的顺序依次执行。
高性能的并行计算算法设计与分析
高性能的并行计算算法设计与分析随着计算机技术的不断发展，越来越多的应用需要处理大量的数据和复杂的计算任务。
并行计算算法可以有效地将计算任务分解为多个子任务，并利用多个处理器同时进行计算，提高计算效率。
本文将探讨高性能的并行计算算法的设计与分析，介绍一些常用的并行计算算法和评估方法。
在设计高性能的并行计算算法时，首先需要考虑的是任务的划分与调度。
任务划分是将一个大的计算任务分解为多个子任务的过程，而任务调度是将这些子任务分配给不同的处理器进行计算的过程。
合理的任务划分和调度可以最大程度地提高并行计算的性能。
常用的任务划分策略包括数据划分和任务划分。
数据划分是将数据划分为多个小块，并将每个小块分配给不同的处理器进行计算。
而任务划分则是将计算任务分为多个子任务，并将每个子任务分配给不同的处理器进行处理。
这两种划分策略可以根据问题的特点和计算资源的分布选择合适的方式。
与任务划分相对应的是任务调度。
任务调度决定了每个处理器计算哪些子任务，并控制处理器之间的通信和同步。
常用的任务调度策略包括静态调度和动态调度。
静态调度在计算开始前就确定每个处理器的计算任务，而动态调度则是在计算过程中根据处理器的负载情况动态地调整任务分配。
除了任务划分与调度，算法设计中还需要考虑数据通信和同步的问题。
并行计算中，不同处理器之间需要进行数据交换和同步操作，以保证计算的正确性和一致性。
数据通信和同步的效率对并行计算的性能影响很大，因此需要精心设计和优化。
在进行高性能并行计算算法的分析时，可以采用多种评估指标。
常用的指标包括加速比、效率和可扩展性。
加速比定义为串行算法的执行时间与并行算法的执行时间的比值，反映了并行计算的效率。
效率表示并行计算的实际效果与理论效果之间的比例。
可扩展性表示并行算法在不同规模问题上的可扩展性能力。
为了更好地评估并行算法的性能，可以采用实际测试或者理论分析的方法。
实际测试包括在真实的并行计算环境中进行测试，收集运行时间等信息进行评估。
并行计算.4算法
方根划分技术
示例: A={1,3,8,9,11,13,15,16},p=8; B={2,4,5,6,7,10,12,14,17},q=9
(1)(2)
B:
A:
1 2 1 2
3 4 3 4
(f) 主元划分 ： 6 14 15 39 46 48 72 91 93 12 21 36 40 54 61 69 89 97 20 27 32 33 53 58 72 84 97
(g) 全局交换 ： 6 14 15 12 21 20 27 32 33 39 46 48 36 40 54 61 69 53 58 72 91 93 89 97 72 84 97
均匀划分技术
• 例 PSRS排序过程。N=27，p=3，PSRS排序如下：
(a) 均匀划分 ：15 46 48 93 39 6 72 91 14 36 69 40 89 61 97 12 21 54 53 97 84 58 32 27 33 72 20
(b) 局部排序 ： 6 14 15 39 46 48 72 91 93 12 21 36 40 54 61 69 89 97 20 27 32 33 53 58 72 84 97 (c) 正则采样 ： (d) 采样排序 ： (e) 选择主元 ： 6 6 33 39 12 69 72 20 12 33 40 39 69 40 20 69 33 72 72 72
并行算法
1 一般设计方法
并行算法的一般设计方法
• 串行算法的直接并行化
• 从问题描述开始设计并行算法 • 借用已有算法求解新问题
串行算法的直接并行化
• 设计方法描述
• 快排序算法的并行化
设计方法的描述
• 方法描述 –发掘和利用现有串行算法中的并行性，直接将 串行算法改造为并行算法。 –许多并行编程语言都支持通过在原有的串行程 序中加入并行原语（例如某些通信命令等）的 方法将串行程序并行化。来自借用已有算法求解新问题
大规模数据分析中并行计算算法的设计与实现技巧分享
大规模数据分析中并行计算算法的设计与实现技巧分享随着互联网技术的快速发展和信息化进程的加速，大规模数据分析成为了解决复杂问题和发现隐藏信息的重要手段。
然而，处理大规模数据集所需的计算资源往往是一个巨大的挑战。
为了提高计算效率，许多数据分析任务需要使用并行计算算法。
本文将分享一些设计和实现大规模数据分析中并行计算算法的技巧。
首先，我们需要明确并行计算算法的基本概念。
并行计算是指在多个处理单元上同时执行计算任务，以提高计算速度和效率。
在大规模数据分析中，常见的并行计算算法有MapReduce、并行排序、图计算等。
对于并行计算算法的设计，以下是一些技巧：1. 划分数据集：将大规模数据集合理划分成适当大小的子集，以便能够并行处理。
这可以通过水平划分（根据记录的属性）或垂直划分（根据属性的值）来实现。
划分数据集时要考虑数据之间的依赖关系，以保证并行计算的正确性和一致性。
2. 选择合适的并行计算模型：根据数据集的特性和分析任务的需求，选择适合的并行计算模型。
例如，MapReduce模型适用于大规模数据分析和计算，并行排序适用于排序和统计任务，图计算适用于网络分析和社交网络分析等。
3. 任务调度和负载均衡：并行计算算法通常涉及多个计算单元或计算节点，任务调度和负载均衡非常重要。
任务调度可以确保在计算单元之间合理分配任务，并且使计算资源得到充分利用。
负载均衡可以保证每个计算单元的负载相对均衡，避免某个计算单元的负载过重而导致性能下降。
4. 并行计算算法的设计模式：并行计算算法常常采用一些经典的设计模式来实现。
例如，MapReduce模式中的Map阶段和Reduce阶段，可以将数据分为多个片段并进行并行计算，然后将结果合并。
在实现大规模数据分析中的并行计算算法时，以下是一些技巧：1. 并行编程模型和框架的选择：选择适合的并行编程模型和框架可以大大简化并行计算算法的实现过程。
例如，Hadoop/MapReduce框架、Spark框架等提供了高级的抽象层和并行计算支持，可以方便地进行大规模数据分析的并行计算。
高性能计算中的并行算法分析与设计研究
高性能计算中的并行算法分析与设计研究在高性能计算中，为了处理大规模数据和复杂问题，使用并行算法成为了一种必要的选择。
并行算法可以将任务分解成多个子任务，同时运行在多个处理单元上，以提高计算速度和效率。
本文将对高性能计算中的并行算法进行分析与设计研究。
首先，对于并行算法的分析来说，我们需要考虑以下几个方面。
首先是任务的可并行性分析。
并行算法最大的挑战之一是如何将任务分解成可并行执行的子任务。
在分析任务可并行性时，需要确定任务之间的依赖关系，并确定哪些任务可以并行执行。
这需要对任务的数据流、控制依赖和资源限制进行详细分析。
其次是算法的分解与调度。
一旦确定了任务的可并行性，就需要将任务分解成多个子任务，并将它们分配到可用的处理单元上。
这需要考虑任务之间的负载均衡、通信开销、同步和互斥等问题。
通过合理的分解和调度，可以提高算法的并行效率。
另外，我们还需要考虑并行算法的可扩展性。
随着问题规模的增加，系统中可用的处理单元数量也会增加。
因此，并行算法需要具备良好的可扩展性，即在处理单元增加时，算法的性能仍能得到有效的提升。
这可以通过减小通信开销、提高并行度、优化数据布局等方式来实现。
进一步来说，对于并行算法的设计研究，我们可以考虑以下几个方面。
首先是并行算法设计的目标。
在设计并行算法时，需要明确设计的目标是什么。
是为了提高计算速度？还是为了节约能源或降低成本？针对不同的目标，可以采用不同的设计策略和算法框架。
例如，当目标是提高计算速度时，可以采用数据并行或任务并行的策略。
其次是并行算法的选择和实现。
并行算法有多种选择和实现方式，可以根据具体需求选择合适的算法。
例如，并行排序可以采用快速排序并行化实现，矩阵乘法可以采用Cannon算法或Strassen算法等。
根据不同算法的特点和调优方式，可以设计出高效的并行算法。
另外，还需要考虑并行算法的性能评估与调优。
在设计完并行算法后，需要对其性能进行评估和调优。
可以通过实验室实验、仿真模拟和性能分析等方式来评估算法的性能，并根据评估结果进行相应的调优。
并行计算算法设计与分析
并行计算算法设计与分析一、引言在现代计算机系统中，并行计算已经成为一种重要的技术手段。
并行计算算法的设计与分析是研究并行计算的核心内容之一。
本文将详细介绍并行计算算法的设计与分析方法，并讨论其在实际应用中的意义与挑战。
二、并行计算算法的分类1. 数据并行算法数据并行算法采用将计算任务分割为多个子任务，每个子任务在不同的处理单元上并行执行的方式。
典型的数据并行算法包括矩阵乘法算法、并行排序算法等。
2. 任务并行算法任务并行算法是将计算任务分解为多个相互独立的子任务，并行执行的方式。
各个子任务之间没有数据依赖关系，可以同时进行计算。
典型的任务并行算法包括并行搜索算法、并行图算法等。
3. 流水线并行算法流水线并行算法是将计算任务分解为多个阶段，不同处理单元在不同阶段上并行执行，通过流水线的方式提高计算效率。
典型的流水线并行算法包括多级缓存机制的并行计算算法、指令级并行计算算法等。
三、并行计算算法的设计方法1. 并行分解并行分解是指将原始的计算任务分解为多个子任务的过程。
在并行分解过程中，需要考虑任务的划分方式、任务之间的依赖关系以及负载均衡等问题。
2. 并行通信并行通信是指多个处理单元之间的信息传递与同步。
在并行计算算法的设计中，合理的并行通信方式能够提高计算效率。
常用的并行通信方式包括消息传递接口MPI、共享内存等。
3. 并行合并并行合并是指将多个子任务的计算结果合并为最终的结果的过程。
在并行合并过程中，需要考虑合并方式以及结果的正确性验证等问题。
四、并行计算算法的分析方法1. 速度up与加速比速度up表示并行计算与串行计算相比的计算速度提升程度。
加速比表示并行计算中处理单元数量增加时，计算速度相对于串行计算的提升比例。
通过对速度up与加速比的分析，可以评估并行算法的性能优劣。
2. 并行性的度量与评估并行性是指并行计算中各个子任务可以同时进行的程度。
通过对并行性的度量与评估，可以确定并行计算算法的最佳并行度。
分布式计算系统中的并行算法设计
分布式计算系统中的并行算法设计随着互联网的普及，人们对于数据的处理需求越来越高，如何有效地利用多台计算机进行数据处理成为了一项热门的研究领域。
分布式计算系统（Distributed Computing System）因此应运而生。
分布式计算系统是由多个计算机组成的计算集群，这些计算机协同工作，共同完成运算任务。
而在分布式计算系统中，算法设计就显得格外重要，因为只有优秀的算法才能够合理地利用计算机资源完成计算任务。
本文将介绍分布式计算系统中的并行算法设计，探究优秀算法背后的设计思路。
一、并行算法设计的基本思路并行算法是指通过分割计算任务，让多台计算机同时执行不同的计算任务，以提高计算速度的一种算法，在分布式计算系统中广泛应用。
在设计并行算法时，需要考虑以下几个方面：1.分解任务：将大型任务分解为若干小型任务，以便各台计算机分别执行。
2.确定任务执行时间：根据不同的任务特点和计算机性能等因素，对任务进行评估，确定各个任务需要执行的时间。
3.任务分配：根据各台计算机的性能、负荷等因素，将任务分配至合适的计算机上执行。
4.任务调度：协调各个计算机的任务进度，避免重复计算和数据竞争等问题。
二、并行算法设计的常见方法在实际运用中，有多种方法可供选择，常见的并行算法设计方法有以下几种：1.分治法：将大问题拆分成若干小问题，分配给多个计算机分别处理，最终将结果汇总得到解决方案。
例如，在搜索引擎中，将任务分解为若干个关键词的搜索，每个计算机处理自己负责的关键词，最后将结果合并。
2.流水线法：将大型任务划分成若干阶段，各个计算机处理不同的阶段，对于同一阶段的数据，多个计算机同时处理。
例如，在图像处理中，可以将图像处理分成几个阶段，交给多个计算机依次处理，以提高处理速度。
3.蒙特卡罗方法：通过统计随机事件的数量来估计概率和结果。
这种方法适合于处理难以精确计算的问题，例如在金融领域中的股票交易预测。
4.并行搜索法：在算法搜索中，将搜索任务分为若干部分，交由多个计算机分别搜索，最终将结果合并。
并行算法的设计与分析课件
2.3 分治策略
n设计思想
• 将原问题划分成若干个相同的子问题分而治之，若子问题仍然
较大，则可以反复递归应用分治策略处理这些子问题，直至子 问题易求解。
n求解步骤
• 将输入划分成若干个规模相等的子问题； • 同时(并行地)递归求解这些子问题； • 并行地归并子问题的解成为原问题的解。
n示例
• SIMD-SM模型上的FFT递归算法
Parallel Algorithms 3 / Ch2
2.1 平衡树方法
n算法2.1 SIMD-SM上求最大值算法
Begin for k=m-1 to 0 do for j=2k to 2k+1-1 par-do A[j]=max{A[2j], A[2j+1]} end for end for
end
时间分析 t(n)=m×O(1)=O(logn) p(n)=n/2 c(n)=O(nlogn) 非成本最优
2023/10/19
Y.Xu Copyright
USTC
Parallel Algorithms 4 / Ch2
2.1 平衡树方法
前缀和
n 问题定义
n个元素{x1,x2,…,xn}，前缀和是n个部分和： Si=x1*x2*…*xi, 1≤i≤n 这里*可以是＋或×
for j=1 to n/2h par-do B[h,j]=B[h-1,2j-1]*B[h-1,2j]
end for end for
时间分析:
(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]
高性能运算中的并行算法设计
高性能运算中的并行算法设计随着计算机性能的不断提高，对于大规模复杂计算的需求也不断增加，而并行计算技术作为一种有效的解决方案得到了广泛应用。
在高性能运算中，设计高效的并行算法是实现优秀性能的关键。
本文将从算法设计的角度出发，介绍高性能运算中的并行算法设计方法，并探讨并行算法优化的主要手段。
一、并行算法设计的基本思想并行算法是指将单个算法任务划分为若干个可并行执行的子任务，并利用多个计算单元同时处理这些子任务，从而提高计算效率。
基于这一思想，设计并行算法需要考虑以下几个方面：1. 任务分解与调度：将单个算法任务分解为若干个可并行执行的子任务，并合理安排和调度这些任务的执行顺序，以达到最优的执行效率。
2. 数据分布与同步：将算法数据分布到各个计算单元中，同时保证这些计算单元间的数据同步和交换，以确保算法正确性和执行效率。
3. 存储管理与通信优化：设计合理的存储管理方法和通信优化方案，以充分利用计算资源，降低存储和通信带宽的开销，提高算法性能。
二、并行算法设计的主要手段为了提高并行算法的效率，一般需要采用以下几种优化手段：1. 并行化框架设计：选择适合的并行计算框架和编程模型，如MPI、OpenMP、CUDA等，以充分发挥计算机的多核计算能力，加速算法的执行。
2. 线程和进程优化：通过选择合适的线程和进程数目，以及动态调整线程的执行顺序、优先级和任务调度策略等，充分利用计算资源，提高并行算法的效率。
3. 任务分解和负载均衡优化：通过合理的任务分解和任务调度策略，使各个计算单元间的任务负载均衡，以尽可能避免性能瓶颈和出现空闲计算资源等现象，提高并行算法的效率。
4. 数据分布和同步优化：通过合理的数据分布和同步策略，减少计算单元间的数据交换和同步开销，提高并行算法的效率。
5. 存储管理和通信优化：通过采用高效的存储管理方法和通信优化方案，减少存储和通信带宽的开销，提高算法性能。
三、并行算法优化案例分析以下是两个常见的并行算法优化案例：1. 矩阵乘法算法的并行化优化矩阵乘法是计算机科学中一个非常重要的数学问题，其计算量相对较大，因此对于大规模矩阵乘法的计算，通常需要采用并行算法进行优化。
《并行程序设计导论》第四章
并行程序设计导论第四章：并行算法的设计与分析并行算法是并行程序设计的核心，它直接影响着程序的性能和效率。
本章将介绍并行算法的设计方法，分析并行算法的性能，并探讨如何评估并行算法的效率。
一、并行算法的设计方法1.分治法分治法是一种常见的并行算法设计方法，它将问题分解成若干个子问题，分别解决后再合并结果。
分治法的关键在于子问题的划分和结果的合并。
在并行计算中，分治法可以充分利用多核处理器的并行性，提高程序的执行效率。
2.流水线法流水线法是一种将计算过程分解成多个阶段，每个阶段由不同的处理器并行执行的算法设计方法。
在流水线法中，数据在各个阶段之间流动，每个阶段只处理部分数据。
这种方法可以充分利用处理器的计算能力，提高程序的执行效率。
3.数据并行法数据并行法是一种将数据分解成多个部分，每个部分由不同的处理器并行处理的算法设计方法。
在数据并行法中，每个处理器处理相同的数据结构，执行相同的操作。
这种方法可以充分利用处理器的计算能力，提高程序的执行效率。
二、并行算法的性能分析1.时间复杂度时间复杂度是衡量算法性能的一个重要指标，它表示算法执行时间与输入规模之间的关系。
在并行算法中，时间复杂度通常表示为多个处理器执行时间的总和。
对于一个并行算法，我们希望其时间复杂度尽可能低，以提高程序的执行效率。
2.加速比加速比是衡量并行算法性能的另一个重要指标，它表示并行算法执行时间与最优串行算法执行时间的比值。
加速比越高，说明并行算法的性能越好。
在实际应用中，我们希望并行算法的加速比尽可能接近处理器的核心数量。
3.可扩展性可扩展性是衡量并行算法性能的另一个重要指标，它表示算法在增加处理器数量时的性能变化。
对于一个好的并行算法，我们希望其在增加处理器数量时，性能能够得到有效提升。
三、并行算法的效率评估1.性能模型性能模型是一种用于评估并行算法效率的工具，它将算法的性能与处理器数量、数据规模等因素联系起来。
通过性能模型，我们可以预测并行算法在不同条件下的性能表现，为算法设计和优化提供依据。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
都是双调序列。
ak
Batcher定理：
设序列a1,…,an,an+1,…, a2n是一个双调序列, 记 bi=min{ai, ai+n} ==> MIN={b1,…,bn}, ci=max{ai, ai+n} ==> MAX={c1,…,cn}, 则有： (1) bi≤cj ，1≤i, j≤n； (2) MIN和MAX序列仍是双调的。
并行算法的设计与分析
第4章 排序与选择网络
4.1 Batcher归并和排序网络
4.1.1 比较操作和[0,1]原理 1. Batcher比较器
– 比较和条件交换操作: CCI – 比较器网络：用Batcher比较器连成的，完成某一功能的网络 – 假定：每次每个元素只能与另一个元素比较 – 比较器网络的参数：比较器数目、延迟级数 2. [0, 1]原理(定理4.1): 如果一个n输入的网络能排序所有2n种{0,1}序列，那么它也能排序n个 数的任意序列。
奇偶排序 5
双调对接比较
分组Batcher奇偶排序
3.分组选择网络的正确性定理
P.129 定理4.4
4. 复杂性分析
分组选择网络比较器数目
分组选择延迟级数
4.2.2 平衡分组选择网络
1. 平衡分组选择过程
① 将n个输入数据划分成g=n/m个长度为m的子序列；
② 使用Batcher奇偶排序网络对g个子序列排序； ③ 将所有有序子序列形成双调序列，进行两两对接；使用 Batcher定理形成MAX,MIN序列，弃去MAX序列，调用 Batcher双调排序网络成对地归并MIN序列得到有序序列； ④ 重复步③ ~ ④ ，直至恰好包含所需的m个 最小元素为止。 特点: (1) 用双调排序网络取代奇偶排序网络(第1次除外)。 (2) 减少了比较器的级数。
3. 双调排序网络（BSN）
对输入长度为n的数据序列，逐次使用双调归并网络进行并 行归并。 示例：BSN(n=8)，其中标有×的比较器按降序输出。
8 3 1 5 3 8 1 3 1 2 3 4
5
1 7 2 4 6
5
8 7 6 4 2
7 2 4 6
5 6 7 8
双调排序网络的复杂性
比较器数目CsBIT(n): CsBIT(n)= CsBIT(「n/2 |)+ CsBIT(| n/2 」)+CMBIT(n ), n>=2 当n=2t时，解上述递归方程得：
4.1.3 双调归并网络
2. 双调归并递归网络构造 (依据Batcher定理)
2n个输入的双调序列两两比较形成2个大小为n的MIN和MAX序列。 并行递归地归并MIN和MAX双调序列，直到输入序列为2个元素为止。
MIN MAX
双 调 序 列
MIN MAX
MIN MAX MIN MAX
4.1.3 双调归并网络
2. 分组选择网络示例（n=16, m=4）
13 7 1 10 2 4 1 7 10 13 2 4 8 11 3 5 9 15 6 12 14 16 分组Batcher奇偶排序 取MIN 1 7 4 2 2 3 5 9 6 双调对接比较 取MIN 3 5 6 9 4 3 1 2 4
7
1
B(4)
11 8 15 3 9 6 12 16 14 分组
2. 奇偶排序网络（OESN） 对输入长度为n的数据序列，逐次使用奇偶归并网络进行并 行归并。 示例： OESN (n=8)
3 8 5 1 3 8 1 5 2 7 1 3 5 8 2 4 6 7 1 2 3 4 5 6 7 8
7 2
4 6
4 6
奇偶排序网络的复杂性
比较器数目CsOE(n):
M OE
– 当m=n=2t时，展开，推得：
M M M 1 COE (n, n) 2COE (n / 2, n / 2) n 1 2 C ( n / 2 , n / 2 ) ( n 1 ) OE 2 2 M M 2COE (n / 2, n / 2) (n 1) 2(2COE (n / 4, n / 4) n / 2 1) (n 1) M 2 2 COE (n / 2 2 , n / 2 2 ) (n 2) (n 1) ... M M 2t COE (n / 2t , n / 2t ) (n 2i ) nCOE (1,1) n 2i i 0 i 0 i 0 t 1 t 1 t 1
4.1.2 奇偶递归归并网络
1. 递归网络构造 有序序列A: a1,a2,…,an B: b1,b2,…,bm 奇偶递归归并（算法）思想： (1) A, B中奇数编号元素进入奇归并器, 对这些奇数编号元素递归地进行 奇偶归并,直到输入元素数为2止; (2) A, B中偶数编号元素进入偶归并器， 对这些偶数编号元素递归地进行 奇偶归并,直到输入元素数为2止; (3) 将步(1)奇归并器的输出与步(2)偶 归并器的输出进行交叉并行比较. 注: (m,n)规模划一分为二：
n 1 n 1
log n
n M 1 D ( BIT log n ) log n 2 i 1
4.1.4 Batcher排序网络
1. 排序网络原理（算法）——倍增技术应用 (1) 将n个输入数看成长度分别为1的n个有序序列：对n个输入 数进行两两比较，以形成长度分别为21的n/21个有序序列。
(2) 利用奇偶归并网络或者双调归并网络对长度为21的有序序 列进行两两归并，形成长度分别为22的n/22个有序序列。
(3) 依次类推，第i次排序时，利用奇偶归并网络或者双调归并 网络对长度为2i-1的有序序列进行两两归并，形成长度分别为 2i的n/2i个有序序列。
(4) 最后，利用奇偶归并网络或者双调归并网络，归并长度分 别为n/21的21个有序序列，以最终获得20=1个完整的长度为n 的有序序列。
4
5 9 6 3 3
5 6
9
双调对接比较 取MIN
双调对接比较 分组Batcher双调排序 取MIN
4.平衡分组选择网络复杂性分析
平衡分组选择网络比较器数目
平衡分组选择网络延迟级数
注：平衡分组选择网络比分组选择网络快了O(logm)倍。
MIN比较器数
MAX比较器数本级两两源自较器数当n=2t时 延迟级数
D
M BIT
M M 1 DBIT ( n / 2) 1 (1 DBIT ( n / 2 2 ))
0 ( n) M M 1 max D ( n / 2 ), D BIT BIT ( n / 2)
m / 2, n / 2奇 m / 2, n / 2偶
4.1.2 奇偶递归归并网络
2. 示例：m=n=4， A=(2,4,6,8)， B=(0,1,3,5)， (4, 4)奇偶归并2×(2, 2)奇偶归并 ＋ 1级交叉并行比较。 2 4 6 8 0 1 3 5 2 0 6 3 4 1 8 5 0 2 3 6 1 4 5 8 0 2 3 6 1 4 5 8 0 1 2 3 4 5 6 8
CsOE(n)= CsOE(「n/2 |)+ CsOE(| n /2」)+CMOE(「n/2 |, | n /2」 ), n>=2
当n=2t 时，解上述递归方程得：
延迟级数DsOE(n): 当n=2t时，展开有： DsOE(n)= DsOE(2t)=∑t i=1 DMOE(2i-1, 2i-1)=（logn+log2n）/2 Knuth推出，一般地DsOE(n):
n tn (n 1) n log n 1
4.1.2 奇偶递归归并网络
3. 复杂性分析 延迟级数：穿过网络任一路线上的最多层次数 0 m 0或n＝0 M DOE (m, n) 1 m n 1 1 maxD M ( m / 2 , n / 2 ), D M ( m / 2 , n / 2 ) 其他 OE OE – 一般地有
3. 示例: 双调序列(8,6,4,2,0,1,3,5)的(4,4)双调（递归）归并网络
8 6
4 2 8 0 6 1
MIN归并
0 8
0 1 2 3
1 6
3 4 2 5
2个(2,2)双调归并网络 MAX归并
0 1
3 5
4 3
2 5
两两比较
4 5
6 8
4.1.3 双调归并网络
4. 复杂性分析
比较器数目
2. 平衡分组选择网络示例 P.130 (n=16, m=4)
13 7 1 10 2 4
1
7 10 13 2 4 8 11 3 5 9 15 6 12 14 16
1 7
B(4) 双调排序
1 2
4 7 1
4
2
B(4)
11 8 15 3 9 6 12 16 14 分组 分组Batcher奇偶排序
2
3
5 奇偶排序
M M DOE (m, n) 1 DOE (m / 2, n / 2)
– 当m=n=2t时，展开，可以解得： M DOE (n, n) logn 1
4.1.3 双调归并网络
1. 定义及定理
定义: 一个序列a1,a2,…,an是双调序列(Bitonic Sequence)，如果： (1) 存在一个ak(1≤k≤n), 使得a1≥…≥ak≤…≤an成立；或者 (2) 循环移位序列使之能够满足条件(1)。 示例： 序列(1,3,5,7,8,6,4,2,0), (7,8,6,4,2,0,1,3,5) 和 (1,2,3,4,5,6,7,8)
1.基于划分原理的(m,n)-选择递归过程 ① 将n个输入数据划分成若干个 (≥ n/m)大小相等的子序列； ② 使用Batcher排序网络对各子 序列排序； ③ 将有序子序列两两对接形成 双调序列，对这些双调序列 使用 Batcher定理进行两两比较交换形 成MAX,MIN序列，弃去MAX序 列；再使用Batcher排序（归并） 网络将MIN序列排成有序序列； ④ 重复③直至MIN序列恰好包 含所需的m个最小元素为止。