Optimizing Nondeterminacy: Exploiting Race Conditions in Parallel Programs

William Moses, Massachusetts Institute of Technology

Photo of William Moses

As computation moves toward parallel programming models, writing efficient parallel programs becomes paramount. That has led to several efforts (Tapir, HPVM, among others) to augment serial compilers such as LLVM to have a first-class representation of parallelism. Such representations theoretically permit the compiler to both analyze and optimize parallel programs.

A major difference between serial and parallel programs is that in many parallel runtimes one cannot make any assumptions about the ordering of various logical tasks. This nondeterminism creates an opportunity for the compiler. Since any ordering is valid, the compiler can also reorder tasks if it believes it beneficial.

This poster will discuss how the compiler can take advantage of this nondeterminacy through a number of example optimizations, examining their theoretical implications as well as how they perform when implemented atop the Tapir extension to LLVM.

Abstract Author(s): William S. Moses