AAD: Software Tool for Asynchronous-Algorithm Development

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

AAD: A Software Tool for Asynchronous-Algorithm DevelopmentZhiyuan Li, Ananth Grama, Ahmed SamehDepartment of Computer SciencesPurdue UniversityProject SummaryIntellectual Merit:Data communication and memory access latency will continue to be the most severeperformance-limiting factor for high-end computing problems. This proposal takes the view that, for a wide rangeof 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 updatedusing the new values of its neighbors.Data values are therefore propagated across the problem domain over the timesteps. Currently, the predominant wayto 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 onlyincurs a heavy performance penalty due to processor waiting, butit also severely limits the compiler's ability to transform programs to achievemore 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 valuescomputed at a predetermined step. The new model will hence overcomethe 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 theparallel execution efficiency,the application programmer should tune the frequency at whichthe data propagation is re-synchronized in order toaccelarate the convergence. The proposed tool will make it easyfor the application programmer to perform such important tuning.Broader Impact:The success of this project will contribute substantially tothe 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 educationalcomputational science and engineering (CSE) graduate program. Students and faculty in this program will use the tool in courses on parallel computingand 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 toolin CSE education programs elsewhere.The PIs have a track record of transferring research ideas toindustrial labs and such collaboration will continue to projectpositive 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.