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

MSPA-MCS：服务器集群中随机调度的建模、分析和学习算法

• 批准号: 0624849
• 负责人: Chengzhong Xu
• 金额: $ 49.42万
• 依托单位: Wayne State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2006
• 资助国家: 美国
• 起止时间: 2006-09-01 至 2010-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0624849&HistoricalAwards=false
• 关键词: MSPA; MCS; Modeling; Analysis; Learning

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.

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