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
|
\environment fonts_env
\environment lsr_env
\startcomponent pipelining
\chapter[sec:pipelining]{Loop Pipelining}
\startsynopsis
This section describes the future plans of implementing loop pipelining in Vericert, also called
loop scheduling. This addresses the final major issue with Vericert, which is efficiently
handling loops.
\stopsynopsis
Standard instruction scheduling only addresses parallelisation inside hyperblocks, which are linear
sections of code. However, loops are often the most critical sections in code, and scheduling only
addresses parallelisation within one iteration.
\section{Loop pipelining example}
\startplacemarginfigure[location=here,reference={fig:pipelined-loop},title={Example of pipelining a
loop.}]
\startfloatcombination[nx=2]
\startplacesubfigure[title={Simple loop containing an accumulation of values with an
inter-iteration dependency.}]
\startframedtext[frame=off,offset=none,width={0.6\textwidth}]
\starthlC
for (int i = 1; i < N; i++) {
c1 = acc[i-1] * c;
c2 = x[i] * y[i];
acc[i] = c1 + c2;
}
\stophlC
\stopframedtext
\stopplacesubfigure
\startplacesubfigure[title={Pipelined loop reducing the number of dependencies inside of the
loop.}]
\startframedtext[frame=off,offset=none,width={0.6\textwidth}]
\starthlC
c1 = acc[0] * c;
c2 = x[1] * y[1];
for (int i = 1; i < N-1; i++) {
acc[i] = c1 + c2;
c2 = x[i+1] * y[i+1];
c1 = acc[i+1] * c;
}
acc[N-1] = c1 + c2;
\stophlC
\stopframedtext
\stopplacesubfigure
\stopfloatcombination
\stopplacemarginfigure
\in{Figure}[fig:pipelined-loop] shows an example of pipelining a loop which accumulates values and
modifies an array. In \in{Figure}{a}[fig:pipelined-loop], the body of the loop cannot be scheduled
in less than three cycles, assuming that a load takes two clock cycles. However, after transforming
the code into the pipelined version on the right
\startmode[section]
\section{Bibliography}
\placelistofpublications
\stopmode
\stopcomponent
|
