Processing math: 100%

随机并行算法(Randomized Algorithm)

(并行与分布式计算八)

随机并行算法简介

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

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

伯努利随机试验:

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

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

  • PrX(1ϵ)pneϵ2np/2
  • PrX(1+ϵ)pneϵ2np/3

PRAM模型需要加入一些特征

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

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

  • 一个随机并行算法需要的资源上界 f(n): 对于任意的输入n,该算法使用的资源数量有 1nc的概率最多为 αf(n), 其中 α 和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,找出集合 XV ,使得
  1. X中每一顶点v的度小于等于某个常量d

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

  3. 集合X满足 |X|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|3|V|6

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

  • Vd 为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$
  • |Vh|(6|V|12)/(d+1)
  • |vd|=|V||Vh|(d5)|V|/(d+1)

  • 构造分数阶独立集X:

  • Vd 中选择任意的顶点v,除去所有v在 Vd 中邻接的顶点
  • 再选 Vd 的另外一个顶点重复以上步骤
  • 重复直到遍历 Vd 中所有顶点
  • |X||Vd|/(d+1)(d5)|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
  • 最终被选的包括独立试验的和非独立试验的

  • Pr|X|αneβn (由Chernoff bounds得)

  • 其中0<α<1/8, β=(18α)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

  • 独立的伯努利随机试验:|Vd|/36(两点距离>2即可)
  • 成功率:1/27
  • 独立试验中的平均成功点数至少为: |Vd|/361/27
  • 最终被选的包括独立试验的和非独立试验的

  • Pr|X|αneβn

  • αβ为常量

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

基本策略类似于hashing

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

关键思想:

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

指纹函数

  • 文本字符串T长度为n,模式字符串P长度为m,mn
  • 确定P在T中出现的所有位置

  • 令集合B为T的所有长度为m的子字符串的集合,起始位置i(1inm+1)

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

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

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

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

满足以上性质的指纹函数

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

f(0)=[10 11]

f(1)=[11 01]

  • 对字符串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) = [11 01][10 11][11 01][11 01] = [25 13]

指纹的增长速度(不满足性质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)的元会大至 Fm+1ϕm+15

  • ϕ=1+521.618

解决指纹增长过快的问题

  • 令p为[1, 2, …, M]内的素数,令 Zp 为模p的整数环
  • 定义 fp(X)=f(X) module p

  • e.g

    • X = (1011)^4, 长度为16
    • f(X) = [206575 115321]
    • 给定素数p = 7
    • f(X) = [31 36]
  • 引理9.4: 对任意整数 m17 , 有 mlnmπ(m)1.2551mlnm

  • 引理9.5: 给定正数 u2m, u的不等质因数的数量为 π(m), 当 m29

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

  • fp为从函数集合 F=fp 中随机选取的函数,其中p是范围[1, 2, …, M]内的素数
  • 任意两个长度为m的不同字符串产生错误匹配的概率不大于 π(2.776m)π(M), m11

  • 推论9.1: 选取的素数在[1,2,,mk]范围内,则两个长度为m的字符串产生错误匹配的概率不大于 3.48kmk1, k > 1

  • π(2.776m)1.25512.776mln(2.776m)3.48mln(2.776m)
  • π(mk)mklnmk=mkklnm

  • 随机选取的指纹函数 fpF, p为[1, 2, …, M]中的素数,t对字符串产生错误匹配的概率上界为 π(2.776mt)π(M), mt11

  • 推论9.2: 任意一个正整数常量k,M=mtk, t对长度为m字符串产生错误匹配的概率为 O(1tk1)

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(log2n); W(n)=O(nlogn)