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

计算机科学中的许多领域，从数据挖掘到模拟再到计算生物学，都非常关注非常规应用程序，这些应用程序处理处理复杂数据结构的复杂算法。例如，为了分析大型数据集，点关联--一种数据挖掘算法--将数据组织成树状结构，然后对其进行处理以提取趋势和模式。随着这类算法变得越来越普遍，更重要的是，它们所应用的数据集变得越来越大，编写高性能的不规则应用程序变得至关重要。然而，不规则算法的复杂性使得编写高性能应用程序变得非常困难：算法的简单表达式不能很好地执行，高性能实现很难表达。一个有吸引力的解决方案是开发一套工具，它可以采用简单的算法表达式，并自动将程序转换为更高性能的版本。该项目旨在为非规则程序开发自动化的、健壮的和普遍适用的性能增强技术和转换。识别和执行非规则程序的性能增强转换的主要障碍是明显缺乏统一非规则应用程序的原则。然而，这项研究认为，确实有这样的原则可以指导转型的发展。通过利用不规则算法的高级结构特性，可以自动转换不规则程序以显著提高它们的性能。该项目致力于建立一个框架，以便(I)分析不规则程序，(Ii)识别有利可图的和合法的转换，(Iii)根据这些转换自动重组程序，然后(Iv)调整转换后的应用程序的性能，以最好地适应目标执行平台。

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.