随机并行算法(Randomized Algorithm)

发表于

(并行与分布式计算八)

随机并行算法简介

随机算法：使用了随机数生成器(random-number generator)的算法

随机算法的分析基于概率论(Probability Theory)基本事实

伯努利随机试验:

  • $Pr{X \geq m} = \sum{j=m}^n (_j^n)p^jq^{n-j}$

切尔诺夫界/不等式(Chernoff bounds):

  • $P_r{ X \leq (1 - \epsilon)pn } \leq e^{-\epsilon^2np/2}$
  • $P_r{ X \geq (1 + \epsilon)pn } \leq e^{-\epsilon^2np/3}$

PRAM模型需要加入一些特征

  • 主要为每个处理器能够在一步时间内产生有限范围内的随机数
  • 设正整数范围为[1, 2, …, M], 限制产生的随机数长度为O(logn)bits，其中n是输入的长度
  • 这样的随机数能够在一个内存位置中出现，因此可用O(1)步完成
  • k个处理器产生k的独立的随机数
  • randomized PRAM

high-likelihood bounds(高可能性边界):

  • 一个随机并行算法需要的资源上界 $f(n)$: 对于任意的输入n，该算法使用的资源数量有 $1 - n^{-c}$的概率最多为 $\alpha f(n)$, 其中 $\alpha$ 和c是正的常数
  • $O(f(n))$

两种类型的随机算法:

  • Las Vegas(拉斯维加斯)算法
    • 总是产生正确的解
    • 性能用期望资源使用数或使用资源的上界的概率衡量
  • Monte Carlo(蒙特卡洛)算法
    • 允许存在误差，但保持在足够小的概率

  • 优点：简单、易实现、易并行、性能往往比较好

  • 缺点：性能也随机，快慢不总是一样

在图中找分数阶的独立集(Fractional Independent Set)

可平面图G = (V, E): 可映射到平面上且边不相交

aim: to identify a large independent set of G consisting excusively of low-degree vertices

  • 图G的顶点集合为V，找出集合 $X \subseteq V$ ，使得

  1. X中每一顶点v的度小于等于某个常量d

  2. 集合X是独立的，即X中任意两个定点不相邻(没有边连接)

  3. 集合X满足 $|X| \geq c|V|$(对某个正常数c)

  • X即为图G的一个分数阶的独立集

给定图G=(V,E)，定义其分数阶的独立集X满足下面三个条件：

  • 低度性：存在常数d，使X是顶点度数小于d的顶点组成的V子集
  • 独立性：X中的任意两点都在G中不相邻
  • 分数阶：存在正的常数c，使|X|不小于c|V|

引理9.1: 平面图G = (V, E), |V| > 2, 则 $|E| \leq 3|V| - 6$

定理9.2: 任意平面图G = (V, E)都能在线性串行时间内建立一个分数阶独立集X

  • 令 $V_d$ 为G的一个阶不大于d的顶点子集(d >= 6)
  • 令$V_h = V - Vd$ ，则 $\sum{v \in V_h}deg(v) \geq (d + 1)|V_h|$
  • $(d + 1)|Vh| \leq \sum{v \in V}deg(v) \leq 6|V| - 12$
  • $|V_h| \leq (6|V| - 12)/(d + 1)$

  • $|v_d| = |V| - |V_h| \geq (d - 5)|V|/(d + 1)$

  • 构造分数阶独立集X：

  • 从 $V_d$ 中选择任意的顶点v，除去所有v在 $V_d$ 中邻接的顶点
  • 再选 $V_d$ 的另外一个顶点重复以上步骤
  • 重复直到遍历 $V_d$ 中所有顶点
  • $|X| \geq |V_d|/(d + 1) \geq (d - 5)|V|/(d + 1)^2$，是|V|的函数

有向环(directed cycles)

求有向环G = (V, E)上的分数阶独立集

Algorithm 9.1

1
2
3
4
5
6
7
8
(Randomized Symmetry Breaking)
Input: A directed cycle G = (V, E) whose arcs are specified by an array S of length n.
Output: The set of vertices X = {v \in V | label(v) = 1}, which forms a fractional independent set with high probability.
begin
  for all v \in V pardo
    1. Assign label(v) = 1 or 0 randomly with equal probability.
    2. if (label(v) = 1 and label(S(v)) = 1) then set label(v) := 0
end

  • T(n) = O(1), W = O(n)

  • 复杂度分析

  • 独立的伯努利随机试验：n/2（两点距离>1即可）

  • 顶点被选（最终label为1）的概率：1/4
  • 在独立试验中的平均被选率：n/8

  • 最终被选的包括独立试验的和非独立试验的

  • $ P_r{|X| \leq \alpha n} \leq e^{-\beta n} $ (由Chernoff bounds得)

  • 其中$ 0 < \alpha < 1/8 $, $ \beta = (1 - 8\alpha)^2/16 $

