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

Wayne State University, Detroit MI

Investigators

Abstract

The investigators and their colleagues study the problem of dynamic resource management in large scale and reconfigurable clusters and develop a novel stochastic framework for modeling, analysis, resource allocation, and strategy adaptation of parallel applications. The framework features three key innovations. First, it introduces the methodology of sequential optimal stopping times into the field of parallel processing for designing optimal scheduling strategies. It relies on a workload evolution model that captures both dynamic load changes and server capacity variations in a unified structure. Second, the framework contains an aggregation method that utilizes cluster structures to reduce computational complexities, based on treatment of two-time-scale Markovian systems developed recently. Since the Markov decision processes for remapping problems require control actions be stopping rules, the proposed techniques constitute a new paradigm of stopping rules in two-time-scale Markov systems and make a broader impact on the theory of Markov decision processes. Third, the framework includes a novel learning methodology that can update scheduling strategies recursively to accommodate time-varying uncertain environments in which statistical properties are not available a priori. The methodology integrates projection and truncation algorithms into the Q-learning procedures to enhance its implementation efficiency, state bounding, and speed of convergence. This project establishes asymptotic properties of the algorithms, which may shed new light to the studies of Q-learning theory. In addition to convergence of the algorithm under random truncations, rates of convergence are also ascertained using an associate diffusion process. An overwhelming majority of today's supercomputers are constructed by aggregating a large number of processing nodes to overcome the barrier of processor speed. Engineering such systems presents key challenges, including coordination of the behaviors of the processing nodes to achieve high sustainable performance in real applications and reconfiguration of the systems in response to node/link failures to provide fault-resilient services. Current practices often rely on heuristic approaches to the issues and offer little insights into the potential and limitation of large scale clusters. This study intertwines today's discoveries of cluster computing principles with advances in mathematical sciences. Not only does it develop new knowledge about enabling technologies of next generation of high-end computers, but also it advances mathematical models and theories in new applications. Moreover, it motivates graduate and undergraduate students of diversified fields to participate in interdisciplinary research in both computer and mathematical sciences.