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

点击翻译按钮获取中文摘要

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.