插入排序希尔排序

并行算法虽然可以充分发挥多核CPU的性能但并非所有的运算都可以改造成并行的形式。

那么什么样的运算是无法并行的呢简单来说执行过程中有数据相关性的运算都是无法完美并行的。

假如程序中现在有两个数B和C计算(BC)×B/2这个运算过程就是无法并行的。

原因是如果BC没有执行完成则永远算不出(BC)×B这就是数据相关性。

如果线程执行时所需的数据存在这种依赖关系那么就没有办法将它们完美地并行化。

下图诠释了这个道理

遇到这种情况时有没有什么补救措施呢答案是肯定的那就是借鉴日常生产中的流水线思想。

比如现在要生产一批小玩偶。

小玩偶的制作分为四个步骤第一组装身体第二在身体上安装四肢和头部第三给组装完成的玩偶穿上一件漂亮的衣服第四包装出货。

为了加快制作进度我们不可能叫四个人同时加工一个玩具因为这四个步骤有着严重的依赖关系。

如果没有身体就没有地方安装四肢如果没有组装完成就不能穿衣服如果没有穿上衣服就不能包装发货。

因此找四个人来做一个玩偶是毫无意义的。

但是如果你现在要制作的不是一个玩偶而是一万个玩偶情况就不同了。

你可以找四个人第一个人只负责组装身体完成后交给第二个人第二个人只负责安装头部和四肢完成后交第三人第三人只负责穿衣服完成后交第四人第四人只负责包装发货。

这样所有人都可以一起工作共同完成任务而整个时间周期也能缩短到原来的1/4左右这就是流水线的思想。

一旦流水线满载每次只需要一步假设一个玩偶需要四步就可以产生一个玩偶如下图所示

类似的思想可以借鉴到程序开发中。

即使(BC)×B/2无法并行但是如果你需要计算一大堆B和C的值你依然可以将它流水化。

首先将计算过程拆分为三个步骤

P1:ABCP2:DA×BP3:DD/2

上述步骤中的P1、P2和P3均在单独的线程中计算并且每个线程只负责自己的工作。

此时P3的计算结果就是最终需要的答案。

P1接收B和C的值并求和将结果输入给P2。

P2求乘积后输入给P3。

P3将D除以2得到最终值。

一旦这条流水线建立只需要一个计算步骤就可以得到(BC)×B/2的结果。

为了实现这个功能我们需要定义一个在线程间携带结果进行信息交换的载体

上述代码中P1取得封装了两个操作数的Msg并求和将结果传递给乘法线程P2第9行。

当没有数据需要处理时P1等待。

最后是提交任务的主线程这里我们提交100万个请求让线程组进行计算

上述代码第13行将数据提交给P1加法线程开启流水线的计算。

在多核或者分布式场景中这种设计思路可以有效地将有依赖关系的操作分配在不同的线程中进行计算尽可能利用多核的优势。

2、并行搜索

搜索几乎是每一个软件都必不可少的功能。

对于有序数据通常可以采用二分查找法。

对于无序数据则只能挨个查找。

本节将讨论有关并行的无序数组的搜索实现。

给定一个数组我们要查找满足条件的元素。

对于串行程序来说只要遍历一下数组就可以得到结果。

但如果要使用并行方式则需要额外增加一些线程间的通信机制使各个线程可以有效运行。

一种简单的策略就是将原始数据集合按照期望的线程数进行分割。

如果我们计划使用两个线程搜索那么就可以把一个数组或集合分割成两个。

每个线程各自独立搜索当其中有一个线程找到数据后立即返回结果即可。

定义线程池、线程数量及存放结果的变量result。

在result中我们会保存符合条件的元素在arr数组中的下标默认为-1表示没有找到给定元素

并行搜索会要求每个线程查找arr中的一段因此搜索函数必须指定线程需要搜索的起始位置和结束位置

上述代码第4行首先通过result判断是否已经有其他线程找到了需要的结果。

如果已经找到则立即返回并不再查找。

如果没有找到则进行下一步搜索。

第7行的条件成立则表示当前线程找到了需要的数据那么就会将结果保存到result变量中。

这里使用CAS操作如果设置失败则表示其他线程已经先找到了结果。

因此可以无视失败的情况找到结果后返回即可。

最后是pSearch()方法它是并行查找函数根据线程数量对arr数组进行划分并建立对应的任务提交给线程池处理

上述代码中使用了JDK内置的Future模式其中第48行将原始数组arr划分为若干段并根据划分结果建立子任务。

每一个子任务都会返回一个Future对象通过Future对象可以获得线程组得到的最终结果。

在这里由于线程之间通过result共享彼此的信息只要一个线程成功返回后其他线程都会立即返回。

因此不会出现由于排在前面的任务长时间无法结束而导致无法立即获取搜索结果的情况。

3、并行排序

排序是一项常用的操作。

应用程序在运行时可能无时无刻不在进行排序操作。

排序的算法有很多但这里并不打算一一介绍它们。

大部分排序算法都是串行执行的。

当排序元素很多时若使用并行算法代替串行算法显然可以更有效地利用CPU。

但将串行算法改造成并行算法并非易事甚至会极大地增加原有算法的复杂度。

这里将介绍几种相对简单但是也足以让人眼前一亮的平行排序算法。

3.1、分离数据相关性奇偶交换排序

