南京大学：《并行处理技术——分布式与并行计算 Distributed and Parallel computing（并行计算——结构、算法、编程）》课程教学资源（课件讲稿）第五章 并行算法的一般设计方法

第五章并行算法的一般设计方法 Case Study: (1)排序(Sot) (2)选择 (Select) (3)搜索 (Search) (4) 匹配 (Matching

第五章 并行算法的一般设计方法 Case Study: （1）排序 （Sort） （2）选择 （Select） （3）搜索 （Search） （4）匹配 （Matching）

第五章并行算法的一般设计方法 5.1串行算法的直接并行化 5.2从问题描述开始设计并行算法 5.3借用已有算法求解新问题

第五章 并行算法的一般设计方法 5.1 串行算法的直接并行化 5.2 从问题描述开始设计并行算法 5.3 借用已有算法求解新问题

5.1串行算法的直接并行化 5.1.1设计方法描述

5.1串行算法的直接并行化 5.1.1 设计方法描述

设计方法的描述 *方法描述 *发掘和利用现有串行算法中的并行性，直接将串行算法 改造为并行算法。 *评注 *由串行算法直接并行化的方法是并行算法设计的最常用 方法之一； *不是所有的串行算法都可以直接并行化的； *一个好的串行算法并不能并行化为一个好的并行算法； *许多数值串行算法可以并行化为有效的数值并行算法。 6 2011/10/18

 方法描述  发掘和利用现有串行算法中的并行性，直接将串行算法 改造为并行算法。  评注  由串行算法直接并行化的方法是并行算法设计的最常用 方法之一；  不是所有的串行算法都可以直接并行化的；  一个好的串行算法并不能并行化为一个好的并行算法；  许多数值串行算法可以并行化为有效的数值并行算法。 6 2011/10/18 设计方法的描述

5.1串行算法的直接并行化 5.1.1设计方法描述 5.1.2快排序算法的并行化 5.1.3枚举排序算法的并行化

5.1串行算法的直接并行化 5.1.1 设计方法描述 5.1.2 快排序算法的并行化 5.1.3 枚举排序算法的并行化

Case Study:快排序算法的并行化 *排序算法 *在计算机科学与数学中，一个排序算法(Sorting algorithm)是一种能将一串数据依照特定排序方式的一 种算法。最常用到的排序方式是数值顺序以及字典顺序。 有效的排序算法在一些算法（例如搜索算法与合并算法） 中是重要的，如此这些算法才能得到正确解答。排序算 法也用在处理文字数据以及产生人类可读的输出结果。 8 2011/10/18

 排序算法  在计算机科学与数学中，一个排序算法（Sorting algorithm）是一种能将一串数据依照特定排序方式的一 种算法。最常用到的排序方式是数值顺序以及字典顺序。 有效的排序算法在一些算法（例如搜索算法与合并算法） 中是重要的，如此这些算法才能得到正确解答。排序算 法也用在处理文字数据以及产生人类可读的输出结果。 8 2011/10/18 Case Study:快排序算法的并行化

Case Study:快排序算法的并行化 *快速排序及其串行算法 *快速排序(Quick Sort)是一种最基本的排序算法，它的 基本思想是：在当前无序区[1，]中取一个记录作为比 较的“基准”（一般取第一个、最后一个或中间位置的 元素)，用此基准将当前的无序区R[1,]划分成左右两 个无序的子区R[1,i1]和R[i,n](1sisn),且左边的无序子 区中记录的所有关键字均小于等于基准的关键字，右边 的无序子区中记录的所有关键字均大于等于基准的关键 字；当R[1,i1]和R[i,n]非空时，分别对它们重复上述的 划分过程，直到所有的无序子区中的记录均排好序为止。 9 2011/10/18

 快速排序及其串行算法  快速排序（Quick Sort）是一种最基本的排序算法，它的 基本思想是：在当前无序区R[1，n]中取一个记录作为比 较的“基准”（一般取第一个、最后一个或中间位置的 元素），用此基准将当前的无序区R[1，n]划分成左右两 个无序的子区R[1，i‐1]和R[i，n](1≤i≤n)，且左边的无序子 区中记录的所有关键字均小于等于基准的关键字，右边 的无序子区中记录的所有关键字均大于等于基准的关键 字；当R[1，i‐1]和R[i，n]非空时，分别对它们重复上述的 划分过程，直到所有的无序子区中的记录均排好序为止。 9 2011/10/18 Case Study:快排序算法的并行化

