(并行与分布式计算八)
随机并行算法简介
随机算法:使用了随机数生成器(random-number generator)的算法
随机算法的分析基于概率论(Probability Theory)基本事实
伯努利随机试验:
- $Pr{X \geq m} = \sum{j=m}^n (_j^n)p^jq^{n-j}$
切尔诺夫界/不等式(Chernoff bounds):
- PrX≤(1−ϵ)pn≤e−ϵ2np/2
- PrX≥(1+ϵ)pn≤e−ϵ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的概率最多为 α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,找出集合 X⊆V ,使得
X中每一顶点v的度小于等于某个常量d
集合X是独立的,即X中任意两个定点不相邻(没有边连接)
集合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|≥(d−5)|V|/(d+1)
构造分数阶独立集X:
- 从 Vd 中选择任意的顶点v,除去所有v在 Vd 中邻接的顶点
- 再选 Vd 的另外一个顶点重复以上步骤
- 重复直到遍历 Vd 中所有顶点
- |X|≥|Vd|/(d+1)≥(d−5)|V|/(d+1)2,是|V|的函数
有向环(directed cycles)
求有向环G = (V, E)上的分数阶独立集
Algorithm 9.1
|
|
- T(n) = O(1), W = O(n)
复杂度分析
独立的伯努利随机试验:n/2(两点距离>1即可)
- 顶点被选(最终label为1)的概率:1/4
- 在独立试验中的平均被选率:n/8
最终被选的包括独立试验的和非独立试验的
Pr|X|≤αn≤e−βn (由Chernoff bounds得)
- 其中0<α<1/8, β=(1−8α)2/16
可平面图(planar graphs)
求任意可平面图G = (V, E)上的分数阶独立集
Algorithm 9.2
|
|
- T(n) = O(1), W = O(n)
复杂度分析
参数d取为6
- 独立的伯努利随机试验:|Vd|/36(两点距离>2即可)
- 成功率:1/27
- 独立试验中的平均成功点数至少为: |Vd|/36∗1/27
最终被选的包括独立试验的和非独立试验的
Pr|X|≤αn≤e−βn
- α 和 β为常量
字符串匹配的随机并行算法
基本策略类似于hashing
- hash函数将集合U映射到一个整数范围之内([1, 2, …, r])
- u -> h(u)
- 将长度为m的字符串映射为O(logm)比特的整数(fiingerprint):两个不同的字符创映射到同一个整数的概率极其低(前提是hash函数选得好)
关键思想:
- 指纹(Fingerprints): 把字符串匹配问题转换为固定几个整数的比较问题
- 随机选质数,作为除数对指纹的整数求余,使余数的长度上界能固定
- 用比较余数来代替比较指纹整数
- 最终算法达到右面三个要求:
- property 9.1: 对任意字符串 X∈B, fp(X) 由O(logm)比特组成,对每个p∈S
- property 9.2: 随机选择 F 中的一个fp,将两个不同的字符串X和Y映射到D中同一元素的概率非常小
- property 9.3: 对每个p∈S, fp(X)很容易并行地计算,对所有B中的字符串
指纹函数
- 文本字符串T长度为n,模式字符串P长度为m,m≤n
确定P在T中出现的所有位置
令集合B为T的所有长度为m的子字符串的集合,起始位置i(1≤i≤n−m+1)
问题转化成确定B中元素是否和P相同
令 $\mathcal{F} = { fp }{p \in S}为函数集合,其中f_p$ 将长度为m的字符串映射到值域D中
- F 必须满足以下三个特性:
- 1.对任意字符串 X∈B, fp(X) 由O(logm)比特组成,对每个p∈S
- 2.随机选择 F 中的一个fp,将两个不同的字符串X和Y映射到D中同一元素的概率非常小
- 3.对每个p∈S, 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+1√5
- ϕ=1+√52≈1.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: 对任意整数 m≥17 , 有 mlnm≤π(m)≤1.2551mlnm
引理9.5: 给定正数 u≤2m, u的不等质因数的数量为 π(m), 当 m≥29 时
随机化匹配产生错误的概率
- fp为从函数集合 F=fp 中随机选取的函数,其中p是范围[1, 2, …, M]内的素数
任意两个长度为m的不同字符串产生错误匹配的概率不大于 π(⌊2.776m⌋)π(M), m≥11
推论9.1: 选取的素数在[1,2,…,mk]范围内,则两个长度为m的字符串产生错误匹配的概率不大于 3.48kmk−1, k > 1
- π(⌈2.776m⌉)≤1.25512.776mln(2.776m)≈3.48mln(2.776m)
π(mk)≥mklnmk=mkklnm
随机选取的指纹函数 fp∈F, p为[1, 2, …, M]中的素数,t对字符串产生错误匹配的概率上界为 π(⌈2.776mt⌉)π(M), mt≥11
推论9.2: 任意一个正整数常量k,M=mtk, t对长度为m字符串产生错误匹配的概率为 O(1tk−1)
Algorithm 9.4
|
|
- T(n) = O(logn), W(n) = O(n)
快速排序的随机并行算法
Algorithm 9.5
|
|
- T(n)=O(log2n); W(n)=O(nlogn)