并行处理算法

㈠ 并发算法之并行排序

大部分排序算法都是串行执行的，当排序元素很多时，使用并行排序算法可以有效利用CPU，提高运算效率，但将串行算法改成并行算法将会极大的增加原有算法的复杂度。

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

冒泡排序：如果数据较小，会逐步被交换到前面，对于大的数字会下沉，交换到数组的尾部。

在每次迭代交换过程中，由于每次交换的两个元素存在数据冲突，对于每个元素，它既可能与前面的元素交换，也可能与后面的元素交换，因此很难直接改成并行算法。如果能够解开这种数据的相关性，就可以更容易的使用并行算法，奇偶交换排序就是基于这种思想的。

对于奇偶交换排序，它将排序过程分成两个阶段，奇交换和偶交换。奇交换总是比较奇数索引及其相邻的后续元素，而偶交换总是比较偶数索引及其相邻的后续元素。并且奇交换和偶交换会成对出现，这样才能保证比较和交换涉及到数组中的每一个元素。在每个阶段内，所有的比较和交换是没有数据相关性的，每次比较和交换都可以独立执行。

flag用来记录当前迭代释放发生了数据交换，start用来表示奇交换或偶交换。初始start=0，表示进行偶交换，每次迭代结束切换start状态。如果上次比较交换发生了数据交换，或当前正在进行的是奇交换，循环不会停止，直到不再发生交换，并且当前进行的是偶交换为止。

2、改进的插入排序：希尔排序

插入排序思想：一个未排序的数组可以分为两部分，前半部分是已排序的，后半部分是未排序的，在进行排序时，只需在未排序的部分中选择一个元素，将其插入到前面有序的数组中即可。最终未排序的部分越来越少，直至为0排序完成。

插入排序很难并行化，因为上一次的数据插入依赖于上一次得到的有序序列，多个步骤之间无法并行。

希尔排序将整个数组根据间隔h分割为若干个子数组，子数组相互穿插在一起，每次排序时分别对每一个子数组进行排序。每次排序时总是交换间隔为h的两个元素。在每组排序完成后，可以递减h的值，进行下轮排序，直到h=1，此时等价于一次插入排序。

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

改造成并行希尔排序：

--参考文献《实战Java高并发程序设计》

㈡ 用并行可实现的算法有哪些

首先，应用的场合和解决的问题不一样。分布式计算比较倾向于在计算寻找模式的东西，穷举暴力之类的计算。分布式的计算被分解后的小任务互相之间有独立性，节点之间的结果几乎不互相影响，实时性要求不高。而并行计算则比较倾向于一些海量数据进行分析处理的场合，每个节点的每一个任务块都是必要的，计算的结果相互影响，要求每个节点的计算结果要绝对正确，并且在时间上做到同步。举例来说，像MD5破解，就比较适合使用大规模的分布式计算来穷举，但对海量日志数据进行处理来分析用户行为就比较适合并行计算处理。 其次，实现方式区别比较大。分布式计算会是一个比较松散的结构，并行计算则是各节点之间通过高速网络或其它总线之类的东西连接。因此并行计算一般在企业内部进行，而分布式计算可能会跨越局域网，或者直接部署在互联网上，节点之间几乎不互相通信。很多公益性的项目，就是的使用分布式计算的方式在互联网上实现，比如以寻找外星人为目的的SETI项目。

㈢ 并行计算的定义

并行计算（Parallel Computing）是指同时使用多种计算资源解决计算问题的过程，是提高计算机系统计算速度和处理能力的一种有效手段。它的基本思想是用多个处理器来协同求解同一问题，即将被求解的问题分解成若干个部分，各部分均由一个独立的处理机来并行计算。并行计算系统既可以是专门设计的、含有多个处理器的超级计算机，也可以是以某种方式互连的若干台的独立计算机构成的集群。通过并行计算集群完成数据的处理，再将处理的结果返回给用户。
并行计算可分为时间上的并行和空间上的并行。
时间上的并行：是指流水线技术，比如说工厂生产食品的时候步骤分为：
1． 清洗：将食品冲洗干净。
2． 消毒：将食品进行消毒处理。
3． 切割：将食品切成小块。
4． 包装：将食品装入包装袋。
如果不采用流水线，一个食品完成上述四个步骤后，下一个食品才进行处理，耗时且影响效率。但是采用流水线技术，就可以同时处理四个食品。这就是并行算法中的时间并行，在同一时间启动两个或两个以上的操作，大大提高计算性能。
l 空间上的并行：是指多个处理机并发的执行计算，即通过网络将两个以上的处理机连接起来，达到同时计算同一个任务的不同部分，或者单个处理机无法解决的大型问题。
比如小李准备在植树节种三棵树，如果小李1个人需要6个小时才能完成任务，植树节当天他叫来了好朋友小红、小王，三个人同时开始挖坑植树，2个小时后每个人都完成了一颗植树任务，这就是并行算法中的空间并行，将一个大任务分割成多个相同的子任务，来加快问题解决速度。