Title page for ETD etd-07072008-202058

Type of Document Master's Thesis
Author Bhattacharya, Pamela
URN etd-07072008-202058
Title Model-Driven Search-Based Loop Fusion Optimization for Handwritten Code
Degree Master of Science in Systems Science (M.S.S.S.)
Department Computer Science
Advisory Committee
Advisor Name Title
Gerald Baumgartner Committee Chair
Jagannathan Ramanujam Committee Member
Rahul Shah Committee Member
  • optimization
  • loop fusion
  • compilers
Date of Defense 2008-06-30
Availability unrestricted
The Tensor Contraction Engine (TCE) is a compiler that translates

high-level, mathematical tensor contraction expressions into efficient,

parallel Fortran code. A pair of

optimizations in the TCE, the fusion and tiling

optimizations, have proven successful for minimizing disk-to-memory

traffic for dense tensor computations. While other optimizations

are specific to tensor contraction expressions, these two

model-driven search-based

optimization algorithms could also be useful for optimizing handwritten

dense array computations to minimize disk to memory traffic.

In this thesis, we show how to apply the loop fusion algorithm to

handwritten code in a procedural language.

While in the TCE the loop fusion algorithm operated on high-level

expression trees, in a standard compiler it needs to operate on

abstract syntax trees. For simplicity, we use the fusion algorithm

only for memory minimization instead of for minimizing disk-to-memory

traffic. Also, we limit ourselves to handwritten, dense array

computations in which loop bounds expressions are constant,

subscript expressions are simple loop variables, and there are no

common subexpressions.

After type-checking, we canonicalize the abstract syntax tree to move

side effects and loop-invariant code out of larger expressions. Using

dataflow analysis, we then compute reaching definitions and add

use-def chains to the abstract syntax tree. After undoing any partial

loop fusion, a generalized loop fusion algorithm traverses the

abstract syntax tree together with the use-def chains. Finally, the

abstract syntax tree is rewritten to reflect the loop structure found

by the loop fusion algorithm.

We outline how the constraints on loop bounds expressions and array

index expressions could be removed in the future using an algebraic

cost model and an analysis of the iteration space using a polyhedral model.

  Filename       Size       Approximate Download Time (Hours:Minutes:Seconds) 
 28.8 Modem   56K Modem   ISDN (64 Kb)   ISDN (128 Kb)   Higher-speed Access 
  Bhattacharya_Thesis.pdf 534.45 Kb 00:02:28 00:01:16 00:01:06 00:00:33 00:00:02

Browse All Available ETDs by ( Author | Department )

If you have questions or technical problems, please Contact LSU-ETD Support.