Analysis of Cycle Stealing and Other Multi-Server Problems via New Dimensionality Reduction Approach

随机过程是分析计算机系统性能的一个非常强大的工具。然而，仍然存在一些非常基本的计算机系统问题，这些问题在很大程度上仍然难以解决。一个例子是简单的周期窃取问题，其中一台服务器可以在交换开销下窃取另一台服务器的空闲周期。周期窃取遍及从网络服务器场到工作站网络、磁盘阵列到数据库服务器集群的各种应用程序，然而，诸如量化周期窃取的好处或了解在什么条件下周期窃取是有利可图的非常简单的问题尚不清楚。另一个例子是在服务器群中寻找和分析任务分配的最佳策略这一长期悬而未决的问题。有趣的是，这些问题和其他开放的基本计算机系统问题都是困难的，原因是相同的：它们都有一个在二维或更多维(2D)上无限增长的马尔可夫链表示。具有重复结构的一维(1D)无限马尔可夫链可以通过计算方法来求解，而这些二维无限马氏链却不能.本项目提出了一种新的方法来解决上述问题，从而得到二维无限马尔可夫链.其思想是在不去除相关问题信息的情况下，将二维无限链转换为可分析的一维无限链。这是通过使用马尔可夫链转变来表示各种类型的忙期的持续时间来实现的。该项目将需要对这项技术的普遍适用性进行数学探索，将该技术应用于具体问题，并在实际系统中实施分析解决方案。拟议活动产生的广泛影响包括：服务器群中的调度研讨会；工作产生的所有源代码和文档的在线可用性；一套高度可访问的排队理论应用的课堂讲稿，每年都会发展，以反映作者当前的研究目标；与匹兹堡超级计算机中心的合作，以实施该提案中的想法；以及本科生在调度方面的研究机会。该项目涉及1名教员(仅1个暑期月)和0.5名研究生，历时3年。

Stochastic processes are a very powerful tool for analyzing the performance of computer systems. However there are still some very fundamental computer systems problems which remain largely intractable. One example is the simple cycle stealing problem, where one server can steal another server's idle cycles under a switching cost overhead. Cycle stealing pervades applications ranging from Webserver farms, to networks of workstations, to disk arrays, to databaseserver clusters, and yet very simple questions like quantifying the benefit of cycle stealing, or understanding under what conditions cycle stealing is profitable are not yet understood. Another example is the long standing open problem of finding and analyzing the optimal policy for task assignment in a server farm. Interestingly, these problems and other open fundamental computer systems problems are difficult for the same reason: they all have a Markov chain representation which grows infinitely in two or more dimensions (2D). While a one-dimensional (1D) infinite Markov chain with repeating structure can be solved via computational approaches, these 2D infinite chains can not.This project proposes a new approach for attacking problems such as those above, resulting in a 2D infinite Markov chain. The idea is to transform the 2D infinite chain into a 1D infinite chain which can be analyzed, without removing the relevant problem information. This is achieved by using Markov chain transitions to denote the durations of various types of busy periods. The project will entail a mathematical exploration of the general applicability of this technique, the application of the technique to specific problems, and the implementation of the analytical solutions within real systems.Broader impacts resulting from the proposed activity include: a workshop on scheduling in server farms; online availability of all source code generated from the work along with documentation; a highly-accessible set of lecture notes on queueing theory applications which evolves yearly to reflect the current research aims of the author; collaborations with the Pittsburgh Supercomputer Center to implement ideas in this proposal; and undergraduate research opportunities in scheduling. The project involves 1 faculty member (1summer month only) and 0.5 graduate students over the course of 3years.