并行算法的探索与实践

### 并行算法的探索与实践 在并行算法的世界里，有众多强大的工具和方法，它们在不同的场景中发挥着重要作用。下面将详细介绍并行前缀计算、搜索算法、排序算法、顺序统计以及傅里叶变换等方面的内容。 #### 1. 并行前缀计算 在并行前缀计算算法中，求和操作必要时可被任何其他结合操作替代。通过数学归纳法可以证明，对算法 `parPrefix` 的第 15 行进行修改： ```plaintext pref ixList[ j] : = temp −2∧(i −1)] ⊗temp[ j]; ``` 其中 `⊗` 是任意二元结合操作，这将得到 `list[1] ⊗list[2] ⊗... ⊗list[ j]` 的值，即 `∑(i = 1 到 j) list[i]`，对于所有 `j = 1, 2, ..., N` 都成立。 #### 2. 搜索算法 搜索算法在不同类型的序列中有着不同的实现方式，下面分别介绍无序序列和有序序列的搜索算法。 - **无序序列搜索**： - **算法思路**：将整个搜索范围 `[1..N]` 分成 `p` 部分，在每个子数组中按照顺序搜索算法进行搜索。 - **代码实现**： ```pascal const N=100; type Mass = array[1..N] of integer; function parSequentialSearch( list :Mass; target :integer):integer; // list — analyzed array of N elements // target — target value var i , j , left , right ,r:integer; begin r:=0; parallel for i:=1 to p do begin left :=(i−1)∗Ceil(N/p)+1; right:=i∗Ceil(N/p); if right>N then right:=N; // sequential search in list [ left .. right] for j:=left to right do if list [ j]=target then r:=j ; end; result:=r; end; ``` - **算法特性**：变量 `j` 的循环需要执行 `⌈N/p⌉` 次比较，算法执行时间为 `O(N/p)`，加速比 `Sp = p`，成本 `C p = p · O(N/p) = O(N)`，说明该并行算法在无序序列搜索中是成本最优的。 - **有序序列搜索**： - **二分搜索**：将整个数组分成 `p` 部分，在每个子数组中进行二分搜索，称为 `parBinarySearch` 算法。执行时间为 `Tp = ⌈log₂(N/p)⌉`，加速比 `Sp = O(log₂N / log₂(N/p))`，成本 `C p = O(p log₂(N/p))`。需要注意的是，该算法的成本超过了 `BinarySearch` 算法，但有算法可以将有序数组的搜索成本降低到 `O(p logₚ₊₁(N + 1))`。 - **(p + 1)-ary 搜索**：在每次算法执行步骤中，`p` 次比较的结果可将数组分成 `p + 1` 个子数组，然后递归地对包含键值的段进行下一步操作。存在一种算法，能在 `CREW` 机器上使用 `p` 个处理器，在时间 `O(log₂(N + 1) / log₂(p + 1))` 内解决有序数组中目标元素的搜索问题。 - **证明过程**：使用数学归纳法，引入谓词 `P(m) = {在大小为 N 的有序数组中进行并行搜索的算法在 m 个顺序步骤内完成操作}`。 - **基础步骤**：当 `m = 1` 且 `p ⩾N` 时，算法显然在一个顺序步骤内完成操作。 - **归纳步骤**：假设对于大小为 `(p + 1)ᵏ - 1` 的数组，`k` 步足够。对于大小为 `(p + 1)ᵏ⁺¹ - 1` 的数组，处理器 `i`（`1 ⩽i ⩽p`）比较 `list[i(p + 1)ᵏ]` 与目标值。基于 `p` 次并行比较的结果，可得出目标元素包含在大小为 `(p + 1)ᵏ - 1` 的子数组中。根据归纳假设，还需要 `k` 步完成算法操作，即对于大小为 `(p + 1)ᵏ⁺¹ - 1` 的数组，`k + 1` 步足够。因此，谓词 `P(m)` 对于所有自然数 `m` 都为真。 - **算法实现**： ```pascal const N=100; type Mass = array[1..N+1] of integer; MassTemp = array[0..p+1] of integer; function parPSearch( list :Mass; target :integer):integer; // list — analysed array of N elements // target — target value var temp,s:MassTemp; left , right , i ,m,k:integer; begin left :=1; right:=N; k:=0; m:=Ceil(Log2(N+1)/Log2(p+1)); s[0]:=0; // the value of the boundary s[p+1]:=1; // elements of the array s while ( left<=right) and (k=0) do begin temp[0]:= left −1; parallel for i:=1 to p do begin temp[ i ]:=( left−1)+i∗(p+1)^(m−1); //ith processor compares // the value target with list [temp[ i ]] if temp[ i]<=right then case compare( list [temp[ i ]] , target) of −1: s[ i ]:=0; 0: k:=temp[ i ]; +1: s[ i ]:=1; end else begin temp[ i ]:=right+1; s[ i ]:=1; end; if s[ i]<>s[i−1] then begin left:=temp[i−1]+1; right:=temp[ i]−1; end; if ( i=p) and (s[ i]<>s[ i+1]) then left:=temp[ i]+1; end; m:=m−1; end; result:=k; end; ``` 以下是无序序列搜索和有序序列二分搜索的对比表格： | 搜索类型 | 算法 | 执行时间 | 加速比 | 成本 | | ---- | ---- | ---- | ---- | ---- | | 无序序列 | `parSequentialSearch` | `O(N/p)` | `p` | `O(N)` | | 有序序列 | `parBinarySearch` | `⌈log₂(N/p)⌉` | `O(log₂N / log₂(N/p))` | `O(p log₂(N/p))` | 下面是无序序列搜索的 mermaid 流程图： ```mermaid graph TD; A[开始] --> B[初始化 r = 0]; B --> C[并行 for i = 1 to p]; C --> D[计算 left 和 right]; D --> E[right > N ?]; E -- 是 --> F[right = N]; E -- 否 --> G[在 list[left..right] 中顺序搜索]; F --> G; G --> H[list[j] = target ?]; H -- 是 --> I[r = j]; H -- 否 --> J[继续搜索]; J --> G; I --> K[结束循环]; ```