可平面图(planar graphs)

求任意可平面图G = (V, E)上的分数阶独立集

Algorithm 9.2

1
2
3
4
5
6
7
8
9
10
11
12
13
(Fractional Independent Set)
Input: A planar graph G = (V, E) represented by its edge lists. The edges on the list of a vertex v are ordered counterclockwise as they appear around the vertex v in a planar embedding of G. 
Output: A labeled set of low-degree vertices forming a large independent set with high probability. 
begin
  1. for each vertex v in V pardo
    if (deg(v) <= 6) then set lowdeg(v) := 1
                     else set lowdeg(v) := 0
  2. for each vertex v in V pardo
    if (lowdeg(v) = 1) then Randomly assign label(v) := 0 or 1 with equal probability
  3. for each vertex v in V pardo
    if (label(v) = 1) then
      if (label(u) = 1 for some u on the list of v) then set label(v) := 0
end

  • T(n) = O(1), W = O(n)

  • 复杂度分析

  • 参数d取为6

  • 独立的伯努利随机试验：$|V_d|/36$（两点距离>2即可）
  • 成功率：1/27
  • 独立试验中的平均成功点数至少为： $|V_d|/36 * 1/27$

  • 最终被选的包括独立试验的和非独立试验的

  • $ P_r {|X| \leq \alpha n } \leq e^{-\beta n} $

  • $\alpha$ 和 $\beta$为常量

字符串匹配的随机并行算法

基本策略类似于hashing

  • hash函数将集合U映射到一个整数范围之内([1, 2, …, r])
  • u -> h(u)
  • 将长度为m的字符串映射为O(logm)比特的整数(fiingerprint)：两个不同的字符创映射到同一个整数的概率极其低(前提是hash函数选得好)

关键思想：

  • 指纹(Fingerprints): 把字符串匹配问题转换为固定几个整数的比较问题
  • 随机选质数，作为除数对指纹的整数求余，使余数的长度上界能固定
  • 用比较余数来代替比较指纹整数
  • 最终算法达到右面三个要求:
    • property 9.1: 对任意字符串 $X \in B$, $f_p(X)$ 由O(logm)比特组成，对每个$p \in S$
    • property 9.2: 随机选择 $\mathcal{F}$ 中的一个$f_p$，将两个不同的字符串X和Y映射到D中同一元素的概率非常小
    • property 9.3: 对每个$p \in S$, $f_p(X)$很容易并行地计算，对所有B中的字符串

指纹函数

  • 文本字符串T长度为n，模式字符串P长度为m，$m \leq n$

  • 确定P在T中出现的所有位置

  • 令集合B为T的所有长度为m的子字符串的集合，起始位置i($ 1 \leq i \leq n-m+1 $)

  • 问题转化成确定B中元素是否和P相同

  • 令 $\mathcal{F} = { fp }{p \in S}$为函数集合，其中 $f_p$ 将长度为m的字符串映射到值域D中

  • $\mathcal{F}$ 必须满足以下三个特性：
    • 1.对任意字符串 $X \in B$, $f_p(X)$ 由O(logm)比特组成，对每个$p \in S$
    • 2.随机选择 $\mathcal{F}$ 中的一个$f_p$，将两个不同的字符串X和Y映射到D中同一元素的概率非常小
    • 3.对每个$p \in S$, $f_p(X)$很容易并行地计算，对所有B中的字符串

$f_p(X)$称为字符串X的指纹(fingerprint)

满足以上性质的指纹函数

  • 由{0, 1}组成的字符串
  • 将{0, 1}映射到 整数环Z上的2*2矩阵
  • (满足性质2但不满足1和3)

$$ f(0) =
\left[
\begin{matrix}
1 & 0 \
1 & 1
\end{matrix}
\right]
$$

$$ f(1) =
\left[
\begin{matrix}
1 & 1 \
0 & 1
\end{matrix}
\right]
$$

  • 对字符串XY，f(XY)=f(X)f(Y)(Z上的矩阵乘法)
  • 指纹是一一对应的
  • 通过比较行内元素的大小，可以知道最后是0还是1（0是左大右小，1是左小右大）

  • 而矩阵f(0)和f(1)的逆是已知的，可以右乘最后一位的逆矩阵来从指纹中删除最后一位，从而可以依次知道倒数第1、2、3、…位

  • e.g.

    • X = 1011
    • f(X) = f(1)f(0)f(1)f(1)
    • f(X) = $
      \left[
      \begin{matrix}
      1 & 1 \
      0 & 1
      \end{matrix}
      \right]
      $$
      \left[
      \begin{matrix}
      1 & 0 \
      1 & 1
      \end{matrix}
      \right]
      $$
      \left[
      \begin{matrix}
      1 & 1 \
      0 & 1
      \end{matrix}
      \right]
      $$
      \left[
      \begin{matrix}
      1 & 1 \
      0 & 1
      \end{matrix}
      \right]
      $ = $
      \left[
      \begin{matrix}
      2 & 5 \
      1 & 3
      \end{matrix}
      \right]
      $

