Skip to Main Content
 

Global Search Box

 
 
 
 

Files

ETD Abstract Container

Abstract Header

Tools for Performance Optimizations and Tuning of Affine Loop Nests

Hartono, Albert

Abstract Details

2009, Doctor of Philosophy, Ohio State University, Computer Science and Engineering.

Multicore processors have become mainstream and the number of cores in a chip will continue to increase every year. Programming these architectures to effectively exploit their very high computation power is a non trivial task. First, an application program needs to be explicitly restructured using a set of code transformation techniques to optimize for specific architectural features, especially for parallelism and data locality. Then a significant amount of time is spent on tuning the optimized code to find the best optimization parameter values. However, high performance often means lower productivity as the optimized codes become difficult to understand, maintain and modify. In this dissertation, we present techniques to address these issues by automatic generation of efficient parallel programs, and by the use of empirical search for tuning. The research from this dissertation has been implemented and made publicly available as two useful software tools: one for parameterized tiled loop generation, and one for empirical performance tuning using annotations.

Tiling is a critical loop transformation that optimizes both for data locality enhancement as well as coarse-grained parallel execution on many-core systems. Parameterized tiled code refers to tiled loops where the tile sizes are not fixed compile-time constants. It is important for auto-tuning systems since they often execute a large number of runs with dynamically varied tile sizes. Multi-level tiling is essential for maximizing data locality in systems with deep memory hierarchies. Previous approaches to tiled code generation have addressed parametric tiling but have been restricted to perfect loop nests and sequential execution. Prior parallel tiling solutions can handle imperfect loop nests but are only applicable to compile-time constant tile sizes. We develop systematic solutions to parameterized multi-level tiling of arbitrary imperfectly nested affine loops for both sequential and parallel execution. We develop approaches to mapping independent tiles to different processing units using compile-time and run-time schedules. The proposed parametric tiling approaches have been implemented in the PrimeTile code generation tool that can automatically generate parallel tiled code from affine C program sections.

To enable fast tuning of application programs, we develop an extensible annotation-based empirical tuning system called Orio. It is aimed not only at improving the productivity of the application programmer but also the performance and portability of the generated code. Orio allows programmers to insert annotations in the form of structured comments in the source code to trigger a number of architecture-independent and architecture-specific code optimizations. Given an annotated code as input, Orio generates many optimized code versions for the computation and empirically evaluates the alternatives, to select the best performing version for production use. The tuning system utilizes non-derivative heuristic search algorithms to effectively narrow the space of all possible optimized code versions. The tool's design for extensibility simplifies integration with other code transformation tools to generate highly tuned code.

P. Sadayappan (Advisor)
Atanas Rountev (Committee Member)
Dhabaleswar K. Panda (Committee Member)
J. Ramanujam (Committee Member)
146 p.

Recommended Citations

Citations

  • Hartono, A. (2009). Tools for Performance Optimizations and Tuning of Affine Loop Nests [Doctoral dissertation, Ohio State University]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=osu1259685041

    APA Style (7th edition)

  • Hartono, Albert. Tools for Performance Optimizations and Tuning of Affine Loop Nests. 2009. Ohio State University, Doctoral dissertation. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=osu1259685041.

    MLA Style (8th edition)

  • Hartono, Albert. "Tools for Performance Optimizations and Tuning of Affine Loop Nests." Doctoral dissertation, Ohio State University, 2009. http://rave.ohiolink.edu/etdc/view?acc_num=osu1259685041

    Chicago Manual of Style (17th edition)