Realize the PageRank Algorithm in OpenMP

Introduction

Background

PageRank是Google创始人Larry Page和Sergey Brin在1996年创造的算法，起源于他们在斯坦福的一个关于开发有效搜索引擎的项目。
他们把万维网(World Wide Web)看作是一个巨大的文件集，在这个集中，文件与文件间有着复杂的超链接结构。因此万维网也可以抽象成一个巨大的有向图，节点代表各网页，而有向边则代表网页之间的超链接。如何通过节点在图中的位置来计算逼近它对应的重要性，是PageRank算法的主要目的。
在详细讨论pageRank算法以前，需要先阐述一些有关的基础概念与定义。首先，如何把万维网抽象成一个有向图对PageRank算法至关重要。因为，万维网的link structure可以确定每个节点在整个网络中的相对位置，而这个相对位置则为后续计算它的重要性提供了信息。
我们用节点(vertex)来代表网页，有向边(edge)来代表网页间的链接关系。由于网页之间的链接边(或 link)有两个方向，因此分别命名为forward link(outedge) 和 backlink(inedge)。下图示意了一个，由5个网页组成的网络的link structure：

图1：W.W.W as a directed graph

Principle

基于万维网link structure的这个结构特性，PageRank算法的核心思想应运而生。
既然网页之间相互链接，那么对于一个网页而言，每一个指向它的链接(inedge)都可以类似成一个学术引用，代表了它的重要性。但是与学术引用不同，网页并没有质量控制和发表成本等门槛。因此，如果只单用inedge的数量来表示重要性的话，所得出的重要性指标会很容易被操控篡改。仅仅是靠低成本地制造大量垃圾网页，使它们指向某一特定网页，便可以增加此网页的引用数量。
基于这个考虑，除了使用引用数目(inedge的数目)这个局部指标以外，还应该使用万维网的全局信息。因为涉及万维网巨大的整体结构，这部分信息难以被简单篡改，使得计算出的重要性更为robust。
由观察得知，一个网页的重要与否，取决于以下两个因素：

与学术引用类似，此网页是否有许多入链接，即是否很多网页都指向它
指向它的网页中，是否存在非常重要的网页。例如：某网页也许只有一个入链接，但此入链接是源自Wiki这样的权威网页
PageRank正是综合地考虑了网页的入链接数目这个局部指标，以及入链接网页重要性这个全局指标，来逼近一个网页的真实重要性。为了达到这一综合，此算法使用了重要性传递(rank propagation through links)这一思想，让rank依照万维网的结构动态流动直到稳定，所得的最终结果便是网页最后的重要性(或 Rank)。

PageRank Algorithm

basics

PageRank的定义
$R(u)=c\sum_{v\in{B_u}}\frac{R(v)}{N_v}$
$u:$ 某一个网页
$R:$ 此网页对应的PageRank值(此公式算出的PageRank为naive版本)
$c:$ 归一化系数
$B_u:$ 指向网页u的网页集合
$N_u=|F_u|$
$F_u:$ 网页u指向的网页集合

图2

如上图中:
$B_2=\{1, 3\}$
$F_1=\{2, 4\}$
$N_1=|F_1|=2$

Matrix Representation

为了能够高效地计算网络里各个网页的PageRank，需要把上一节中公式表达成矩阵运算形式。
首先，假设网络中一共包含了N 个网页。设 R 为一个向量，一共包含 N 个entries，它的每个entry均存储了对应网页的PageRank值。
$R_{N\times{1}}:$ 一个数组，负责存储每个网页的PageRank。
设一矩阵 $A_{N\times{N}}$ ，它存储了网络任意两个网页间的链接关系。
$\begin{eqnarray}A_{u,{v}}=\begin{cases} \frac{1}{N_v}, &if\ exsits\ an\ edge\ from\ v\ to\ u\cr 0, &if\ not \end{cases} \end{eqnarray}$
例如下图三中的网络所对应的矩阵 A 为：

图3

A_{4\times{4}}=\left[ \begin{matrix}0 & 0 & \frac{1}{3} & 0 \\ \frac{1}{2} & 0 & \frac{1}{3} & 0 \\ 0 & 1 & 0 & 0 \\ \frac{1}{2} & 0 & \frac{1}{3} & 1 \end{matrix} \right]

Computation Process

在有了矩阵表达后，原先计算PageRank的公式可以进行如下转换：
$R(u)=c\sum_{v\in{B_u}}\frac{R(v)}{N_v}\ \ \Longrightarrow\ \ R=cAR$
因此，在实际计算时，可以反复循环计算 R，直到收敛。即：
$R_{i+1}=cAR_i$
由 Power method convergence theorem可知，由于矩阵 A
可以看作是一个跳转概率矩阵，其每列都是一个网页对应的跳转概率分布，因此如下数列收敛：
$R,AR,A^2R,....A^kR$
即，按此方法计算PageRank，最终会到达一个稳定状态。此状态即使最后的网页重要性排序的结果。

interpretation

