MSPA-MCS: Modeling, Analysis, and Learning Algorithms for Stochastic Scheduling in Clusters of Servers

研究者和他们的同事研究了大规模和可重构集群中的动态资源管理问题，并开发了一种新的随机框架，用于并行应用的建模、分析、资源分配和策略适应。该框架具有三个关键创新。首先，将顺序最优停止时间方法引入并行处理领域，用于设计最优调度策略。它依赖于一个工作负载演化模型，该模型在一个统一的结构中捕获动态负载变化和服务器容量变化。其次，该框架包含一种聚合方法，该方法利用聚类结构来降低计算复杂性，该方法基于对最近开发的双时间尺度马氏系统的处理。由于映射问题的马尔可夫决策过程要求控制动作是停止规则，因此所提出的技术构成了双时间尺度马尔可夫系统中停止规则的新范式，并对马尔可夫决策过程理论产生了更广泛的影响。第三，该框架包括一种新的学习方法，可以递归地更新调度策略，以适应时变的不确定环境，其中统计属性不可先验地获得。该方法将投影和截断算法集成到q -学习过程中，以提高其实现效率，状态边界和收敛速度。该项目验证了算法的渐近性质，为q -学习理论的研究提供了新的思路。除了算法在随机截断下的收敛性外，还使用关联扩散过程确定了收敛率。今天绝大多数的超级计算机都是通过聚集大量的处理节点来克服处理器速度的障碍。工程这样的系统提出了关键的挑战，包括协调处理节点的行为，以在实际应用中实现高可持续性能，以及在响应节点/链路故障时重新配置系统，以提供故障弹性服务。当前的实践通常依赖于启发式方法来解决问题，并且对大规模集群的潜力和局限性提供的见解很少。这项研究将当今集群计算原理的发现与数学科学的进步联系在一起。它不仅开发了下一代高端计算机技术的新知识，而且还在新的应用中推进了数学模型和理论。此外，它还激励不同领域的研究生和本科生参与计算机和数学科学的跨学科研究。

The investigators and their colleagues study the problem of dynamicresource management in large scale and reconfigurable clusters and developa novel stochastic framework for modeling, analysis, resourceallocation, and strategy adaptation of parallel applications.The framework features three key innovations. First, it introduces themethodology of sequential optimal stopping times into the field of parallelprocessing for designing optimal scheduling strategies. It relies on aworkload evolution model that captures both dynamic load changes andserver capacity variations in a unified structure. Second, the frameworkcontains an aggregation method that utilizes cluster structures to reducecomputational complexities, based on treatment of two-time-scale Markoviansystems developed recently. Since the Markov decision processes forremapping problems require control actions be stopping rules,the proposed techniques constitute a new paradigmof stopping rules in two-time-scale Markov systems and makea broader impact on the theory of Markov decisionprocesses. Third, the framework includes a novel learning methodology that canupdate scheduling strategies recursively to accommodate time-varyinguncertain environments in which statistical properties are not availablea priori. The methodology integrates projection and truncationalgorithms into the Q-learning procedures to enhance its implementationefficiency, state bounding, and speed of convergence. This projectestablishes asymptotic properties of the algorithms, which may shed new lightto the studies of Q-learning theory. In addition to convergence of thealgorithm under random truncations, rates of convergence are alsoascertained using an associate diffusion process. An overwhelming majority of today's supercomputers are constructedby aggregating a large number of processing nodes to overcome thebarrier of processor speed. Engineering such systemspresents key challenges, including coordination of the behaviors of theprocessing nodes to achieve high sustainable performance in real applicationsand reconfiguration of the systems in response to node/link failuresto provide fault-resilient services. Current practices often rely onheuristic approaches to the issues and offer little insights into thepotential and limitation of large scale clusters. This study intertwinestoday's discoveries of cluster computing principles with advances inmathematical sciences. Not only does it develop new knowledge about enablingtechnologies of next generation of high-end computers, but alsoit advances mathematical models and theories in new applications.Moreover, it motivates graduate and undergraduate students of diversified fields to participatein interdisciplinary research in both computer and mathematical sciences.