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.