AAD: Software Tool for Asynchronous-Algorithm Development

Purdue University, West Lafayette IN

Investigators

Abstract

AAD: A Software Tool for Asynchronous-Algorithm Development Zhiyuan Li, Ananth Grama, Ahmed Sameh Department of Computer Sciences Purdue University Project Summary Intellectual Merit: Data communication and memory access latency will continue to be the most severe performance-limiting factor for high-end computing problems. This proposal takes the view that, for a wide range of applications, the computation efficiency can be substantially improved by a fundamental change to the data propagation model in parallel algorithms. Many important applications use iterative solvers to solve partial differential equations (PDEs). In such solvers, each data point is iteratively updated using the new values of its neighbors. Data values are therefore propagated across the problem domain over the time steps. Currently, the predominant way to propagate the data requires the processor to suspend its computation until all data computed at a predetermined time step have arrived from its neighbors. Such a rigid model not only incurs a heavy performance penalty due to processor waiting, but it also severely limits the compiler's ability to transform programs to achieve more efficient parallel execution and better data locality. The PIs propose a software tool which supports a new model called the asynchronous model. Under this model, each data point is updated based on whatever the most recent values available from its neighbors, instead of waiting for values computed at a predetermined step. The new model will hence overcome the difficulties mentioned above. The asynchronous model, nonetheless, may change the convergence rate of the algorithm. Hence, based on the tradeoff between the convergence rate and the parallel execution efficiency, the application programmer should tune the frequency at which the data propagation is re-synchronized in order to accelarate the convergence. The proposed tool will make it easy for the application programmer to perform such important tuning. Broader Impact: The success of this project will contribute substantially to the advance of high-end computing. Moreover, it will also make significant educational and outreach impact. The PIs plan to use the proposed software tool in Purdue's educational computational science and engineering (CSE) graduate program. Students and faculty in this program will use the tool in courses on parallel computing and performance evaluation, as well as in research projects that can benefit from fine-tuning performance on high-end parallel computing platforms. The software developed in this project can also be an effective tool in CSE education programs elsewhere. The PIs have a track record of transferring research ideas to industrial labs and such collaboration will continue to project positive influences on high-performance computer industries. This project will also further enhance PIs' ability to engage a broad community of undergraduate students in various disciplines, through Honor Seminars, special mentoring programs and undergraduate research opportunities.