Rus, Silvius Vasile (2006-12). Hybrid analysis of memory references and its application to automatic parallelization. Doctoral Dissertation. Thesis uri icon

abstract

  • Executing sequential code in parallel on a multithreaded machine has been an elusive goal of the academic and industrial research communities for many years. It has recently become more important due to the widespread introduction of multicores in PCs. Automatic multithreading has not been achieved because classic, static compiler analysis was not powerful enough and program behavior was found to be, in many cases, input dependent. Speculative thread level parallelization was a welcome avenue for advancing parallelization coverage but its performance was not always optimal due to the sometimes unnecessary overhead of checking every dynamic memory reference. In this dissertation we introduce a novel analysis technique, Hybrid Analysis, which unifies static and dynamic memory reference techniques into a seamless compiler framework which extracts almost maximum available parallelism from scientific codes and incurs close to the minimum necessary run time overhead. We present how to extract maximum information from the quantities that could not be sufficiently analyzed through static compiler methods, and how to generate sufficient conditions which, when evaluated dynamically, can validate optimizations. Our techniques have been fully implemented in the Polaris compiler and resulted in whole program speedups on a large number of industry standard benchmark applications.
  • Executing sequential code in parallel on a multithreaded machine has been an
    elusive goal of the academic and industrial research communities for many years. It
    has recently become more important due to the widespread introduction of multicores
    in PCs. Automatic multithreading has not been achieved because classic, static
    compiler analysis was not powerful enough and program behavior was found to be, in
    many cases, input dependent. Speculative thread level parallelization was a welcome
    avenue for advancing parallelization coverage but its performance was not always optimal
    due to the sometimes unnecessary overhead of checking every dynamic memory
    reference.
    In this dissertation we introduce a novel analysis technique, Hybrid Analysis,
    which unifies static and dynamic memory reference techniques into a seamless compiler
    framework which extracts almost maximum available parallelism from scientific
    codes and incurs close to the minimum necessary run time overhead. We present how
    to extract maximum information from the quantities that could not be sufficiently
    analyzed through static compiler methods, and how to generate sufficient conditions
    which, when evaluated dynamically, can validate optimizations.
    Our techniques have been fully implemented in the Polaris compiler and resulted
    in whole program speedups on a large number of industry standard benchmark applications.

publication date

  • December 2006