Information Technology Reference
In-Depth Information
(
Iteration
(
ʷ
)
, Switching
)
(1
,
2)
(2
,
3)
,
(3
,
2)
(4
,
4)
,
(5
,
2)
,
(6
,
3)
,
(7
,
2)
(8
,
5)
,
(9
,
2)
,
(10
,
3)
,
(11
,
2)
,
(12
,
4)
,
(13
,
2)
,
(14
,
3)
,
(15
,
2)
···
(2
ʳ−
2
,ʳ−
2+2)
,
(2
ʳ−
2
+1
,
2)
, ···,
(2
ʳ−
1
−
2
,
3)
,
(2
ʳ−
1
−
1
,
2)
(2
ʳ−
1
,ʳ
−
1+2)
,
(2
ʳ−
1
+1
,
2)
,
···
,
(2
ʳ
−
2
,
3)
,
(2
ʳ
−
1
,
2)
(a) Inter-iteration switching after each iteration from iteration 1 to iteration 2
ʳ
−
1
Iteration Range
1
2
to
3
4
to
7
8
to
15
Total Switching
s
1
=2
s
2
=
s
1
+3
×
2
0
=2+3
s
3
=
s
2
+3
=2
=5
=11
=23
×
2
1
=5+6
s
4
=
s
3
+3
×
2
2
=11+12
···
···
···
···
2
ʳ−
2
to
2
ʳ−
1
s
ʳ−
1
=
s
ʳ−
2
+3
×
2
ʳ−
3
s
ʳ
=
s
ʳ−
1
+3
×
2
ʳ−
2
=3
×
2
ʳ−
2
−
1
−
1
2
ʳ−
1
to
2
ʳ
=3
×
2
ʳ−
1
−
1
−
1
(b) Total inter-iteration switching in mentioned iteration ranges
Fig. 5.
Inter-iteration switching on the address bus of data memory for
LUG
in
Fig. 2(c), where,
base address
(
a
)=0
the first memory address reference (of
a
[
i
next
]) in the (
uf
+2)
th
iteration (next
iteration).
S
LUG inter
can be obtained from Fig. 5. Figure 5(a) shows the inter-
iteration switchings for each iteration (from iteration 1 to iteration 2
ʳ
1). In
Fig. 5(b) the total inter-iteration switching in the mentioned iteration ranges
forms a series whose
ʳ
th
term is obtained from the recurrence relation as shown
in equation (9)
−
2
ʳ−
2
,forʳ>
1
,ands
1
=2
s
ʳ
=
s
ʳ−
1
+3
×
(9)
The solution of the recurrence relation in equation (9) is shown in equation (10)
2
ʳ−
1
s
ʳ
=3
×
−
1
.
(10)
The
S
LUG inter
can be obtained from the summation of the series obtained in
Fig. 5(b). This can be written as
S
LUG inter
=3
×
(2
0
+2
1
+2
2
+
···
+2
ʳ−
1
)
−ʳ
=
3
(2
ʳ
×
−
1)
−
ʳ
. The final expression for
S
LUG inter
can be written as shown in
equation (11).
n
uf
−
1
log
2
n
uf
S
LUG inter
=3
×
−
(11)
Substituting equations (8) and (11) in equation (7), the expression of
S
LUG
is
obtained as
S
LUG
=
uf
−
1
n
log
2
uf
. Table 1 compares
uf
×
(
uf
−
1) + 3
×
−
S
LU
and
S
LUG
considering
n
=2
10
. For any
n
,
n
uf
reduction in
S
LUG
is
minimum (25%) when
uf
=2
2
and maximum (50%) when a loop is totally
unrolled (
n
=
uf
). But, total loop unrolling is impractical due to hardware
limitations of the system.
≥
