Of possible interest...

[Scott_Fahlman@SEF-PMAX.SLISP.CS.CMU.EDU]

Just in case you missed this announcement, it sounds like you ought to go
to this and/or read the thesis.

-- Scott


------- Forwarded Message

From: burks+@F.GP.CS.CMU.EDU (Sharon Burks)
Organization: School of Computer Science, Carnegie Mellon
Date: Mon, 30 Mar 92 11:59:10 -0500
Subject: Angelika Zobel - Thesis Oral

                                  THESIS ORAL

                     Program Structure as a Basis for the
               Parallelization of Global Compiler Optimizations

                                ANGELIKA ZOBEL

                             Friday, 3 April 1992
                                   10:00 PM
                                Wean Hall 5409


                                   Abstract

   Optimizing  compilers  can  produce  very efficient code but incur a high
   compilation cost.  Because interactions between  arbitrary  points  in  a
   program  are  possible,  global  compiler  optimizations  are  inherently
   expensive and in general there is no  easy  way  to  partition  the  data
   processed   during   global   compiler   optimizations  into  independent
   components.

   This thesis explores how program structure can be used to provide a basis
   for  the  parallelization  for  global compiler optimizations.  I use two
   different  concepts  to  obtain  data  parallelism  in  global   compiler
   optimizations.    In  my first example, interval analysis, parallelism is
   based on explicit program  structure,  e.g.    loops  in  a  program  are
   processed  in  parallel.   This concept can not be applied to NP complete
   optimizations because data interactions are  more  complex.    My  second
   example  is  global  register  allocation via optimal coloring of a graph
   denoting register conflicts, an NP complete problem.  In previous methods
   for  register coloring program structure is used heuristically if at all.
   I present my model  for  global  register  allocation  in  which  program
   structure  is  used to analyze a register conflict graph.  The purpose of
   this analysis is to detect clique separators that  partition  a  conflict
   graph  into  independent components that can be colored independently and
   combined to an overall coloring by renaming.  Properties of  live  ranges
   in  loops  and conditionals are linked to characteristics of the conflict
   graph.  If certain restrictions are met by the live ranges that occur  in
   conditionals and loops, the register conflict graph can be transformed to
   an equivalent interval graph.   Interval  register  conflict  graphs  are
   desirable  because  they  can be colored optimally in polynomial time and
   because all clique  separators  of  an  interval  graph  can  be  located
   systematically.    The experimental evaluation of my method shows that in
   many cases the entire conflict graph or large  portions  thereof  can  be
   mapped  to  equivalent  interval  graphs.  Consequently, in such conflict
   graphs almost all clique separators can be detected which makes  it  easy
   to  partition  the conflict graph into independent components that can be
   processed independently. I will discuss how the knowledge about  interval
   portions  of  register  conflict graph can be used both as a platform for
   the  parallelization  of  global  register  allocation  and  to   improve
   sequential register coloring algorithms.

                               Thesis Committee:
                              Thomas Gross, Chair
                               Peter Steenkiste
                                Mario Barbacci
                     David Wortman, University of Toronto

        A copy of the thesis summary has been posted in the CS Lounge.

------- End of Forwarded Message