Repository navigation
Expand file tree
/
Copy pathpaper.tex
More file actions
547 lines (460 loc) · 23.6 KB
/
Copy pathpaper.tex
File metadata and controls
547 lines (460 loc) · 23.6 KB
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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
% llncs : version 2.4 for LaTeX2e as of 16. April 2010
\documentclass{llncs}
%
\usepackage{amsmath}
\usepackage{nomencl}
\input{includes}
%
\begin{document}
%
\frontmatter % for the preliminaries
\pagestyle{headings} % switches on printing of running heads
\mainmatter % start of the contributions
%
\title{Automatic Parallelization and Optimization of a
SLAM Application Written in the PENCIL Language}
%
\author{}
\institute{INRIA and \'Ecole Normale Sup\'erieure \\
\email{\textit{first}.\textit{last}@inria.fr}}
\maketitle{}
\begin{abstract}
Low-level GPU programming with CUDA and OpenCL is difficult, error
prone, and not performance-portable. Automatic parallelization
and code optimization techniques have been proposed
to hide this complexity and regain some performance portability.
\pencil{} is a higher level, platform-neutral compute intermediate
language, designed to improve the ability of compilers to better
parallelize and optimize code when targeting accelerators.
In this paper, we report our experience in using automatic
parallelization and optimization techniques of a challenging,
real world application written in \pencil{}:
the KinectFusion application, a large computer
vision and \textit{simultaneous localization and mapping} (SLAM)
application.
We use a polyhedral compiler to map the \pencil{} code into
an OpenCL code.
We demonstrate how \pencil{} helps in enhancing the ability of
that polyhedral compiler to automatically parallelize and optimize
the SLAM application and we show that we obtain acceptable performance
compared to the relatively low programming effort and compared to
the high portability benefit.
\end{abstract}
\section{Introduction}
Special-purpose \emph{accelerators} such as GPUs can significantly
outperform general-purpose processors in terms of raw performance and
energy efficiency. Software for such accelerators is currently
written using low-level APIs and target-specific languages, such as
OpenCL and CUDA, which increases the cost of its development and
maintenance.
Computer vision is a typical domain that relies extensively on the
use of accelerators and where writing low level code to target
different architectures is becoming more and more difficult, error
prone and featuring non-portable optimizations.
On the other hand, writing high level code and lowering that code
through an optimizing compiler naturally arose as a viable alternative.
\pencil{}~\cite{pencil,pencil_pact,pencil_wolfhpc}, a platform-neutral
compute intermediate language is an example of a language that can be
used to target accelerators.
Although the target platforms are highly parallel, \pencil{} has
sequential semantics. In addition, it is equiped with language
constructs and specific properties particularly well
suited for static analysis of array computations.
To compile \pencil{} programs to OpenCL, the polyhedral framework is used,
a program representation and a set of analyses, transformations and code
generation algorithms that enable a compiler to reason about advanced
loop nest transformations addressing most of the parallelism and
locality-enhancing challenges.
To understand the tradeoffs behind the design of such an a
language, we study ....
In this paper, we evaluate \pencil{} on a benchmark from the computer
vision and the \textit{simultaneous localization and mapping} (SLAM)
domains.
This benchmark is particularly interesting as it represents a realistic
application that has code patterns that are challenging for a classical
polyhedral compiler, such as irregular, data-dependent control flow
and array accesses.
We compare the performance of the automatically generated OpenCL codes
with the reference OpenCL manual implementation of SLAMBench.
Although our study focuses on examples from the domain of computer
vision, the proposed language and the \pencil{} compilation flow
is generally applicable to a wide set of array-based computational
problems.
Separate evaluations on the fields of image processing, linear algebra,
signal processing and on the SHOC and Rodinia benchmarks have been
published in~\cite{pencil_pact}.
\section{Overview of the SLAMBench Computer Vision Benchmark}
To explore the applicability of \pencil to a complex,
real-world application, a \pencil port for the SLAMBench
Benchmark was implemented~\cite{SLAMBench2015}.
SLAMBench provides C++, OpenMP, OpenCL, and CUDA implementations
of KinectFusion~\cite{KinectFusion2011}, a dense computer vision
and \textit{simultaneous localization and mapping} (SLAM)
application
SLAMBench was developed as part of the PAMELA project, that
intends to take a holistic approach to the development
of many-core architectures, compilers, and runtime systems,
while focusing on the computer vision application
domain~\cite{PAMELAWeb2012}.
SLAMBench is composed of 12 key kernels (listed in
Table~\ref{SLAMBench_Features}).
\begin{itemize}
\item \textbf{\textit{preprocessing}:} \textit{mm2meters, bilateralFilter};
\item \textbf{\textit{integration}:} \textit{integrate};
\item \textbf{\textit{raycasting}:} \textit{raycast};
\item \textbf{\textit{rendering}:} \textit{renderDepth, renderTrack, renderVolume};
\item \textbf{\textit{tracking}:} \textit{depth2vertex, vertex2normal,
halfSampleRobustImage, track, reduce}.
\end{itemize}
Ten of the twelve can be classified as being irregular:
All kernels except \textit{depth2vertex}, \textit{vertex2Normal},
and \textit{mm2meters} exhibit non static-affine conditions and/or
loop-bounds, while \textit{raycast}, \textit{renderVolume},
\textit{vertex2Normal}, \textit{integrate}, and
\textit{bilateralFilter} also exhibit non static-affine array reads.
TODO: Why is it interesting.
TODO: Show code snapshots.
%-------------------------------------------------
%-------------------------------------------------
\section{Overview of \pencil{}}
\pencil is a subset of the C99 language carefully designed to
capture static properties essential to the implementation of advanced
loop nest transformations. It provides a set of language constructs
that helps parallelizing compilers to perform more accurate static
analyses and to generate efficient target-specific code. These
specific constructs provide information that is difficult for a
compiler to extract but that can be easily captured from a DSL, or
expressed by an expert programmer.
We designed \pencil with four main goals in mind:
(1) the language should simplify static code analysis,
to enable a high degree of optimization.
The main impact of this is that the use of pointers is
disallowed, except in specific cases,
(2) \pencil should provide facilities that allow a domain
expert or a DSL-to-\pencil compiler to convey, in \pencil,
domain-specific information that can be exploited by the \pencil
compiler during optimization,
(3) a standard non-parallelizing C99 compiler that supports
GNU C attributes should be able to compile \pencil.
This ensures portability to platforms without OpenCL support and allows
existing tools to be used for debugging (unparallelized) \pencil code.
(4) we chose a sequential semantics for \pencil in order to simplify
DSL compiler development and the work of a domain expert directly
developing in \pencil, and more importantly, to avoid committing
to any particular pattern(s) of parallelism.
We detail the most important restrictions imposed by \pencil from the point of
view of enabling GPU-oriented compiler optimizations. The \pencil
specification~\cite{pencil} contains the rules in full.
\smallskip\noindent\textbf{Pointer restrictions.}
Pointer declarations and definitions are allowed in \pencil{}, but
pointer manipulation (including arithmetic) is not, except that C99
array references are allowed as arguments in function calls.
Pointer dereferencing is also not
allowed except for accessing C99 arrays. The restricted use of
pointers is important for moving data between different address
spaces of hardware accelerators, as it essentially eliminates aliasing
problems.
\smallskip\noindent\textbf{No recursion.}
Recursive function calls are not allowed, because accelerator programming
languages such as OpenCL forbid this.
\smallskip\noindent\textbf{Sized, non-overlapping arrays.}
Arrays must be declared using the C99 variable-length array
syntax \cite{c99}; array function arguments must be declared using
\lstinline!pencil_attributes!, a macro expanding to the
\lstinline!restrict! and the \lstinline!const! C99 type qualifiers
and to the \lstinline!static! C99 keyword. During optimization,
the \pencil compiler thus knows the length of arrays, and that arrays
do not overlap.
\smallskip\noindent\textbf{Structured \lstinline!for! loops.} A \pencil
\lstinline!for! loop must have a single iterator, an
invariant start value, an invariant stop value and a
constant increment (step). Invariant in this context means that the
value does not change in the loop body. By precisely specifying
the loop format we avoid the need for a sophisticated induction
variable analysis. Such an analysis is not only complex to
implement, but more importantly results in compiler analyses
succeeding or failing under conditions unpredictable to the user.
\smallskip
An additional programming guideline (which is not mandatory as it cannot be
statically checked in general)
is that array accesses should not be linearized. Linearization tends to
obfuscate affine subscript expressions, hindering the effectiveness of
the \pencil compiler.
Multidimensional C99 arrays should be used instead.
The main constructs introduced by \pencil include the
assume builtin function, the
\lstinline!independent! directive, summary functions and
the kill builtin function.
They are described here very briefly, for a complete
description please refer to~\cite{pencil,pencil_pact,pencil_wolfhpc}.
\subsection{Assume Builtin}
\lstinline!__pencil_assume! is an intrinsic function
\lstinline!__pencil_assume(!$e$\lstinline!)!, where $e$ is a logical expression,
indicates that $e$ is guaranteed to hold whenever the control flow reaches
the intrinsic.
This knowledge is taken on trust by the \pencil compiler, and may enable
generation of more efficient code.
An assume statement allows a programmer to communicate high level facts
in the generated code.
A \emph{general 2D convolution} in image processing is a a good
example that demonstrates the use of \lstinline!__pencil_assume!.
This image processing kernel calculates the weighted sum of the
area around each pixel using a kernel matrix for weights.
It is sufficient, in general to consider that the size of the
convolution matrix (the matrix that hols the convolution kernel)
does not exceed $15\times15$.
This can be expressed using the assume builtin as follows:
\begin{lstlisting}[stepnumber=1,numbers=left,numberstyle={\tiny\tt},numbersep=5pt,escapechar=@,language=pencil]
__pencil_assume(kernel_matrix_rows <= 15);
__pencil_assume(kernel_matrix_cols <= 15);
\end{lstlisting}
\subsection{Independent Directive}
\label{sec:for-directives}
The \lstinline!independent! directive is used to annotate loops.
It indicates that the desired result of the loop execution does not
depend in any way upon the execution order of the data accesses from
different iterations. In particular, data accesses from different
iterations may be executed simultaneously.
In practice, the \lstinline!independent! directive can be used to
indicate that the marked loop does not have any loop carried
dependence (i.e., it could be run in parallel).
\subsection{Summary Functions}
\label{sec:summaries}
The effect of a function call on its array arguments is derived
from an analysis of the called function.
In some cases, the results of this analysis may be too inaccurate.
In the extreme case, no code may be available for the function and the
compiler can then only assume that every element of the passed arrays
is accessed.
In order to obtain more accurate information on memory accesses, the user
may tell the compiler to derive the memory accesses not from the actual
function body, but from some other function with the same signature.
Such a function is called a \emph{summary function}.
In practice, summary functions are used to describe the memory access
patterns of (1) library functions called from \pencil code, for which
source code is not available for analysis, and (2) non-\pencil functions
called from \pencil code, as they are otherwise difficult to analyze.
The use of summary functions enables more precise static analysis.
\subsection{\pencil Kill}
\label{sec:kill}
The \lstinline!__pencil_kill! builtin function
allows the user to refine dataflow information
within and across any control flow region in the program.
It is a polymorphic function that signifies that its argument
(a variable or an array element) is dead at the program point
where \lstinline!__pencil_kill! is inserted, meaning that no data
flows from any statement instance executed before the kill to any
statement instance executed after.
\subsection{Non-\pencil{} Region Memory Tag}
The \lstinline!__pencil_npr_mem_tag!\footnote{\lstinline!__pencil_npr_mem_tag!
stands for \emph{Non \pencil Region Memory Tag}.} builtin function has the
following prototype:
\begin{lstlisting}[language=pencil]
void __pencil_npr_mem_tag(void *location, enum npr_mem_tags mode);
\end{lstlisting}
\noindent where \lstinline!mode! can be either \lstinline!r!,
\lstinline!w!, \lstinline!rw! or \lstinline!n!.
If mode is \lstinline!r!, the intrinsic allows the optimizer to assume that
the memory pointed by \lstinline!location! is used for read only in all the
non-\pencil regions that are reachable by the intrinsic (this is
valid until this intrinsic is called once again).
The mode \lstinline!w! indicates that the memory pointed by \lstinline!location!
is used for write only, the mode \lstinline!rw! indicates that it is used for
read and write, and the mode \lstinline!n! indicates that it is not used at
all.
If the assumption is violated during execution, the behavior
is undefined.
\paragraph{Example}
\begin{lstlisting}[language=pencil]
__pencil_npr_mem_tag(A, n);
#pragma pencil region
{
for (int i = 0; i < N; i++)
A[i] = 0;
}
int *B = (int *) malloc (sizeof(int)*N);
#pragma pencil region
{
for (int i = 0; i < N; i++)
B[i] = A[i];
}
\end{lstlisting}
The use of \lstinline!__pencil_npr_mem_tag! indicates that the array \lstinline!A!
is not used in the non-\pencil regions of the program that follow the call to
\lstinline!__pencil_npr_mem_tag!.
In this case, if the \pencil compiler generates OpenCL code, it will avoid
copying the array A back from the GPU device memory into the host memory after
the first \pencil region.
%-------------------------------------------------
%-------------------------------------------------
\section{Polyhedral Compilation of PENCIL Code}
\section{Evaluation}
\label{slambench}
The benchmark reports results for 5 distinct phases, each of which
is composed of one or more of the above kernels.
For each phase, we compare performance against the pre-existing OpenCL
implementation that has been hand-optimized for the ARM Arndale board
with the Mali-T604 GPU.
Methodology
Platforms
Table~\ref{SLAMBench_Speedups} presents the results for our optimized
\pencil implementation, compiled using the best \PPCG tile and
work-group size parameters that could be identified with reasonable
effort.
We present both the wall-clock times as well as only the total kernel
execution times in seconds for both the hand-optimized OpenCL and
\pencil implementations.
The \pencil implementation's wall-clock performance is only
$0.31\times$ that of the hand-optimized OpenCL.
The key reason for this is the current lack of support for whole-program
optimization, particulary with respect to memory allocation across host
and device memory.
The hand-optimized OpenCL judiciously allocates memory between host and
device memory, minimizing unnecessary copies between kernel invocations.
Unfortunately, OpenCL generated from \pencil is compiled as a separate
library that is invoked from within the C++ SLAMBench code.
Therefore, \PPCG is only able to optimize and transform memory access
patterns within each kernel, independently of the other kernels.
Thus each runtime kernel invocation requires copying of the relevant
data-structures from host to device memory, and then back.
As each of the kernels is called either 882 or 2646 times (for the
default dataset), the cumulative effect of these repeated copies
significantly reduces wall-clock performance relative to hand-tuned OpenCL.
Nevertheless, despite the $3\times$ overall slow-down, \pencil SLAMBench
wall-clock performance is still roughly $2.4\times$ better than the
sequential C++ implementation.
\begin{table}[htbp]
\begin{center}
\scalebox{0.85}{
\begin{tabular}{|l|r|r|r|r|r|r|}
\hline
& \multicolumn{2}{c|}{\textbf{OpenCL}} & \multicolumn{2}{c|}{\textbf{PENCIL}} & \multicolumn{2}{c|}{\textbf{SpeedUp}} \\ \hline
\textbf{Phases} & \textbf{clock} & \textbf{kernel} & \textbf{clock} & \textbf{kernel} & \textbf{clock} & \textbf{kernel} \\ \hline
preprocessing & 16.2 & 10.5 & 23.8 & 11.4 & $0.68\times$ & $0.92\times$ \\ %\hline
integration & 69.3 & 67.7 & 403.7 & 93.7 & $0.17\times$ & $0.72\times$ \\ %\hline
raycasting & 65.8 & 64.8 & 97.3 & 56.7 & $0.68\times$ & $1.14\times$ \\ %\hline
rendering & 23.3 & 17.9 & 44.8 & 15.7 & $0.52\times$ & $1.14\times$ \\ %\hline
tracking & 98.9 & 50.2 & 355.1 & 81.5 & $0.28\times$ & $0.62\times$ \\ %\hline
\textbf{Total} & \textbf{279.2} & \textbf{200.5} & \textbf{906.1} & \textbf{259.1} & \textbf{0.31$\times$} & \textbf{0.77$\times$} \\ \hline
\end{tabular} }
\end{center}
\vskip-0.1cm
\caption{Performance comparison of the PENCIL implementation of
SLAMBench vs. hand-optimized OpenCL, on ARM Mali-T604.}
\label{SLAMBench_Speedups}
\vskip-0.1cm
\end{table}
Furthermore, though the \pencil implementation exhibits only a third
of the wall-clock performance of hand-optimized OpenCL, the kernel-only
execution times are only 23\% slower overall. The \textit{raycasting} and
\textit{rendering} phases even exhibit a 14\% kernel performance improvement
over hand-optimized OpenCL, while the \textit{preprocessing} phase is only
about 8\% slower.
The reason that kernel performance is sometimes better than hand-optimized
OpenCL is that the simplicity and higher-level of abstraction provided by
\pencil make it much easier to more thoroughly explore the optimization
search-space, simply by changing the \PPCG compiler parameters.
This is in contrast to the more involved and careful changes that must
be manually made to OpenCL host and kernel code for each set of tile
and work-group size parameters, or for any of the loop optimizations
and transforms that must be manually implemented without the assistance
of a polyhedral compiler.
Note that unlike the other benchmarks discussed above, the SLAMBench
\pencil compilation flow did not make use of auto-tuning, so the current
best \PPCG parameters were discovered through manual trial-and-error.
With further work, we hope to make use of auto-tuning to further improve
upon the reported kernel performance figures. To improve to wall-clock
performance and improve memory allocation across the system, further
enhancements to both the \pencil language and the \PPCG compiler must
be considered.
Table~\ref{SLAMBench_Features} lists the \pencil features that affect
the implementation and/or performance of each of the ported kernels.
All of the kernels that have non static-affine code require \PPCG's
support for irregular code compilation.
In addition, most such kernels also make use of summary
functions -- innermost loop code was extracted into library functions
that were called from within the \pencil code.
This was needed to incorporate non-polyhedral code optimizations like
vector data-types, that were necessary to improve performance relative
to the hand-optmized OpenCL.
%track: NSCC
%raycast: NSCC, NSRD
%renderVolume: NSCC, NSRD
%renderTrack: NSCC
%renderDepth: NSCC
%halfSampleRobustImage: NSCC
%vertex2Normal: NSRD
%depth2Vertex:
%mm2meters:
%integrateKernel: NSCC, NSRD
%bilateralFilter: NSCC, NSRD
%reduce: NSCC
\begin{table}[htbp]
\centering
\begin{center}
\scalebox{0.75} {
\begin{tabular}{|l|l|l|l|}
\hline
Kernel & no support for & no parameter & no \\
& \textit{irregular} code & tuning & \textit{assumes} \\
% & or summary functions & & \\
\hline
\textit{mm2meters} & - & $15\% \downarrow$ & $28\% \downarrow$ \\
\textit{bilateralFilter} & no code generation & - & $14\% \downarrow$ \\
\textit{integrate} & no code generation & $51\% \downarrow$ & - \\
\textit{depth2vertex} & - & - & $79\% \downarrow$ \\
\textit{vertex2normal} & no code generation & $58\% \downarrow$ & - \\
\textit{halfSampleRobustImage} & no code generation & $14\% \downarrow$ & $6\% \downarrow$ \\
\textit{renderDepth} & no code generation & - & $23\% \downarrow$ \\
\textit{renderTrack} & no code generation & - & $5\% \downarrow$ \\
\textit{renderVolume} & no code generation & $52\% \downarrow$ & - \\
\textit{raycast} & no code generation & $51\% \downarrow$ & - \\
\textit{track} & no code generation & $27\% \downarrow$ & $4\% \downarrow$ \\
\textit{reduce} & no code generation & $24\% \downarrow$ & - \\
\hline
\end{tabular} }
\end{center}
\vskip-0.2cm
\caption{\label{SLAMBench_Features}Effect of not Using \pencil Features on the Speedups}
\vskip-0.5cm
\end{table}
The \pencil based SLAMBench implementation performance was also
highly sensitive to \PPCG's compiler flags, in particular the
work-group and tile size parameters for each kernel.
The third column of Table~\ref{SLAMBench_Features} presents the
performance impact of compiling each kernel with default
parameters only, relative to execution with the most optimized
set of parameters.
Many of the kernels exhibit performance degradation of $15-60\%$.
Also removing the \lstinline!__pencil_assume! statements further
degrades the performance of some of the kernels by $4-80\%$.
The results in this section demonstrate the potential advantages
of the \pencil language and polyhedral compilation for rapidly
implementing and tuning code for execution on GPUs or other
accelerators, even for a complex, real-world application like
KinectFusion.
We also identify a key remaining issue that need to be addressed
-- optimizing memory allocation and communication across host
and accelerator -- for this to become the preferred approach to
rapid and efficient accelerator programming.
% This is what we do here: (a) a short description of SLAMBench:
% what it is, why it is relevant etc. (PAMELA justification here),
% followed by (b) Characteristics of SLAMBench: it contains irregular
% code, is a full application (i.e. pencil code must be incorporated
% with irregular, non-compute CPP benchmark code), and (c) the
% constituents of SLAMBench - the various kernels, divided into phases.
% some insight into the kernel code itself (esp the key ones: integrate,
% track, reduce).
% For SLAMbench, several features were essential for either getting
% it to work at all or having it perform correctly.
% Summary functions used extensively.
% These were sometimes necessary to overcome some fragility in
% our toolchain, but also proved useful in enabling target-specific,
% non-polyhedral, OpenCL code optimizations like vectorization.
% Also used: assumes. independent directive was not needed.
% kills not used, but could've helped.
\section{Related Work}
\section{Conclusion}
\bibliographystyle{abbrv}
\bibliography{bibliographies/pencilbib,bibliographies/SLAMBenchCitations}
\end{document}