Information Technology Reference
In-Depth Information
2 Present Work
2.1 Basic Approach
define n
1000000
int main
()
{
register int i
;
int a
[
n
];
for
(
i
=0;
i<n
;
i
=
i
+ 16)
{
a
[
i
]=0;
a
[
i
+1]=0;
a
[
i
+2]=0;
define n
1000000
int main
()
{
register int i
;
int a
[
n
];
for
(
i
=0;
i<n
;
i
=
i
+ 16)
{
a
[
i
]=0;
a
[
i
+1]=0;
a
[
i
+3]=0;
a
[
i
+2]=0;
a
[
i
+6]=0;
a
[
i
+7]=0;
a
[
i
+5]=0;
a
[
i
+4]=0;
a
[
i
+12]=0;
a
[
i
+13]=0;
a
[
i
+15]=0;
a
[
i
+14]=0;
a
[
i
+10]=0;
a
[
i
+11]=0;
a
[
i
+9]=0;
a
[
i
+8]=0;
define n
1000000
int main
()
{
register int i
;
int a
[
n
];
for
(
i
=0;
i<n
;
i
++)
{
a
[
i
]=0;
}
return
0;
a
[
i
+3]=0;
a
[
i
+4]=0;
a
[
i
+5]=0;
a
[
i
+6]=0;
a
[
i
+7]=0;
a
[
i
+8]=0;
a
[
i
+9]=0;
a
[
i
+10]=0;
a
[
i
+11]=0;
a
[
i
+12]=0;
a
[
i
+13]=0;
a
[
i
+14]=0;
a
[
i
+15]=0;
}
(a) Original Program
}
return
0;
}
return
0;
}
(b) Original Program with loop
}
(c) Original Program with unrolled loop
having partial Gray code sequence
unrolling
Fig. 1.
Programs for array initialization
Figure 1(a) shows a program where all the
n
elements of an array
a
are
initialized to an integer value
0
. This array initialization involves sequential
access of
n
memory locations, where the index variable
i
'isstoredinaCPU
register. The program in Fig. 1(b) is the loop unrolled version of the program
in Fig. 1(a), where the loop unrolling factor (
uf
)is
16
. Loop unrolling reduces
the number of loop manipulation instructions by a factor
uf
, saving time and
energy. The program in Fig. 1(c) is a loop unrolled version of the program in
Fig. 1(a), where the array
a
s memory address references within the body of the
unrolled loop follows a Gray code sequence. So, the number of
0
1
and
−
to
−
1
0
bit transitions for array
a
s memory address references within the body
of the unrolled loop, referred as intra-iteration switching, is restricted to
uf
−
to
−
1
.
The present work refers a simple unrolled loop as
LU
, and an unrolled loop with
partial Gray code sequence as
LUG
.Thenumberof
0
−
0
bit transitions (switchings) on the address bus of the data memory for
LU
and
LUG
are referred as
S
LU
and
S
LUG
, respectively. Figure 2 shows the generalized
form of the original loop,
LU
and
LUG
, where an array
a
is initialized with
value
.Where,
value
is either a constant or a variable stored in CPU register.
Let,
data type
be the type of data stored in the array
a
,
data type
may be
char,
1
and
1
−
to
−
−
to
−