Thesis Available on ILP

My thesis has at long last been finished and is available to
anyone who is interested. The title is:


Exploiting Instruction Level Parallelism in the Presence
of Conditional Branches


This thesis investigates the compilation of control-intensive
applications for wide-issue superscalar and VLIW processors.
Generally, a high frequency of branches restricts the exploitable
ILP in an application to a small amount. The thesis focuses
on two techniques, speculative and predicated execution, to overcome
the branch bottlenecks in these applications. The abstract appended
below gives a more complete overview.


The thesis is available either from my web page:
http://www.crhc.uiuc.edu/Impact/people/graduated/Scott_A_Mahlke.html


or via anonymous ftp to:
ftp.crhc.uiuc.edu -> pub/IMPACT/report/phd-thesis-scott-mahlke.ps.Z


If you have any questions/comments/etc. regarding the thesis,
please let me know.


-Scott


---------------------------------------------------------------------


Title: Exploiting Instruction Level Parallelism in the Presence
              of Conditional Branches


Abstract:


        Wide issue superscalar and VLIW processors utilize instruction-level
parallelism (ILP) to achieve high performance. However, if insufficient
ILP is found, the performance potential of these processors suffers
dramatically. Branch instructions, which are one of the major
limitations to exploiting ILP, enforce strict ordering conditions in
programs to ensure correct execution. Therefore, it is difficult to
achieve the desired overlap of instruction execution with branches in
the instruction stream. To effectively exploit ILP in the presence of
branches requires efficient handling of branches and the dependences
they impose.


        This dissertation investigates two techniques for exposing and
enhancing ILP in the presence of branches, speculative execution and
predicated execution. Speculative execution enables an ILP compiler
to remove dependences between instructions and prior branches. In
this manner, the execution of instructions and predicted future
instructions may be overlapped. Compiler-controlled speculative
execution is employed using an efficient structure called the superblock.
The formation and optimization of superblocks increase ILP along
important execution paths by systematically removing constraints due to
unimportant paths. In conjunction with superblock optimizations,
speculative execution is utilized to remove control dependences in the
superblock to aggressively reorder instructions across branches to
achieve a high degree of execution overlap.


        For many applications, speculative execution alone is not sufficient
to achieve high performance. The fundamental limitation is that
speculation only removes dependences between branches and other
instructions. The branches themselves remain in the code, which causes
difficult problems. This motivates the second technique investigated in
this dissertation, predicated execution, which is an architectural
capability that enables the conditional execution of instructions based
on the value of a Boolean source operand. Predicated execution allows a
compiler to eliminate branch instructions using this conditional execution
support. Additionally, predicated execution provides an efficient
interface for the compiler to overlap the execution of multiple paths of
control. Predicated execution is exploited in the compiler via a
generalized form of a superblock, called the hyperblock. Hyperblocks
provide the framework for the compiler to selectively eliminate branches
using predicated execution as well as apply speculative execution to
exploit ILP.


--
Scott A. Mahlke HP Laboratories
mahlke@hpl.hp.com Compiler and Architecture Research Group
--

Return to the comp.compilers page.
Search the comp.compilers archives again.