随着处理的数据量呈爆炸式地增长,如何衡量这些数据的重要性非常关键。PageRank算法被视为解决此类问题的核心算法之一。PageRank值的获取已经成为许多应用中的核心环节,例如搜索引擎、生物制药、推荐系统。以上应用场景中需要对所有数据的PageRank值进行计算。而在另外一些场景中只对部分顶点的PageRank值感兴趣,例如语义相关性分析、邮件过滤、论文检索。本文对需要全局所有顶点的PageRank值进行计算的问题称PageRank问题,只需要对部分目标顶点的PageRank值进行计算的问题定义为Local PageRank问题。如何高效地对这两类问题进行求解的有着重要的现实意义。本文基于GPGPU环境下探讨如何提高对这两类问题的求解效率。GPU可以提供了比CPU强大许多的浮点计算能力,已经被广泛利用到了高性能计算的各个领域。其中在PageRank问题的求解优化中,本文提出PSCR计算方法应用在GPGPU环境下高效进行PageRank计算。PSCR将图中各顶点按照顶点的出度和入度划分成若干个顶点集合并分别处理。对于包含中入度和高入度的顶点的顶点集合利用静态并行和动态并行进行多线程处理,解决单顶点计算量过大的瓶颈。对于包含了低入度的顶点的顶点集合利用顶点计算合并的方式,利用单线程处理若干顶点的方式,解决低入度顶点之间计算负载不均的问题。此外我们将悬停顶点进行合并独立计算有效地减少了计算开销和数据传递的开销。实验结果证明这一系列优化有效地提高了PageRank问题的计算效率,与现有的方法相比计算效率有明显的提升。在对Local PageRank问题的研究过程,本文首先将其转化为求解线性方程组单个分量求解的问题,然后引入蒙特卡罗方法对其进行求解,并分析了蒙特卡罗方法在求解Local PageRank问题中的相关性质。随后在具体的算法实现过程中,本文结合算法本身的特性和GPGPU的体系结构提出了一系列优化策略,包括了方差感知策略、顶点重排策略、Shared Memory策略、均匀概率策略。其中方差感知策略的算法根据相关性质和例子分析提出的利用随机游走的方差变化率动态的判断该顶点所需要的计算资源,以解决各顶点之间计算负载不均的问题;在实现中让每个线程块独立计算避免同步带来的开销。顶点重排策略解决了悬停点造成的存储空间消耗大和随机游走计算复杂度高的问题。Shared Memory策略利用低差异序列为确定性序列的特性,利用Shared Memory存储低差异序列,减少对Global Memory的数据访问开销。均匀概率策略用于图频繁变化的场景中进行快速判断不同顶点之间的重要性排名问题。实验结果表明本文的优化策略对于Local PageRank问题的求解效率在相应场景下有显著地提高。