并行算法的原理

㈠ 并行算法并行算法简介

在计算机科学中，算法被定义为解决问题的一种方法和步骤。并行算法则是指在多处理器的并行计算机系统中，多个处理器协同工作以解决同一问题的策略和步骤。在自然界中，并行现象普遍存在，关键在于能否有效利用这种特性。然而，由于人类思维模式和问题解决方法往往倾向于串行，加上并行算法理论尚未完全成熟，使得过去的研究更多是基于问题出现后才去探索，缺乏前瞻性。

历史上，1970至1980年代，对并行算法的研究达到了高潮，但进入90年代，其热度有所下降。然而，当前并行算法又重新成为研究焦点。随着技术的进步，人们现在能够自行构建个人计算机集群（PC cluster），利用学到的理论知识解决实际问题，不再局限于理论探讨。这既带来了新的机遇，也提出了新的挑战，要求我们不断探索并提升并行算法的效率和实用性，以满足日益增长的需求。

并行算法就是用多台处理机 联合求解问题的方法和步骤,其执行过程是将给定的问题首先分解成若干个尽量相互独立的子问 题,然后使用多台计算机同时求解它,从而最终求得原问题的解.

㈡ pso的并行算法

与大多数随机优化算法相似，当适应值评价函数的计算量比较大时，PSO算法的计算量会很大。为了解决该问题，研究者提出了并行PSO算法。与并行遗传算法类似，并行PSO算法也可以有三种并行群体模型：主从并行模型、岛屿群体模型和邻接模型。
Schutte采用同步实现方式，在计算完一代中所有点的适应值之后才进入下一代。这种并行方法虽然实现简单，但常常会导致并行效率很差。故而有人提出异步方式的并行算法，可以在对数值精度影响不大的条件下提高PSO算法的并行性能。这两种方式采用的都是主从并行模型，其中异步方式在求解上耦合性更高，更容易产生通信瓶颈。
Baskar提出一种两个子种群并行演化的并发PSO算法，其中一个子种群采用原始的PSO算法，另一个子种群采用基于适应值距离比的PSO算法（FDR-PSO）；两个子种群之间频繁地进行信息交换。而El-Abd研究了在子种群中采用局部邻域版本的协作PSO算法，并研究了多种信息交换的方式及其对算法性能的影响。黄芳提出一种基于岛屿群体模型的并行PSO算法，并引入一种集中式迁移策略，提高了求解效率，同时改善了早收敛现象。
Li提出延迟交换信息的并行算法属于邻接模型，该算法可以提高速度，但可能使得解的质量变差。

㈢ 并发算法之并行排序

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

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

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

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

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

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

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

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

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

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

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

改造成并行希尔排序：

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

㈣ 并行算法的并行算法的研究内容

(1) 并行计算模型 并行算法作为一门学科，首先研究的是并行计算模型。并行计算模型是算法设计者与体系结构研究者之间的一个桥梁，是并行算法设计和分析的基础。它屏蔽了并行机之间的差异，从并行机中抽取若干个能反映计算特性的可计算或可测量的参数，并按照模型所定义的计算行为构造成本函数，以此进行算法的复杂度分析。
并行计算模型的第一代是共享存储模型，如SIMD-SM和MIMD-SM的一些计算模型，模型参数主要是CPU的单位计算时间，这样科学家可以忽略一些细节，集中精力设计算法。第二代是分布存储模型。在这个阶段，人们逐渐意识到对并行计算机性能带来影响的不仅仅是CPU，还有通信。因此如何把不同的通信性能抽象成模型参数，是这个阶段的研究重点。第三代是分布共享存储模型，也是我们目前研究所处的阶段。随着网络技术的发展，通信延迟固然还有影响，但对并行带来的影响不再像当年那样重要，注重计算系统的多层次存储特性的影响。
(2) 设计技术并行算法研究的第二部分是并行算法的设计技术。虽然并行算法研究还不是太成熟，但并行算法的设计依然是有章可循的，例如划分法、分治法、平衡树法、倍增法/指针跳跃法、流水线法破对称法等都是常用的设计并行算法的方法。另外人们还可以根据问题的特性来选择适合的设计方法。
（3）并行算法分为多机并行和多线程并行。多机并行，如MPI技术；多线程并行，如OpenMP技术。
以上是并行算法的常规研究内容。