Static and Dynamic Load Balancing of Parallel Discrete-Event Simulations on Distributed Memory Architectures

分布式内存架构上并行离散事件仿真的静态和动态负载平衡

• 批准号: 8819373
• 负责人: David Nicol
• 金额: $ 10.38万
• 依托单位: College of William and Mary
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1989
• 资助国家: 美国
• 起止时间: 1989-08-01 至 1995-11-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=8819373&HistoricalAwards=false
• 关键词: Static; Dynamic; Load; Balancing; Parallel

Scientific computational problems exhibit substantial data level parallelism. The PARTY run-time system is an attempt to obtain efficient parallel implementations for scientific computations, particularly those where the data dependencies are manifest only at run-time. This can preclude compiler based detection of certain types of parallelism. The automated system is structured as follows: A high level language interface is employed in which annotations are used to select an appropriate level of granularity. A directed acyclic graph representation of the program is generated on which various aggregation techniques may be employed in order to generate efficient schedules. These schedules are then mapped onto the target machine. Work clustering and scheduling heuristics are evaluated by 1) using sparse representation of regular problems with well-studied multiprocessor mappings, 2) comparing scheduling and clustering methods using a varied and realistic workload of sparse matrix problems, 3) generation, analysis and modeling of synthetic workloads. The aggregation, mapping and parallel schedule execution methods and software modules developed in the context of the PARTY system are used to implement a system that schedules and executes preconditioned Kryolov space sparse iterative algorithms and explicit PDE solution methods for non uniform meshes on the Encore Multimax, the Intel iPSC and Thinking Machine's CM-11. Finally, a Fortran based interface to the PARTY system will use annotated Fortran to facilitate transparent programmer access to PARTY.

科学计算问题呈现出大量的数据水平 平行性 PARTY运行时系统是一种尝试， 用于科学计算的高效并行实现， 特别是那些数据依赖性仅是明显的 在运行时。 这可能会妨碍基于编译器的 某些类型的并行性。 自动化系统的结构 如下：采用高级语言接口，其中 注释用于选择适当的 粒度 的有向非循环图表示， 生成程序，在该程序上，各种聚合技术可以 以生成高效的时间表。 这些 然后将调度映射到目标机器上。 工作聚类和调度算法通过以下方式评估：1） 使用稀疏表示的规则问题， 多处理器映射，2）比较调度和集群 方法使用了不同的和现实的工作量稀疏矩阵 问题，3）生成，分析和建模的综合 工作量。 聚合、映射和并行调度 执行方法和软件模块开发的上下文 PARTY系统的一部分用于实现一个系统， 并执行预条件Kryolov空间稀疏迭代 非均匀问题的算法和显式偏微分方程求解方法 Encore Multimax、Intel iPSC和Thinking上的网格 机器是CM-11 最后，给出了一个基于Fortran的接口， PARTY系统将使用带注释的Fortran语言，方便透明 程序员访问PARTY。