CAREER: Parallelization using Inspector/Executor Strategies (PIES)

Colorado State University, Fort Collins CO

Investigators

Abstract

Irregular computations occur in many important science and engineering application domains such as solving partial differential equations over irregular grids, molecular dynamics simulations, and computations over sparse matrices. To address this problem, inspector/executor strategies have been developed where the inspector dynamically analyzes memory reference patterns and generates communication schedules and/or reorganizes computation and data, and the executor executes the irregular computation in parallel. Although inspector/executor strategies have been incorporated into many applications and libraries, these strategies are still hindered by two main problems: (1) Currently, no general framework exists for automating the process of incorporating inspector/executor strategies into programs despite the complexity and difficulty that by-hand synthesis entails. (2) The performance of irregular applications significantly lags that of regular applications ? and this gap is widening for current and next-generation high-end multi-core systems. This research involves developing a tool suite called PIES (Parallelization using Inspector/Executor Strategies) for the automatic incorporation of inspector/executor strategies into irregular applications. The PIES tool suite includes the Mapping Intermediate Representation (MapIR) for specifying irregular code and inspector/executor strategies, a program analysis tool capable of determining the legal application of various inspector/executor strategies, a code generator capable of automatically generating inspectors and executors, and performance models to guide the selection of inspector/executor strategies and their parameters. This research includes an outreach program for local high school students based on applying the PIES tool suite to molecular dynamics simulations. Use of the PIES tool suite reduces software development time by automating the incorporation of inspector/executor strategies into existing code and enables the development of new inspector/executor strategies.