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 Keywords
- loop fusion
Date of Defense 2008-06-30 Availability unrestricted AbstractThe 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
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
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
If you have questions or technical problems, please Contact LSU-ETD Support.