在介绍奇偶排序前首先让我们看一下熟悉的冒泡排序。

在这里假设我们需要将数组从小到大排序。

冒泡排序的操作类似水中的气泡上浮在冒泡排序的执行过程中如果数字较小它就会逐步被交换到前面去相反大的数字则会下沉交换到数组的末尾。

可以看到在每次迭代的交换过程中由于每次交换的两个元素存在数据冲突对于每个元素它既可能与前面的元素交换也可能和后面的元素交换因此很难直接改造成并行算法。

如果能够解开这种数据的相关性就可以比较容易地使用并行算法来实现类似的排序。

奇偶交换排序就是基于这种思想的。

对于奇偶交换排序来说它将排序过程分为两个阶段奇交换和偶交换。

奇交换总是比较奇数索引及其相邻的后续元素而偶交换总是比较偶数索引及其相邻的后续元素。

并且奇交换和偶交换会成对出现这样才能保证比较和交换涉及数组中的每一个元素。

从上图可以看到由于将整个比较交换独立分割为奇阶段和偶阶段使得在每一个阶段内所有的比较和交换是没有数据相关性的因此每一次比较和交换都可以独立执行也就可以并行化了。

其中exchFlag用来记录当前迭代是否发生了数据交换而start用来表示是奇交换还是偶交换。

初始时start为0表示进行偶交换每次迭代结束后切换start的状态。

如果上一次比较交换发生了数据交换或者当前正在进行的是奇交换循环就不会停止直到程序不再发生交换并且当前进行的是偶交换为止表示奇偶交换已经成对出现。

上述代码第9行定义了奇偶排序的任务类该任务类的主要工作是数据比较和必要的交换第1823行。

并行排序的主体是pOddEvenSort()方法它使用CountDownLatch记录线程数量对于每一次迭代使用单独的线程对每一次元素比较和交换进行操作。

在下一次迭代开始前必须等待上一次迭代所有线程执行完成。

插入排序也是一种很常用的排序算法。

它的基本思想是一个未排序的数组当然也可以是链表可以分为两个部分前半部分是已经排序的后半部分是未排序的。

在排序时只需要在未排序的部分中选择一个元素将其插入前面有序的数组中即可。

最终未排序的部分会越来越少直到为0排序就完成了。

初始时可以假设已排序部分就是第一个元素。

插入排序示意图如下图所示

上述代码第6行提取准备插入的元素也就是未排序序列中的第一个元素然后在已排序队列中找到这个元素的插入位置第810行插入第13行即可。

简单的插入排序是很难并行化的。

因为这一次的数据插入依赖于上一次得到的有序序列所以多个步骤之间无法并行。

为此我们可以对插入排序进行扩展这就是希尔排序。

希尔排序将整个数组根据间隔h分割为若干个子数组它们相互穿插在一起每一次排序时分别对每一个子数组进行排序。

当h为3时希尔排序将整个数组分为交织在一起的三个子数组如下图所示

其中所有的方块为一个子数组所有的圆形和所有的三角形分别组成另外两个子数组。

每次排序时总是交换间隔为h的两个元素。

在每一组排序完成后可以递减h的值进行下一轮更加精细的排序。

直到h为1此时等价于一次插入排序。

希尔排序的一个主要优点是即使一个较小的元素在数组的末尾由于每次元素移动都以h为间隔进行因此数组末尾的小元素可以在很少的交换次数下就被置换到最接近元素最终位置的地方。

上述代码第46行计算一个合适的h值接着正式进行希尔排序。

第8行的for循环进行间隔为h的插入排序每次排序结束后递减h的值第20行。

直到h为1退化为插入排序。

很显然希尔排序每次都针对不同的子数组进行排序各个子数组之间是完全独立的。

因此很容易改写成并行程序

上述代码中ShellSortTask为并行任务。

ShellSortTask的作用是根据给定的起始位置和h对子数组进行排序因此可以完全并行化。

为控制线程数量这里定义并行主函数pShellSort()在h大于或等于4时使用并行线程第40行否则退化为传统的插入排序。

4、并行算法矩阵乘法

Linus认为并行程序目前只有在服务端程序和图像处理领域有发展的空间。

且不论这种说法是否有局限性从中也可以看出并行对于这两个应用领域的重要性。

而对于图像处理来说矩阵运行是其中必不可少的重要数学方法。

当然除图像处理外矩阵运算在神经网络、模式识别等领域也有着广泛的用途。

在这里我将向大家介绍矩阵运算的典型代表——矩阵乘法的并行化实现。

在矩阵乘法中第一个矩阵的列数和第二个矩阵的行数必须是相同的。

矩阵A和矩阵B相乘其中矩阵A为4行2列矩阵B为2行4列它们相乘后得到的是4行4列的矩阵并且新矩阵中每一个元素为矩阵A和矩阵B对应行列的乘积求和如下图所示

如果需要进行并行计算一种简单的策略是将矩阵A进行水平分割得到子矩阵A1和A2矩阵B进行垂直分割得到子矩阵B1和B2。

此时我们只要分别计算这些子矩阵的乘积再将结果进行拼接就能得到原始矩阵A和B的乘积。

下图展示了这种并行计算的策略

当然这个过程是可以反复进行的。

为了计算矩阵A1×B1我们还可以进一步将矩阵A1和矩阵B1分解直到我们认为子矩阵的大小已经在可接受范围内。