1. 划分设计技术

1.1均匀划分技术

n个元素A[1..n]分成p组，每组A[(i-1)n/p+1..in/p]，i=1~p

示例：MIMD-SM模型上的PSRS排序

    begin

       (1)均匀划分：将n个元素A[1..n]均匀划分成p段，每个p_i处理

                             A[(i-1)n/p+1..in/p]

       (2)局部排序：p_i调用串行排序算法对A[(i-1)n/p+1..in/p]排序

       (3)选取样本：p_i从其有序子序列A[(i-1)n/p+1..in/p]中选取p个样本元素

       (4)样本排序：用一台处理器对p²个样本元素进行串行排序

       (5)选择主元：用一台处理器从排好序的样本序列中选取p-1个主元，并

                              播送给其他p_i

       (6)主元划分：p_i按主元将有序段A[(i-1)n/p+1..in/p]划分成p段

       (7)全局交换：各处理器将其有序段按段号交换到对应的处理器中

       (8)归并排序：各处理器对接收到的元素进行归并排序

    end.

PSRS排序过程。N=27，p=3，PSRS排序如下：

1.2方根划分技术

n个元素A[1..n]分成A[(i-1)n^(1/2)+1..in^(1/2)]，i=1~n^(1/2)

1.3对数划分技术

n个元素A[1..n]分成A[(i-1)logn+1..ilogn]，i=1~n/logn

1.4功能划分技术

n个元素A[1..n]分成等长的p组，每组满足某种特性。

2. 分治设计技术

并行分治设计步骤：

§ 将输入划分成若干个规模相等的子问题；

§ 同时(并行地)递归求解这些子问题；

§ 并行地归并子问题的解，直至得到原问题的解。

3. 平衡树设计技术

以树的叶结点为输入，中间结点为处理结点，由叶向根或由根向叶逐层进行并行处理。

4. 倍增设计技术

Ø  又称指针跳跃(pointerjumping)技术，特别适合于处理链表或有向树之类的数据结构；

Ø  当递归调用时，所要处理数据之间的距离逐步加倍，经过k步后即可完成距离为2^k的所有数据的计算。

5. 流水线设计技术

Ø  将算法流程划分成p个前后衔接的任务片断，每个任务片断的输出作为下一个任务片断的输入；

Ø  所有任务片断按同样的速率产生出结果。