Case Study:快排序算法的并行化 法51单处理机上快速排序算 法 procedure partition(data,k,l) 输入：无序数组data[1,n] Begin 输出：有序数组data[1,n] (1)pivo=data[l] Begin (2)i=k-1 call procedure quicksort(data,1,n) (3)forj=k tol-1 do End if data[j]spivothen procedure quicksort(data,i,j) i=i+1 Begin exchangedata[i]and data[j] (1)if (i<j)then end if (1.1)r=partition(data,i,j) end for (1.2)quicksort(data,i,r-1); (1.3)quicksort(data,r+1,j); (4)exchangedata[i+1]and data[l] end if (5)returni+1 End End 10 2011/10/18

Case Study:快排序算法的并行化 10 2011/10/18 算法5.1 单处理机上快速排序算 法 输入：无序数组data[1,n] 输出：有序数组data[1,n] Begin call procedure quicksort(data,1,n) End procedure quicksort(data,i,j) Begin (1)if (i<j) then (1.1)r = partition(data,i,j) (1.2)quicksort(data,i,r‐1); (1.3)quicksort(data,r+1,j); end if End procedure partition(data,k,l) Begin (1)pivo=data[l] (2)i=k‐1 (3)forj=k tol‐1 do if data[j] ≤pivothen i=i+1 exchangedata[i] and data[j] end if end for (4)exchangedata[i+1] and data[l] (5)returni+1 End

Case Study:快排序算法的并行化 米 快速排序算法的性能主要决定于输入数组的划分是 否均衡，而这与基准元素的选择密切相关。 *在最坏的情况下，划分的结果是一边有1个元素， 而另一边有0个元素（除去被选中的基准元素)。如 果每次递归排序中的划分都产生这种极度的不平衡， 那么整个算法的复杂度将是日(n2)。 *在最好的情况下，每次划分都使得输入数组平均分 为两半，那么算法的复杂度为O(nlogn)。 *在一般的情况下该算法仍能保持O（(nlogn)的复杂 度，只不过其具有更高的常数因子。 11 2011/10/18

11 2011/10/18 Case Study:快排序算法的并行化  快速排序算法的性能主要决定于输入数组的划分是 否均衡，而这与基准元素的选择密切相关。  在最坏的情况下，划分的结果是一边有n‐1个元素， 而另一边有0个元素（除去被选中的基准元素）。如 果每次递归排序中的划分都产生这种极度的不平衡， 那么整个算法的复杂度将是Θ（݊ଶ）。  在最好的情况下，每次划分都使得输入数组平均分 为两半，那么算法的复杂度为O（nlogn）。  在一般的情况下该算法仍能保持O（nlogn）的复杂 度，只不过其具有更高的常数因子

Case Study::快排序算法的并行化 *快速排序的并行算法 *快速排序算法并行化的一个简单思想是，对每次划分过 后所得到的两个序列分别使用两个处理器完成递归排序。 *例如对一个长为n的序列，首先划分得到两个长为n/2的 序列，将其交给两个处理器分别处理；而后进一步划分 得到四个长为/4的序列，再分别交给四个处理器处理； 如此递归下去最终得到排序好的序列。当然这里举的是 理想的划分情况，如果划分步骤不能达到平均分配的目 的，那么排序的效率会相对较差。 12 2011/10/18

 快速排序的并行算法  快速排序算法并行化的一个简单思想是，对每次划分过 后所得到的两个序列分别使用两个处理器完成递归排序。  例如对一个长为n的序列，首先划分得到两个长为n/2的 序列，将其交给两个处理器分别处理；而后进一步划分 得到四个长为n/4的序列，再分别交给四个处理器处理； 如此递归下去最终得到排序好的序列。当然这里举的是 理想的划分情况，如果划分步骤不能达到平均分配的目 的，那么排序的效率会相对较差。 12 2011/10/18 Case Study:快排序算法的并行化