ParaSCAN: A Static Profiler to Help Parallelization

Parallelizing software often starts by profiling to identify program paths that are worth parallelizing. Static profiling techniques, e.g. hot paths, can be used to identify parallelism opportunities for programs that lack representative inputs and in situations where dynamic techniques aren\u27t applicable, e.g. parallelizing compilers and refactoring tools. Existing static techniques for identification of hot paths rely on path frequencies. Relying on path frequencies alone isn\u27t sufficient for identifying parallelism opportunities. We propose a novel automated approach for static profiling that combines both path frequencies and computational weight of the paths. We apply our technique called ParaSCAN to parallelism recommendation, where it is highly effective. Our results demonstrate that ParaSCAN\u27s recommendations cover all the parallelism manually identified by experts with 85% accuracy and in some cases also identifies parallelism missed by the experts