Loop Parallelization

Loop parallelization is the transformation of a sequential loop into a parallel loop whose iterations can execute concurrently on multiple processors. The correctness of this transformation depends on proving that no two iterations write to the same memory location or that any shared writes are synchronized — a problem that reduces, in the general case, to alias analysis over loop-carried pointers. The inability to prove non-aliasing is the single greatest barrier to automatic parallelization of legacy code, and it has motivated decades of research into increasingly precise pointer analyses.

Loop parallelization is where the theoretical limits of alias analysis become the practical limits of hardware utilization. A processor with sixty-four cores is useless if the compiler cannot prove that sixty-four iterations of a loop are independent — and the compiler cannot prove independence if the pointer analysis is too weak to distinguish different objects. We are not waiting for better hardware; we are waiting for better proofs.