AAD: Software Tool for Asynchronous-Algorithm Development

AAD：异步算法开发软件工具

• 批准号: 0444285
• 负责人: Zhiyuan Li
• 金额: $ 65万
• 依托单位: Purdue University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2005
• 资助国家: 美国
• 起止时间: 2005-01-01 至 2009-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0444285&HistoricalAwards=false
• 关键词: AAD; Software; Tool; Asynchronous; Algorithm

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.

AAD：异步算法开发的软件工具李志远，Ananth Grama， Ahmed sameh普渡大学计算机系项目总结智力优势：数据通信和内存访问延迟将继续成为高端计算问题中最严重的性能限制因素。本文认为，对于广泛的应用，通过从根本上改变并行算法中的数据传播模型，可以大大提高计算效率。许多重要的应用使用迭代求解器来求解偏微分方程（PDEs）。在这样的求解器中，每个数据点都使用其邻居的新值进行迭代更新。因此，数据值在时间步长上跨问题域传播。目前，传播数据的主要方法要求处理器暂停其计算，直到在预定时间步长计算的所有数据都从其邻居到达为止。这种严格的模型不仅会由于处理器等待而导致严重的性能损失，而且还严重限制了编译器转换程序以实现更有效的并行执行和更好的数据局地性的能力。pi提出了一个软件工具，该工具支持一种称为异步模型的新模型。在这个模型下，每个数据点都是基于从它的邻居那里获得的最新值来更新的，而不是等待在预定步骤中计算出的值。因此，新模式将克服上述困难。然而，异步模型可能会改变算法的收敛速度。因此，基于收敛速度和并行执行效率之间的权衡，应用程序程序员应该调整数据传播重新同步的频率，以加速收敛。所建议的工具将使应用程序程序员能够轻松地执行如此重要的调优。更广泛的影响：这个项目的成功将大大促进高端计算的发展。此外，它还将产生重大的教育和推广影响。pi计划在普渡大学的教育计算科学与工程（CSE）研究生课程中使用拟议的软件工具。该项目的学生和教师将在并行计算和性能评估课程以及研究项目中使用该工具，这些项目可以从高端并行计算平台的性能微调中受益。本项目开发的软件也可以成为其他地方CSE教育项目的有效工具。ppi在将研究理念转移到工业实验室方面有着良好的记录，这种合作将继续对高性能计算机行业产生积极影响。该项目还将通过荣誉研讨会、特别指导计划和本科生研究机会，进一步提高私人学院与各学科本科生广泛接触的能力。