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

科学计算问题表现出很大的数据级并行性。参与方运行时系统试图为科学计算获得高效的并行实现，特别是那些数据依赖仅在运行时才明显的实现。这可以排除基于编译器的某些类型的并行性的检测。该自动化系统的结构如下：采用高级语言接口，其中使用注释来选择适当的粒度级别。生成程序的有向无环图表示，在其上可以采用各种聚集技术以生成有效的调度。然后将这些时间表映射到目标计算机上。通过1)使用常规问题的稀疏表示和经过充分研究的多处理器映射来评估工作聚类和调度启发式，2)使用不同和现实的稀疏矩阵问题的工作量来比较调度和聚类方法，3)合成工作负载的生成、分析和建模。在PARTY系统环境下开发的聚集、映射和并行调度执行方法和软件模块用于在Encore Multimax、Intel IPSC和Think Machine的CM-11上调度和执行预条件Kryolov空间稀疏迭代算法和用于非均匀网格的显式PDE求解方法的系统。最后，基于Fortran的PARTY系统接口将使用带注释的Fortran来促进程序员对PARTY的透明访问。

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.