Parallelization of utility programs based on behavior phase analysis

Abstract. With the fast development of multiple core processors, automatic par-allelization becomes increasingly important. In this work, we focus on the par-allelization of utility programs, a class of commonly used applications includ-ing compilers, transcoding utilities, compresses, database and so on. They take a series of requests as inputs and serve them one by one. Their highly input-dependence poses a big challenge to analysis and optimizations. We use active profiling to find behavior phase boundaries and then automati-cally detect dependences through profiling.. Under a unified framework, we par-allelize the programs at phase boundaries. This technology enables large-grain parallelization, which may span many loops and subroutines. The parallelized programs show significant speedup on both uniprocessor and multiple-processor machines.