GPU并行计算优化：提升局部PageRank性能

193 浏览量更新于2024-07-15 收藏 256KB PDF 举报

本文是一篇研究论文，主要探讨了如何在通用图形处理单元（GPGPU）环境下提升马尔可夫链蒙特卡洛方法在解决局部PageRank问题上的性能。PageRank是Google搜索引擎的重要算法，用于评估网页的重要性，而局部PageRank则是针对特定网络子图内的节点排序。传统的PageRank计算可能因网络中大量悬挂节点（dangling vertices）导致存储空间需求大，从而拖慢整个过程。文章提出了一种新的策略，旨在通过有效地管理悬挂节点的存储空间和优化马尔可夫链的进程来提高计算效率。作者注意到，当网络中悬挂节点过多时，它们占据了大量内存，这是性能瓶颈的关键因素。为了解决这个问题，他们设计了一种排序策略，通过压缩存储空间并减少马尔可夫链迭代的复杂性来提升计算性能。论文的核心贡献包括： 1. 悬挂节点管理和压缩：提出了一个有效的排序算法，可以减少不必要的存储需求，避免对悬挂节点进行不必要的计算，从而节省内存资源。 2. 并行化与优化：将算法进行了并行化处理，利用GPGPU的并行计算能力，大幅度提升了计算速度，减少了整体计算时间。 3. 性能评估：通过实验研究，展示了新方法在实际应用中的性能提升，包括处理大规模数据集时的速度和内存使用效率的对比分析。这篇论文不仅关注理论创新，还重视实际效果的验证，对于那些在搜索引擎优化、社交网络分析等领域处理大规模图数据的工程师和研究人员来说，提供了有价值的技术参考。同时，它也揭示了如何将GPU技术应用于计算密集型问题，展示了计算硬件与算法优化之间的紧密联系。

kþ1ðÞ

¼ cM

kðÞ

þ 1−cðÞv: (3)

To facilitate the following discussion, transform Equation 3 to

kþ1ðÞ

¼ Ax

kðÞ

þ f; (4)

where A = cM

and f =(1− c)v.

If we set x

(0)

= 0, the PageRank vector can be expressed as Neumann series:

x ¼ ∑

∞

i¼0

f; (5)

where A

¼ max

1≤ j≤n

∑

i¼1



, A

¼ ∑

j¼1



, A

∞

= max

1 ≤ i ≤ n

, f = max

1 ≤ i ≤ n

, and ρ(A) denote the spectral radius of matrix A. Because ρ(A)=c <1,

it is well‐known that Neumann series ∑

∞

i¼0

f is convergent.

If only the mth component of x in Equation 5 is considered, we have

¼ f

þ ∑

¼1

þ ∑

¼1

þ … þ ∑

; ::;i

¼1

…a

k−1

þ …; (6)

where a

∈ A and f

∈ f. Therefore, a selected vertex can independently compute the PageRank value by Equation 6, which is the mathematical form

of local PageRank problem.

2.2

Markov chain Monte Carlo method for local PageRank computations

In this subsection, we introduce how to compute the local PageRank problem by MCMC method, ie, obtain the component x

of Equation 6 by

random walks. We first assume that a

= p

and p

∈ P and b

∈ B, where P is a Markov matrix and B is the adjoin matrix of P. In addition,

the entries of Markov matrix and adjoin matrix should satisfy Equation 7:

>0 ; a

≠0

≥0 ; a

¼ 0

and

; a

≠0

¼ 0 ; a

¼ 0

; (7)

Therefore, Equation 6 can be represented as

¼ f

þ ∑

∞

k¼0

∑

¼1

∑

¼1

…∑

¼1

…b

k−1

…p

k−1

: (8)

Consider the problem of evaluating the inner product of a given vector g with the vector solution of Equation 5

g; xðÞ¼∑

α¼1

; (9)

where g ∈ R

. If we use MCMC method to calculate PageRank values, we should construct a random process way to compute a result as the desired

inner product. Assume a random walk S as follows

→s

→…→s

→…; (10)

where s

∈ {1, 2, … , n}, for j = 1,2,…. The transition probabilities of state P(s

= α)=p

and P(s

= β| s

k − 1

= α)=p

αβ

are defined as follows

αβ

≥0

∑

β¼1

αβ

¼ 1

(

and

αβ

≥0

∑

β¼1

αβ

¼ 1

(

(11)

Clearly, the entries p

αβ

of Equation 11 can satisfy Equation 7 as well.

We now define random variables W

and θ

as follows

¼ W

k−1



k−1

and θ



¼ ∑

∞

; where W

¼ 1: (12)

Therefore, we have the expectation of θ

Eθ



¼ f

þ ∑

∞

k¼0

∑

¼1

∑

¼1

…∑

¼1

…b

k−1

…p

k−1

: (13)

Thus, Eθ

= x

, when we set g as g

= 1 and g

=0, ∀ i ≠ m. Each calculation of expectation of θ

can be considered as a random walk.

Thus, local PageRank problem can be solved by MCMC method. The MCMC method simulates possible pathways for a single vertex as the

vertex is the termination of forward surfing. We can construct variant transition matrixes to approximate the PageRank scores, where the transition

matrices satisfy Equations 7 and 11. In this paper, we adopt the transition probability depending on the entries weighted

LAI ET AL. 3of15

剩余14页未读，继续阅读

weixin_38714162

粉丝: 2
资源: 937

GPU并行计算优化：提升局部PageRank性能

基于GPU的稀疏矩阵存储格式优化研究.pdf

图数据挖掘在社交网络的应用研究.pdf

bigDataExperiments:Hadoop上的各种图形分析算法，这是我在IIIT Delhi的Summer '15实习生的一部分

单机GPU加速图形处理：均衡复制技术

云计算环境下大规模图数据的BSP并行迭代处理系统

大规模图处理系统Pregel详解

图并行计算架构

图论与并行计算：图算法并行化策略的5大案例研究

大规模网络分析加速器：MATLAB网络工具箱的并行计算魔法

【Python数据结构与图形算法】：数据如何在图形中流动

最新资源