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

稀疏和不规则数值应用程序运行时性能优化的自动化方法

• 批准号: 8819374
• 负责人: Joel Saltz
• 金额: $ 14.2万
• 依托单位: Yale University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1989
• 资助国家: 美国
• 起止时间: 1989-08-01 至 1993-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=8819374&HistoricalAwards=false
• 关键词: Automated; Methods; Runtime; Performance; Optimization

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.

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