CAREER:Toward a locality-enhancing transformation framework for irregular programs

职业生涯：为非正规项目建立一个增强地方性的转型框架

• 批准号: 1150013
• 负责人: Milind Kulkarni
• 金额: $ 41.88万
• 依托单位: Purdue University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2012
• 资助国家: 美国
• 起止时间: 2012-02-01 至 2018-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1150013&HistoricalAwards=false
• 关键词: CAREER; Toward; locality; enhancing; transformation

Many domains in computer science, from data-mining to simulation to computational biology, focus heavily on irregular applications, which deal with complex algorithms that manipulate complex data structures. For example, to analyze large data sets, point correlation - a data mining algorithm - organizes data in a tree-like structure that is then manipulated to extract trends and patterns. As such algorithms become more pervasive, and, more importantly, the data sets they are applied to become much larger, writing high performance irregular applications has become critically important. However, the complexity of irregular algorithms makes writing high-performance applications very difficult: simple expressions of the algorithms do not perform well, and high-performance implementations are difficult to express. An attractive solution is to develop a set of tools that could take a simple expression of an algorithm and automatically transform the program into a higher performing version. This project aims to develop automated, robust and generally-applicable performance-enhancing techniques and transformations for irregular programs.The chief obstacle to identifying and performing performance-enhancing transformations on irregular programs is the apparent lack of principles that unify irregular applications. However, this research argues that there are, indeed, such principles that can guide the development of transformations. By leveraging high-level structural properties of irregular algorithms, it is possible to automatically transform irregular programs to significantly improve their performance. This project pursues a set of interlocking efforts to build a framework to (i) analyze irregular programs, (ii) identify profitable and legal transformations, (iii) automatically restructure programs according to those transformations, and then (iv) tune the performance of the transformed applications to best fit the target execution platform.

从数据挖掘到模拟再到计算生物学的计算机科学领域的许多领域，都集中在不规则的应用上，这些应用程序涉及操纵复杂数据结构的复杂算法。例如，要分析大型数据集，点相关性 - 数据挖掘算法 - 在类似树状结构中组织数据，然后被操纵以提取趋势和模式。随着这种算法变得更加普遍，更重要的是，它们应用于更大的数据集，编写高性能不规则应用程序已经变得至关重要。但是，不规则算法的复杂性使编写高性能应用程序非常困难：算法的简单表达不佳，并且很难表达高性能实现。一个有吸引力的解决方案是开发一组可以简单地表达算法的工具，并自动将程序转换为更高的性能版本。该项目旨在开发自动化，健壮且普遍适用的性能增强技术和不规则计划的转型。识别和执行不规则计划上的绩效增强转型的主要障碍是明显缺乏统一不规则应用的原则。但是，这项研究认为，确实有这样的原则可以指导转型的发展。通过利用不规则算法的高级结构特性，可以自动改变不规则的程序以显着提高其性能。该项目采取了一系列互锁的努力，以建立一个框架以（i）分析不规则计划，（ii）确定有利可图的法律转型，（iii）根据这些转换自动重组计划，然后（iv）调整转换应用程序的性能以最适合目标执行平台。