Dr Wayne KellyDiscovering Inherent Parallelism in Sequential Programs

Objective of presentation:

To explain some of the key challenges faced today by developers trying to parallelise sequential programs and to present some next generation, work in progress ideas for addressing these challenges.



Most parallel programs start life as sequential programs. We first code the algorithm; debug it to get it working and then (maybe at a much later stage) try to parallelise it to improve performance. Trying to determine which parts of a sequential program can be safely run in parallel is often very challenging – especially when seeking to parallelise “coarse-grained” outer loops were the code inside the loop(s) contain many function calls, possibly to code that we didn’t write and don’t fully understand. Even compilers specifically designed to automatically parallelise such programs generally struggle to perform precise enough static dependence analysis to parallelise most real programs. The principle challenge is memory aliasing – knowing for sure whether arbitrary instructions might ever access the same memory locations. Unless a parallelising compiler can be certain that a dependence can never exist, it must conservatively decide not to parallelise that code.

At runtime, however, this memory aliasing uncertainty disappears – we know exactly which memory locations are accessed by each instruction. This talk presents the idea of dynamically instrumenting code so that all data and control dependencies that actually arise at runtime are logged and used to determine which parts of the program could have been safely executed in parallel. In other words, it’s a tool to help programmers better understand the flow of data and control within programs they’re trying to parallelise.

The dynamic instrumentation is done as part of the JIT processing of the open source Mono.NET runtime environment on Linux. The dynamically determined data dependencies are exported in an XML format and then presented to the programmer as a graphical overlay on their source code in an IDE designed to serve as parallel programmer’s workbench.



  • Exploiting inherent parallelism in sequential programs.
  • How data and control dependencies prevent parallelisation.
  • How to dynamically determine data and control dependencies.
  • Demo of dynamic data dependence collection using Mono.NET runtime on Linux.
  • Demo of graphical overlay of dependences in IDE.
  • Discussion of where to from here?


Target audience:

  • Developers wanting to understand some of the key challenges of parallelising sequential programs
  • Parallel developers seeking new tools/approaches to make their jobs easier
  • Those who like hacking JITs and assembly code