指纹的增长速度(不满足性质1)

  • X长度为m，则f(X)的每个元是不大于 $F{m+1}$ 的整数，其中 $F{m+1}$ 是第(m + 1)个斐波那契数($ F_1 = F2 = 1, F{m + 1} = Fm + F{m - 1} $)

  • f(X)的元会大至 $F_{m + 1} \approx \frac{\phi^{m+1}}{\sqrt{5}}$

  • $ \phi = \frac{1 + \sqrt{5}}{2} \approx 1.618… $

解决指纹增长过快的问题

  • 令p为[1, 2, …, M]内的素数，令 $Z_p$ 为模p的整数环

  • 定义 $f_p(X) = f(X)$ module p

  • e.g

    • X = (1011)^4, 长度为16
    • f(X) = $
      \left[
      \begin{matrix}
      206 & 575 \
      115 & 321
      \end{matrix}
      \right]
      $
    • 给定素数p = 7
    • f(X) = $
      \left[
      \begin{matrix}
      3 & 1 \
      3 & 6
      \end{matrix}
      \right]
      $

  • 引理9.4: 对任意整数 $m \geq 17$ , 有 $ \frac{m}{\ln m} \leq \pi(m) \leq 1.2551\frac{m}{\ln m} $

  • 引理9.5: 给定正数 $u \leq 2^m$, u的不等质因数的数量为 $\pi(m)$, 当 $m \geq 29$ 时

随机化匹配产生错误的概率

  • $f_p$为从函数集合 $\mathcal{F} = {f_p}$ 中随机选取的函数，其中p是范围[1, 2, …, M]内的素数

  • 任意两个长度为m的不同字符串产生错误匹配的概率不大于 $\frac{\pi(\lfloor2.776m\rfloor)}{\pi(M)}$, $m \geq 11$

  • 推论9.1: 选取的素数在$[1, 2, …, m^k]$范围内，则两个长度为m的字符串产生错误匹配的概率不大于 $\frac{3.48k}{m^{k-1}}$, k > 1

  • $\pi(\lceil2.776m\rceil) \leq 1.2551 \frac{2.776m}{\ln(2.776m)} \approx \frac{3.48m}{\ln(2.776m)}$

  • $\pi(m^k) \geq \frac{m^k}{\ln m^k} = \frac{m^k}{k\ln m}$

  • 随机选取的指纹函数 $f_p \in \mathcal{F}$, p为[1, 2, …, M]中的素数，t对字符串产生错误匹配的概率上界为 $\frac{\pi(\lceil2.776mt\rceil)}{\pi(M)}$, $mt \geq 11$

  • 推论9.2: 任意一个正整数常量k，$M = mt^k$, t对长度为m字符串产生错误匹配的概率为 $O(\frac{1}{t^{k-1}})$

Algorithm 9.4

1
2
3
4
5
6
7
8
9
10
11
12
(Monte Carlo String Matching)
Input: Two arrays T(1:n) and P(1:m) representing the text and the pattern strings, respectively, and an integer M.
Output: The array MATCH indicating all the positions where the pattern occurs in the text.
begin
  1. for 1 <= i <= n-m+1 pardo
       Set MATCH(i) := 0
  2. choose a random prime in the range [1, 2, ..., M], and compute f_p(P)
  3. for 1 <= i <= n-m+1 pardo
       Set L_l := f_p(T(i : i+m-1))
  4. for 1 <= i <= n-m+1 pardo
       if (L_l = f_p(P)) then Set MATCH(i) := 1
end

  • T(n) = O(logn), W(n) = O(n)

快速排序的随机并行算法

Algorithm 9.5

1
2
3
4
5
6
7
8
9
10
11
12
(Randomized Quicksort)
Input: An array A containing the n elements to be sorted.
Output: The Array A in sorted order.
begin
  1. if n <= 30 then sort A using any sorting algorithm and exit.
  2. Select a random element S(A) of A.
  3. for 1 <= i <= n pardo
       A(i) < S(A): Set mark(i) := 1
       A(i) > S(A): Set mark(i) := 0
  4. Compact the elements of A marked 1 at the beginning of A, followed by S(A), which is followed by the elements marked 0. Set k equal to the position of the element S(A).
  5. Recursively sort the subarrays A(1:k-1) and A(k+1:n).
end

  • $T(n) = O(log^2 n)$; $W(n) = O(nlogn)$