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

Keywords

optimization
loop fusion
compilers

Date of Defense

2008-06-30

Availability

unrestricted

Abstract

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.

Files

Filename		Size	Approximate Download Time (Hours:Minutes:Seconds)
Filename		Size	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