Information Technology Reference
In-Depth Information
register int i
;
data type a
[
n
];
for
(
i
=0;
i<n
;
i
=
i
+
uf
)
{
a
[
i
]=
value
;
a
[
i
+1]=
value
;
a
[
i
+2]=
value
;
a
[
i
+3]=
value
;
···
a
[
i
+
uf
register int i
;
data type a
[
n
];
for
(
i
=0;
i<n
;
i
=
i
+
uf
)
{
a
[
i
]=
value
;
a
[
i
+1]=
value
;
a
[
i
+3]=
value
;
a
[
i
+2]=
value
;
···
a
[
i
+
u
2
+1]=
value
;
a
[
i
+
u
2
]=
value
;
register int i
;
data type a
[
n
];
for
(
i
=0;
i<n
;
i
++)
{
a
[
i
]=
value
;
}
(a) Original Loop
−
2] =
value
;
a
[
i
+
uf
−
1] =
value
;
}
}
(b)
LU
(c)
LUG
Fig. 2.
Generalized form of the original loop,
LU
and
LUG
int, long int, float, double,
etc. Each element belonging to a
data type
consumes
sizeof
(
data type
) bytes of memory space, where
sizeof
(
data type
)isapowerof
2. Let,
base address
(
a
) be the base address or the starting address of the array
a
.Let,
b
be obtained by shifting
base address
(
a
)
log
2
sizeof
(
data type
) bits
right. The value of
b
signifies the portion (bits) of the address of array elements
involved in switching activity. The
log
2
sizeof
(
data type
) least significant bits
(
lsb
s) of the address of the array elements are not involved in switching activity,
and remain same for all elements of the array. Let,
a
be an array of
n
=2
ʱ
elements and
uf
=2
ʲ
be the loop unrolling factor, where
ʱ
≥
ʲ
and
ʱ
,
ʲ
uf
=2
ʱ−ʲ
=2
ʳ
times. The
expressions for
S
LU
and
S
LUG
are derived in sections 2.2 and 2.3, respectively,
considering
base address
(
a
)=0and
n
is divisible by
uf
.
n
are natural numbers. The unrolled loop iterates,
2.2 Derivation of
S
LU
S
LU
is dependent on intra-iteration switching (
S
LU intra
) and inter-iteration
switching (
S
LU inter
). So,
S
LU
can be written as shown in equation (1)
S
LU
=
S
LU intra
+
S
LU inter
(1)
S
LU intra
is the total number of
0
0
bit transitions on the
address bus of the data memory, which takes place due to the memory address
references of the elements of array
a
, i.e.
a
[
i
]
,a
[
i
+1]
, ..., a
[
i
+
uf
1
and
1
−
to
−
−
to
−
−
2]
,a
[
i
+
uf
−
1]
(in (
uf
+1)
th
iteration, where, 0
i<n
and
i
is a multiple of
uf
), within the
body of the unrolled loop. For each iteration
ʲlsb
sof
b
follows the sequence
0
,
1
,
2
,
3
,
≤
···
,uf
−
2
,uf
−
1. So,
S
LU intra
can be written as shown in equation (2)
n
uf
× t
ʲ
S
LU intra
=
(2)
where
t
ʲ
is the number of intra-iteration switchings per iteration.
t
ʲ
can be
expressed by the recurrence relation as shown in equation (3)
t
ʲ
=2
×
t
ʲ−
1
+
ʲ, for ʲ >
1
,andt
1
=1
(3)