Asynchronous iterative solution for dominant eigenvectors with applications in performance modelling and PageRank
Asynchronous iterative solution for dominant eigenvectors with applications in performance modelling and PageRank
复制标题
主要特征向量的异步迭代解决方案及其在性能建模和 PageRank 中的应用
DOI：
--
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Douglas Vincent de Jager
中科院分区：
文献类型：
--
作者：
Douglas Vincent de Jager
对于任何复杂的模型，性能分析计算都需要分布式计算工作，可以轻松地占用大型计算集群很多天。产生一个简单的稳态衡量标准涉及到巨大的主导特征向量计算，即使是具有10个以上变量的普通性能模型也是如此。像通过时间分析这样的计算要困难一个数量级，会产生数百次重复的线性系统计算。随着模型描述更大的并发性，模型的状态空间也随之增加，可能正在尝试的任何性能分析问题的规模也随之增加。谷歌使用PageRank算法来衡量网页的相对重要性。它通过制定和解决一个类似巨大的主导特征向量问题来做到这一点，网络上的每个页面都有一个变量。与性能问题一样，随着网页数量的增加，底层系统计算的大小也会增加。由于目前估计网页的数量超过一万亿，PageRank问题需要数千台计算机在许多不同的集群上同时运行。这两个问题共享相同的底层数学类型，以及在大型分布式集群上有效运行的相同要求。传统的迭代求解方法在大型分布式体系结构上的伸缩性很差。这是因为在每个迭代步骤中都要进行通信和同步的内在要求。虽然异步迭代方法从20世纪50年代就已经出现了，但它们还没有在没有某种形式的限制的情况下被应用于主导特征向量问题。当跨大型分布式体系结构实施时，这些方法已被证明在其他环境中非常成功。根据异步技术的当前技术状态，应用于主导特征向量问题需要关于如何以及何时发生更新的固定界限，并且因此实际上需要关于异步通信本身的界限。在这篇论文中，我们展示了如何在没有任何这样的限制的情况下将异步迭代方法应用于占优特征向量问题。我们通过展示如何将齐次、奇异线性系统映射到共享相同解的非齐次、非奇异线性系统来实现这一点。我们为性能分析问题提出了一个单一的异步迭代解决方案框架。我们还给出了三种特定的求解算法。我们通过分析和实证证明，与传统的同步求解方法相比，异步迭代方法具有显著的优势。我们使用本文介绍的理论工具来降低PageRank问题的复杂性，限制悬垂网页的影响。我们生成一个更小、更稀疏的问题，可以使用异步迭代方法来解决。
Performance analysis calculations, for models of any complexity, require a distributed computation effort that can easily occupy a large compute cluster for many days. Producing a simple steady-state measure involves an enormous dominant eigenvector calculation, with even modest performance models having upwards of 10 variables. Computations such as passage-time analysis are an order of magnitude more difficult, producing many hundreds of repeated linear system calculations. As models describe greater concurrency, so the state space of the model increases and with it the magnitude of any performance analysis problem that may be being attempted. The PageRank algorithm is used by Google to measure the relative importance of web pages. It does this by formulating and solving a similarly enormous dominant eigenvector problem, with one variable for every page on the web. As with performance problems, as the number of web pages grows, so the size of the underlying system calculation grows also. With the number of web pages currently estimated to exceed one trillion, the PageRank problem requires many thousands of computers running concurrently over many different clusters. Both problems share the same underlying mathematical type and also the same requirement to run effectively on large distributed clusters. Traditional iterative solution methods scale poorly over large distributed architectures. This is because of the inherent requirement to communicate and synchronise at every iteration step. While asynchronous iterative methods have been around since the 1950s, they have, as yet, not been applied to dominant eigenvector problems without some form of restriction. These methods have been shown to be very successful in other contexts when implemented across large distributed architectures. According to the current state of the art in asynchronous techniques, application to dominant eigenvector problems requires a fixed bound on how and when updates can happen, and thus effectively a bound on the asynchronous communication itself. In this thesis, we show how to apply asynchronous iterative methods to dominant eigenvector problems without any such restrictions. We do this by showing how to map homogeneous, singular linear systems to inhomogeneous, non-singular linear systems which share the same solution. We present a single asynchronous iterative solution framework for performance analysis problems. We also present three particular solution algorithms. We demonstrate analytically and empirically that asynchronous iterative methods offer significant advantages over traditional synchronous solution methods. We use the theoretical tools which we introduce in this thesis to reduce the complexity of the PageRank problem, limiting the ever-increasing impact of dangling web pages. We generate a smaller, sparser problem which may be solved using asynchronous iterative methods.