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.