Automated Methods for Runtime Performance Optimization for Sparse and Irregular Numeric Applications

科学计算问题表现出大量的数据级并行性。PARTY运行时系统试图为科学计算获得有效的并行实现，特别是那些仅在运行时显示数据依赖关系的计算。这可以排除基于编译器对某些类型的并行性的检测。自动化系统的结构如下：采用高级语言接口，其中使用注释来选择适当的粒度级别。生成程序的有向无环图表示，在其上可以采用各种聚合技术以生成有效的调度。然后将这些计划映射到目标计算机上。对工作聚类和调度启发式算法进行了评价：1)使用正则问题的稀疏表示，充分研究了多处理器映射；2)比较调度和聚类方法，使用稀疏矩阵问题的各种实际工作负载；3)合成工作负载的生成、分析和建模。在PARTY系统背景下开发的聚合、映射和并行调度执行方法和软件模块用于实现一个系统，该系统在Encore Multimax、Intel iPSC和Thinking Machine的CM-II上调度和执行预处理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-II. Finally, a Fortran based interface to the PARTY system will use annotated Fortran to facilitate transparent programmer access to PARTY.