PageRank算法的核心是跳转矩阵 A。因为跳转矩阵 A 包含了网络中所有网页的链接关系，根据此链接关系（网页在网络中的位置），可直接推导出网页的重要性。它的每一列包含了一个网页所有的出边(outedges)，及每个出边所对应的概率。也可理解成，若用户当前位于此网页，那么下一时刻用户跳转到其他网页的概率分布。
而这个过程可以更形象地运用 Random Surfer Model来解释。Random Surfer Model模拟了用户在网络上随机浏览的概率分布。此处，随机浏览是说用户从任意的一个网页开始，按照跳转矩阵 A 中，对应网页的跳转概率分布来随机点击跳转到下一网页。用户持续重复这一行为知道被一个死循环困住。而在全过程中，每个网页被浏览的次数可以归一化为一个稳定的概率分布，这个分布即是最后的网页重要性。

Rank Sink

但是按照这个方法计算PageRank会出现一个问题，叫做 Rank Sink。网络中可能会存在由一些网页组成的子网络，这个网络只有入链接(inedges)而没有出链接，形成了一个闭环，如下图所示：

https://goo.gl/images/4hnXVL

当随机浏览的用户进入这个子网络时，他将被困住，一直在这个网络的网页里循环。因此，这些网页的PageRank会趋近于无限大，而这个子网络之外的网页的PageRank会下降，造成失真。

Optimalization

一个有效的解决办法是额外加入一个Escape Term E(u)。它和R(u)一样，也是一个跳转概率分布，通过融合R(u) 和 Escape Term E(u)，死循环可以被打破。相当于，当用户陷入一个死循环时，Escape Term E(u) 提供了随机跳出此循环的可能性。融合方法如下：
$R^{'}(u)=d\sum_{v\in{B_v}}\frac{R^{'}(v)}{N_v}+(1-d)E(u)\ \ \ \ \ ||R^{'}||_1=1$

Implementation in OpenMP

Motivation

此处，我使用OpenMP实现了PageRank的并行计算。
OpenMP是一个共享内存的并行计算模型，适用于多核的单节点并行。它支持多平台，计算中数据的分布与合成可以由 directives 自动处理，因此使用十分便捷，非常适合用来初步并行串行代码。

General Process

根据公式，计算PageRank的伪代码如下：

pseudo code

其中：

S:

initialization of PageRank

E:

Escape Term

d:

a scalar, accelerates convergence & miantains

||R||_1

Experiment Result

在一个有916,428个网页的网络上运行PageRank算法，在此网络中，共有5,105,039个链接。下图为并行与串行的时间对比，横轴为运行的次数，纵轴为每次运行对应的时间。为了保证客观，排除特殊情况，两个算法各独立运行15次。可以看出，并行提升了性能。
$Speedup:$ 1.4803
$Efficiency:$ 0.37

串行 vs. 并行

下图是 scaling factor，由于我的电脑只有四核，因此曲线的走势是合理的。

scaling factor

Analysis

由上面的分析可知，算法的 Speedup 非常不理想的。而这个性能的限制主要有两个因素：

Load imbalance overheads(负载不均衡)
Synchronization overheads(线程同步开销)

Load imbalance overheads

scheduling methods

上图展示了OpenMP的三种 scheduling methods：

Static
Dynamic
Guided
具体实现时，需要根据数据的具体分布来选择合适的scheduling methods，否则可能会降低算法的性能。
首先，在原始的数据上检验不同的scheduling methods对性能的影响。结果如下：

scheduling methods and performance

可以看出，由于负载较为均衡，此时用chunk较小的Dynamic方法反而会增大调度开销，降低性能。
然后，随机在原始网络上选出三个网页(节点)，每个网页手动添加一百万个随机入链接，增加网络的不均衡分布。当计算这个新的strewed数据时，每个iteration的计算量会严重不均衡。各个scheduling methods的运行时间如下：

imbalance data

可以看出，在计算量不均衡时，使用Dynamic更有优势，避免线程空闲。

Synchronization overheads

另一个影响性能的因素是代码的并行度。由于在实现这个算法时，为了避免data races ，在每个iteration中均用了atomic operation，造成了代码同步度的底下，降低了性能。
为了解决这个问题，可以先使每个iteration仅更新改变本地值，避免data races problem，在循环结束后做一个总的final synchronized reduction，以更新最终的全局共享变量。这个操作可以避免使用 atomic operation ，提高了代码的并行度。缺点是需要大量的内存来存放本地数据 ( $N\times{K}\times{8}$ )。
改进的算法与旧算法的性能对比如下：

Realize the PageRank Algorithm in OpenMP

Realize the PageRank Algorithm in OpenMP

Introduction

Background

Principle

PageRank Algorithm

basics

Matrix Representation

Computation Process

interpretation

Rank Sink

Optimalization

Implementation in OpenMP

Motivation

General Process

Experiment Result

Analysis

Load imbalance overheads

Synchronization overheads

Summary

PageRank:

Implementation in OpenMP: