blob: 0beeb8234fa3535f280e196c4007b3bd25d3a078 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
|
<!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 is part of the Google Summer of Code 2011. Hence,
it 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.
</div>
</body>
</html>
|
