Efficient Processor Allocation Policies for Massively Parallel Systems

大规模并行系统的高效处理器分配策略

基本信息

批准号：
10680336
负责人：
SHIMIZU Kentaro
金额：
$ 2.05万
依托单位：
THE UNIVERSITY OF TOKYO
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
1998
资助国家：
日本
起止时间：
1998 至 2000
项目状态：
已结题

项目摘要

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.

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