ALGORITHMS: Adaptive Stochastic Scheduling for Bulk Synchronous Computations and Its Application in Molecular Dynamics Simulations

本研究探讨并行效率的一类重要的批量同步应用程序，例如计算分子动力学，在集群的工作站。批量同步应用程序通常具有随时间推移不确定的计算需求的特征。在多道程序设计环境中，分配给应用程序的节点容量也可能随着其他作业的加入和离开而改变。相对于动态的计算和集群资源的不确定性，本研究旨在开发随机调度策略，支持高性能计算的集群。通过将调度因素描述为随机变量，建立了自适应调度算法的建模和分析框架。它通过考虑工作负载演变和容量变化的动态系统来开发有效的应用程序级重映射策略。在分子动力学计算机模拟的应用程序中的调度策略进行了评估。该研究将融合正式建模/分析，实验和随机调度算法的评估。这项研究的成功将有助于提高高性能集群计算的工业接受度，并将计算分子动力学及时推进到大型多原子系统的模拟中。

This research investigates the parallel efficiency of an important class of bulk synchronous applications, as exemplified by computational molecular dynamics, in clusters of workstations. Bulk synchronous applications are often characteristic of non-deterministic computational requirements over time. In a multiprogramming environment, the nodal capacities allocated to an application may also change as other jobs join and leave. With respect to the dynamics of the computation and uncertainties of the cluster resources, this research aims at developing stochastic scheduling strategies in support of high performance computing in the clusters. It constructs a framework for modeling and analyses of adaptive scheduling algorithms by characterizing scheduling factors as random variables. It develops efficient application-level remapping policies by taking into account the dynamic systems of workload evolution and capacity change. The scheduling strategies are evaluated in the application of molecular dynamics computer simulations. The research will blend formal modeling/analyses, experimentation, and evaluation of stochastic scheduling algorithms. Success of this research will help increase the industrial acceptance of high performance cluster computing and advance computational molecular dynamics to simulations of large, multi-atom systems in a timely manner.