<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN"
        "http://www.w3.org/TR/html4/strict.dtd">
<!-- Material used from: HTML 4.01 specs: http://www.w3.org/TR/html401/ -->
<html>
<head>
  <META http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
  <title>Polly - Memory access optimizations</title>
  <link type="text/css" rel="stylesheet" href="../menu.css">
  <link type="text/css" rel="stylesheet" href="../content.css">
</head>
<body>
<!--#include virtual="../menu.html.incl"-->
<div id="content">
  <!--*********************************************************************-->
  <h1>Polly - Memory access optimizations</h1>
  <!--*********************************************************************-->
<p><em>WARNING: This project was part of the Google Summer of Code 2011.
Tt is currently not finished, but it is in the design and implementation stage.
The Ideas/Plans described here may not yet be implemented in Polly and may be
changed during the actual implementation.</em></p>

This project adds memory access transformations to Polly. In many cases
changing the memory access pattern yields to better data locality or removes
dependences that would otherwise block transformations.

<p>An examples which uses this feature is given below.</p>

Consider the following loop
<pre>
for (i = 0; i < 8; i++)
  sum += A[i];
</pre>
Through memory access transformations this loop can be executed in parallel.
It can be transformed to
<pre>
<em>// Create and initialize an array 'tmp' with size 4</em>
for (i = 0; i < 8; i++)
  tmp[i % 4] += A[i];
sum = tmp[0] + tmp[1] + tmp[2] + tmp[3];
</pre>

Optimizers like PluTo can schedule the code such that an outer, parallel
loop is created:
<pre>
parfor (ii = 0; ii < 4; ii++) {
  tmp[ii] = 0;
  for (i = ii * 2; i < (ii+1) * 2; i++)
    tmp[ii] += A[i];
  }
sum = tmp[0] + tmp[1] + tmp[2] + tmp[3];
</pre>

<h2>TODO</h2>
<h3>Step 1</h3>
Polly exports its polyhedral description in a JSCoP file. Define how memory
layout transformations are expressed in Polly and in the JSCOP file. 
Example:

<p>Consider the following loop.</p>
<pre>
for (i = 0; i < 12; i++)
  A[i] = 0;
</pre>
In the JSCOP file the memory accesses are represented as follows.
<pre>
"accesses": [{
        "kind": "write",
                "relation": "{ Stmt[i] -> A[i] }"
}]
</pre>
To perform a transformation we generate the following code:
<pre>
for (i = 0; i < 12; i++)
  A[0] = i;
</pre>
The representation in the JSCoP file is:
<pre>
"accesses": [{
        "kind": "read",
                "relation": "{ Stmt[i] -> A[0] }"
}]
</pre>
We need to detect this access function change.

<h3>Step 2</h3>
Update the code generation module to reflect the access function change made
in Step 1.
<h3>Step 2.1 Code generation for a constant</h3>
In the JSCOP file an access function which has variables is changed to a
constant. Code is generated to reflect this change. Let the content of original
JSCOP file be:
<pre>
"accesses" : [{
        "kind" : "read",
                 "relation" : "{ Stmt_for_body[i0] -> MemRef_A[i0] }"
}]
</pre>
The transformed JSCOP file is:
<pre>
"accesses" : [{
        "kind" : "read",
                 "relation" : "{ Stmt_for_body[i0] -> MemRef_A[10] }"
}]
</pre>
Code is generated for this change.
<h3>Step 2.2 Code generation for coefficients</h3>
The coefficients of induction variables are changed here. Let the original
JSCOP file be:
<pre>
"accesses" : [{
      "kind" : "read",
               "relation" : "{ Stmt_for_body3[i0, i1] -> MemRef_A[32i0+i1] }"
}]
</pre>
The transformed JSCOP file is:
<pre>
"accesses" : [{
      "kind" : "read",
               "relation" : "{ Stmt_for_body3[i0, i1] -> MemRef_A[16i0+2i1+5] }"
}]
</pre>
Code is generated for this change.
</div>
</body>
</html>