Evaluating automatic parallelization in SUIF

This paper presents the results of an experiment to measure empirically the remaining opportunities for exploiting loop-level parallelism that are mis sed by the Stanford SUIF compiler, a state-of-the-art automatic paralleliza tion system targeting shared-memory multiprocessor architectures. For the p urposes of this experiment, we have developed a run-time parallelization te st called the Extended Lazy Privatizing Dealt (ELPD) test, which is able to simultaneously test multiple loops in a loop nest. The ELPD test identifie s a specific type of parallelism where each iteration of the loop being tes ted accesses independent data. possibly by making some of the data private to each processor. For 29 programs in three benchmark suites, the ELPD test was executed at run time for each candidate loop left unparallelized by th e SUIF compiler to identify which of these loops could safely execute in pa rallel for the given program input. The results of this experiment point to two main requirements for improving the effectiveness of parallelizing com piler technology: incorporating control flow tests into analysis and extrac ting low-cost run-time parallelization tests from analysis results.