Computer Engineering Talk

[Subramanya Sastry <sastry@xxxxxxxxxxx>]

---------- Forwarded message ----------
Date: Mon, 12 Apr 1999 08:36:28 -0500 (CDT)
From: Kewal Saluja <saluja@xxxxxxxxxxxxxxxxxxx>
To: Kewal Saluja <saluja@xxxxxxxxxxxxxxxxxxx>
Subject: Special Seminar -- Computer Engineering



April 12, 1999

There will be a special computer engineering seminar on Tuesday (April 13) 
(Also, we have another seminar on Wednesday April 14)

You can also find this information at
       http://www.cae.wisc.edu/~saluja/seminars/schedule.html


        Speaker:    DAVID AUGUST
        Time:       2:30 pm   
        Date:       April 13, 1999   (Note: TUESDAY)
        Location:   Room 3609, Engineering Hall  -- Note Location

        Subject:    Systematic Program Decision Logic Optimization
			       Using Predication



*************************************************************************

       Systematic Program Decision Logic Optimization Using Predication


				 by

			    David I. August
	 Department of Electrical and Computer Engineering
 	       University of Illinois, Urbana-Champaign




In many ways, modern microprocessor architectures are becoming
increasingly dependent on the sophistication of compilers.  As
processor issue widths increase, the compiler's ability to utilize
available resources by exposing sufficient Instruction-Level
Parallelism (ILP) becomes critical in realizing a system's performance
potential.  One major impediment to a compiler's ability to expose ILP
has been inefficient programmatic control flow.  Historically, the
compiler has translated the programmer's original control structure
directly into assembly code with conditional branch instructions.
Inefficiencies in this structure limit ILP, and much research has been
dedicated to reducing branch control height and to reducing the cost
of branch computation.  Traditional branch handling techniques,
however, are limited by the fact that they cannot significantly alter
the program's original control structure.

The use of predication as a compiler intermediate representation has
enabled compilers to manipulate program control flow in a form more
closely related to the underlying program logic, creating
opportunities for more general restructuring.  This talk presents a
technique which leverages the properties of the predicated
representation to overcome limits on ILP previously imposed by rigid
program control structure.  The method developed abstracts the program
control flow into a logical form referred to as a program decision
logic network.  This network, which can be viewed as a set of Boolean
equations, is minimized using adapted versions of logic synthesis
techniques.  Further network optimization is performed using knowledge
of implications between the condition evaluations, which is discerned
using a value range analysis mechanism.  After minimization, the more
efficient version of the program's original control flow is
re-expressed as predicated assembly code.  This general restructuring
of program control reduces height and complexity in ways that far
exceed the capabilities of previous techniques.



Biography


David August is a Ph.D. candidate in the ECE Department and a senior
member of the IMPACT research group at the University of Illinois at
Urbana-Champaign.  In 1993, he received his bachelor's degree summa
cum laude in electrical engineering from Rensselaer Polytechnic
Institute.  In 1996, he earned his master's degree from the ECE
Department at the University of Illinois with a thesis on ILP
optimizations for predicated code.  His doctoral research focuses on
advanced predicate optimization and new compiler frameworks leveraging
predication.  While a graduate student, he spent three summers at
Intel and at Hewlett-Packard working on EPIC architecture compilation
issues.  He has given invited presentations at major corporations
including Intel, SGI, Digital/Compaq, and Microsoft.  David has been
awarded the Intel Foundation Fellowship, the Office of Naval Research
Graduate Fellowship, the University of Illinois Koehler Fellowship,
the Rensselaer Ricketts Prize, and the Rensselaer Medal Scholarship.
He is a member of IEEE, ACM, Eta Kappa Nu, Tau Beta Pi, and Phi Kappa
Phi.

________________________________
This seminar series is supported by the funds from the AT&T foundation