Efficient Processor Allocation Policies for Massively Parallel Systems

我们设计并实现了一个新的并行程序设计环境Parsley，它提供基于应用程序结构的细粒度调度服务。在Parsley中，应用程序被划分为可以串行或并行运行的子任务。它提供了一个编程接口，允许用户定义子任务并轻松指定它们之间的优先约束。Parsley使用这些约束在运行时调度子任务。在本研究计画中，我们发展Parsley的排程策略与机制，并将其应用于分布记忆多处理器系统上的平行分子动力学模拟程式。调度策略自动改进以反映硬件环境和资源使用情况。基本策略是基于关键路径法的增量式调度算法。在该算法中，子任务的优先级是动态确定的，通过使用每个子任务的执行时间，由资源管理设施的Parsley。与FIFO调度策略相比，此策略将处理器利用率提高了35%到55%.此外，Parsley在异构环境（例如不同工作站和集群的网络）以及同构环境中都很有用。由于Parsley的动态处理器分配功能，用户不需要知道计算机和网络的单独性能。我们已经开发了几个资源管理政策，欧芹在异构环境中，并评估了分子动力学模拟的性能。

We designed and implemented a new parallel programming environment called Parsley, which provides fine-grained scheduling services based on the structures of application programs. In Parsley, application programs are divided into subtasks that can run serially or in parallel. It provides a programming interface that allows a user to define subtasks and to easily specify precedence constraints among them. Parsley uses these constraints to schedule subtasks at run time. In this research project, we developed the scheduling policy and mechanism for Parsley and applied them to parallel molecular dynamics simulation program on distributed memory multiprocessor systems. The scheduling policy is automatically improved to reflect the hardware environment and resource usage. The basic policy is an incremental scheduling algorithm based on the critical path method. In this algorithm, subtask priorities are dynamically determined by using the execution time of each subtask, as monitored by the resource management facilities of Parsley. This policy improves processor utilization by 35 to 55 % compared with the FIFO scheduling policy. In addition, Parsley is useful in the heterogeneous environment (e.g. a network of different workstations and clusters) as well as the homogeneous environment. Users need not be aware of the individual performance of the computers and networks, because of the dynamic processor allocation facilities of Parsley. We have developed several resource management policies for Parsley on heterogeneous environment and evaluated the performance for molecular dynamics simulation.