Techniques for Reducing the Overhead of Run-Time Parallelization Conference Paper uri icon

abstract

  • © Springer-Verlag Berlin Heidelberg 2000. Current parallelizing compilers cannot identify a significant fraction of parallelizable loops because they have complex or statically insufficiently defined access patterns. As parallelizable loops arise frequently in practice, we have introduced a novel framework for their identification: speculative parallelization. While we have previously shown that this method is inherently scalable its practical success depends on the fraction of ideal speedup that can be obtained on modest to moderately large parallel machines. Maximum parallelism can be obtained only through a minimization of the run-time overhead of the method, which in turn depends on its level of integration within a classic restructuring compiler and on its adaptation to characteristics of the parallelized application. We present several compiler and run-time techniques designed specifically for optimizing the run-time parallelization of sparse applications. We show how we minimize the run-time overhead associated with the speculative parallelization of sparse applications by using static control flow information to reduce the number of memory references that have to be collected at run-time. We then present heuristics to speculate on the type and data structures used by the program and thus reduce the memory requirements needed for tracing the sparse access patterns. We present an implementation in the Polaris infrastructure and experimental results.

name of conference

  • Compiler Construction, 9th International Conference, CC 2000, Held as Part of the European Joint Conferences on the Theory and Practice of Software, ETAPS 2000, Berlin, Germany, Arch 25 - April 2, 2000, Proceedings

published proceedings

  • COMPILER CONSTRUCTION, PROCEEDINGS

author list (cited authors)

  • Yu, H., & Rauchwerger, L

citation count

  • 7

complete list of authors

  • Yu, Hao||Rauchwerger, Lawrence

editor list (cited editors)

  • Watt, D. A.

publication date

  • January 2000