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）调整转换后的应用程序的性能，以最适合目标执行平台。