# What are current approaches to auto-parallelisation?

I am looking for answers which provide short overview of models and current state of research for auto-parallelisation of sequential code.

• Are there some things you already know? – Raphael Aug 14 '12 at 7:07
• @Raphael Hmm... I think I have some level of understanding about internal workings of GCC's implementation of OpenMP and have been through a standard course in Parallel Programming and another in Distributed Systems. – check123 Aug 14 '12 at 17:14
• On a side note, I have checked over in library, open access publications and Google (implied?) for generic notes on Auto-Parallelisation without much success the content usually relates to specific system/implementation under consideration and not the general problem of auto-parallelisation. – check123 Aug 14 '12 at 17:19
• Do you want the compiler to find exploitable parallelism, or do you want it to act on some annotations? – Raphael Aug 14 '12 at 20:34
• First one: Compiler finding exploitable parallelism. Not annotation driven. – check123 Aug 15 '12 at 6:13

Automatic parallelization in the most general terms is extracting a dependency graph from the execution sequence of the program and executing distinct paths in this graph in parallel with synchronization introduced at the nodes of the graph where the paths merge.

Our ability to extract the dependency information varies depending on the programming language used. Functional languages have no side effects that makes it easier to parallelize. It is more difficult with imperative languages. Several programming languages were proposed where parallelism may be implicit. Such as array programming languages.

Autoparallelization of inherently sequential programs like programs written in C or FORTRAN attracts significant practical interest. One classical reference work on the subject is Michael Wolfe's "Optimizing Supercompilers for Supercomputers" based on his 1982 PhD thesis [1].

One of the key areas of the work is parallelizing multidimensional loops. Observe that loop indices are often used in linear combinations inside loops (e.g. for a $N\times N$ matrix $a$ in a C language program a[I][J] is a reference to an element that lies at position a + I * N + J). Therefore dependencies between iterations can be expressed as linear equations. Thus the ability to solve systems of linear equations efficiently is important for autoparallelizing compilers.

In an important general case finding depdendencies between operators in a loop requires finding all solutions of a system of linear equations in integers. There exists no polynomial algorithm for finding a solution of such a system of equations, therefore approximate tests are employed, that can detect independence. An important class of tests are derived from Banerjee Inequality.

The essense of the method is as follows. Let $x$ and $y$ be vectors of unknowns of dimension $d$, and $\textrm{A}$, $\textrm{B}$ be some linear operators. For loop dependencies the values of indices usually have upper and lower bounds. Suppose $m_i \leq x_i,y_i \leq M_i$.

To test if a system of linear equations $\textrm{A}x - \textrm{B}y = c$ has a solution we find the upper bounds $UB_j$ and lower bounds $LB_j$ of $\textrm{A}x - \textrm{B}y$ for all possible values of $x$ and $y$, $m_i \leq x_i,y_i \leq M_i$ and test if $c$ lies within the bounds. If it does not, then there is no solution, and two memory references are independent, hence can be executed in parallel. This test is incomplete, but can be efficiently computed.

Different data-dependence heuristics are compared on real and synthetic benchmarks [2]. A recent overview of data-dependence analysis techniques can be found in the publications from the UCSD Kremlin project [3].

1. M. Wolfe, Optimizing Supercompilers for Supercomputers, 1989

2. K. Psarris, K. Kyriakopoulos, An Experimental Evaluation of Data Dependence Analysis Techniques, IEEE Transactions on Parallel and Distributed Systems, March 2004 (vol. 15 no. 3), pp. 196-213

3. S. Garcia, D. Jeon, C. Louie, M.B. Taylor, Kremlin: Rebooting and Rethinking gprof for the Multicore Age, PLDI'2011