Automatic Parallelization of Irregular x86-64 Loops

Abstract

Productivity languages such as Python and R are growing in popularity especially in the development of data analysis algorithms. While these languages provide powerful tools to accelerate the development process, they incur heavy overhead due to their interpreted nature. One approach to remove this overhead is to specialize the interpreter for a given script. Then, loops in the specialized code can be parallelized to further improve performance. In contrast to previous work that targets LLVM loops with affine memory access patterns, we are investigating the problem of parallelizing loops with irregular access patterns at the x86 level. To do so, we split hot loops into a sequential master thread that sends tasks to parallel worker threads.